Computing Communities in Large Networks Using Random Walks - Pons, Pascal; Latapy, Matthieu (Journal of Graph Algorithms and Applications, 2006)
Dense subgraphs of sparse graphs (communities), whichappear in most real-world complex networks, play an important rolein many contexts. Computing them however is generally expensive.We propose here a measure of similarity between vertices based onrandom walks which has several important advantages: it captureswell the community structure in a network, it can be computedefficiently, and it can be used in an agglomerative algorithm tocompute efficiently the community structure of a network. Wepropose such an algorithm, called Walktrap, which runs intime O(mn2) and space O(n2) in the worst case, and in timeO(n2logn) and space O(n2) in most real-world cases (nand m are respectively the number of vertices and edges in theinput graph). Extensive comparison tests show that our algorithmsurpasses previously proposed ones concerning the quality of theobtained community structures and that it stands among the bestones concerning the running time. <!---->