Exploring Network Communities with Random Walks

Communities within a network are sets of nodes such that the nodes within each set are connected more densely internally than with nodes outside the set. Community structures are very common in real-world networks such as social or biological networks. Detecting community structures is equivalent to clustering which is of interest in many areas of science. We propose a computationally efficient method, based on random walks, for community detection and clustering on undirected networks with weighted or unweighted edges. The method employs first-passage properties of random walks on networks, providing key statistics of network community structure such as the number of communities and the size of each community. Our method provides a complete hierarchy of clusters which is determined by the strengths of connections between them. Surprisingly, some of the key statistics can be obtained after exploring only a small fraction of nodes which is relevant to very large real-world networks. We have used this method to cluster biological networks such as gene co-expression networks as well as for finding community statistics of large real-world networks such as wikipedia.