Network community detection and clustering with random walks

Abstract

We present an approach to partitioning network nodes into nonoverlapping communities, a key step in revealing network modularity and functional organization. Our methodology, applicable to networks with weighted or unweighted symmetric edges, uses random walks to explore neighboring nodes in the same community. The walk-likelihood algorithm (WLA) produces an optimal partition of network nodes into a given number of communities. The walk-likelihood community finder employs WLA to predict both the optimal number of communities and the corresponding network partition. We have extensively benchmarked both algorithms, finding that they outperform or match other methods in terms of the modularity of predicted partitions and the number of links between communities. Making use of the computational efficiency of our approach, we investigated a large-scale map of roads and intersections in the state of Colorado. Our clustering yielded geographically sensible boundaries between neighboring communities.