Computing Communities in Large Networks Using Random Walks

作者：Pascal Pons, Matthieu Latapy · 发表于：Journal of Graph Algorithms and Applications · 年份：2006 · DOI：10.7155/jgaa.00124 · 被引用次数：1535 · 研究领域：Complex Network Analysis Techniques、Peer-to-Peer Network Technologies、Data Management and Algorithms

Abstract. Dense subgraphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Computing them however is generally expensive. We propose here a measure of similarities between vertices based on random walks which has several important advantages: it captures well the community structure in a network, it can be computed efficiently, it works at various scales, and it can be used in an agglomerative algorithm to compute efficiently the community structure of a network. We propose such an algorithm which runs in time O(mn 2)andspaceO(n 2)inthe worst case, and in time O(n 2 log n) andspaceO(n 2)inmostreal-world cases (n and m are respectively the number of vertices and edges in the input graph). 1