Paper Info
Title
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.
Year
DOI
Venue
2010
10.1007/978-3-642-13672-6_42
PAKDD'10 Proceedings of the 14th Pacific-Asia conference on Advances in Knowledge Discovery and Data Mining - Volume Part II
Keywords
DocType
Volume
surprising patterns,efficient community extraction algorithm,large mobile call graph,large sparse social graph,persistent pattern,large graphs,surprising pattern,large sparse graph,striking eigenspokes pattern,large graph,form tightly-knit community,scalable community chipping,eigenspokes pattern,fast algorithm,community structure,scalable community,fundamental attribute,term eigenspokes,patent citations,singular spectrum,mobile call graph
Conference
6119
ISSN
ISBN
Citations 
0302-9743
3-642-13671-0
69
PageRank 
References 
Authors
2.36
23
5
Name
Order
Citations
PageRank
B. Aditya Prakash194153.95
Ashwin Sridharan2692.36
Ashwin Sridharan372455.79
Sridhar Machiraju443537.08
Christos Faloutsos5279724490.38