EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs

PDF: http://www.cs.cmu.edu/~badityap/papers/eigenspokes-pakdd10.pdf

通話記録からのソーシャルグラフのパターン検知

EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs

We report a surprising, persistent pattern in large sparse social graphs, which we term EigenSpokes. We focus on large Mobile Call graphs, spanning about 186K nodes and millions of calls, 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”). Furthermore, analysis of several other real-world datasets e.g., Patent Citations, Internet, etc. reveals similar phenomena indicating this to be a more fundamental attribute of large sparse graphs that is related to their community structure. This is the first contribution of this paper. Additional ones include (a) study of the conditions that lead to such EigenSpokes, and (b) a fast algorithm for spotting and extracting tightly-knit communities, called
SpokEn, that exploits our findings about the EigenSpokes pattern