Overlapping Communities Detection via Measure Space Embedding

Abstract

We present a new algorithm for community detection. The algorithm uses random walks to embed the graph in a space of measures, after which a modification of $k$-means in that space is applied. The algorithm is therefore fast and easily parallelizable. We evaluate the algorithm on standard random graph benchmarks, including some overlapping community benchmarks, and find its performance to be better or at least as good as previously known algorithms. We also prove a linear time (in number of edges) guarantee for the algorithm on a $p,q$-stochastic block model with $p\ge c\cdot N^{-\frac{1}{2}+\epsilon }$ and $p-q\ge c^{\prime }\sqrt{p{N}^{-\frac{1}{2}+\epsilon }\log N}$.

References in corpus (10)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Mixture models and exploratory analysis in networks
• An efficient and principled method for detecting communities in networks