EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs

Abstract

We report a surprising, persistent pattern in an important class of large sparse social graphs, which we term eigenspokes. We focus on large mobile call graphs, spanning hundreds of thousands of nodes and edges, and find that the singular vectors of these graphs exhibit a striking eigenspokes pattern wherein, when plotted against each other, they have clear, separate lines that often neatly align along specific axes (hence the term "spokes"). We show this phenomenon to be persistent across both temporal and geographic samples of Mobile Call graphs. Through experiments on synthetic graphs, EigenSpokes are shown to be associated with the presence of community structure in these social networks. This is further verified by analysing the eigenvectors of the mobile call graph, which yield nodes that form tightly-knit communities. The presence of such patterns in the singular spectra has useful applications, and could potentially be used to design simple, efficient community extraction algorithms.