2009 IEEE International Conference on Data Mining Workshops EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs Miami, Florida, USA December 06-December 06 ISBN: 978-0-7695-3902-7
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.
Citation:
B. Aditya Prakash, Mukund Seshadri, Ashwin Sridharan, Sridhar Machiraju, Christos Faloutsos, "EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs," icdmw, pp.290-295, 2009 IEEE International Conference on Data Mining Workshops, 2009 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||