Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00124
Computing Communities in Large Networks Using Random Walks
Vol. 10, no. 2, pp. 191-218, 2006. Regular paper.
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 similarity 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, and it can be used in an agglomerative algorithm to
compute efficiently the community structure of a network. We
propose such an algorithm, called Walktrap, which runs in
time O(mn2) and space O(n2) in the worst case, and in time
O(n2logn) and space O(n2) in most real-world cases (n
and m are respectively the number of vertices and edges in the
input graph). Extensive comparison tests show that our algorithm
surpasses previously proposed ones concerning the quality of the
obtained community structures and that it stands among the best
ones concerning the running time.
|
Journal Supporters
|