Inference of Network Communities using Random Walks

Community structures are very common in real-world networks. For example, social networks such as Facebook, Instagram and Twitter, biological networks such as gene co-expression networks, protein-protein interaction networks or link based networks such as Wikipedia all exhibit pronounced community structure. We propose a novel stochastic method, based on random walks, for community detection 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 after only a small fraction of nodes have been explored. This method provides robust results on large-scale networks in which the complete transition matrix is unavailable due to network size.