Efficient discovery of overlapping communities in massive networks
Open Access
- 15 August 2013
- journal article
- research article
- Published by Proceedings of the National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 110 (36), 14534-14539
- https://doi.org/10.1073/pnas.1221839110
Abstract
Detecting overlapping communities is essential to analyzing and exploring natural networks such as social networks, biological networks, and citation networks. However, most existing approaches do not scale to the size of networks that we regularly observe in the real world. In this paper, we develop a scalable approach to community detection that discovers overlapping communities in massive real-world networks. Our approach is based on a Bayesian model of networks that allows nodes to participate in multiple communities, and a corresponding algorithm that naturally interleaves subsampling from the network and updating an estimate of its communities. We demonstrate how we can discover the hidden community structure of several real-world networks, including 3.7 million US patents, 575,000 physics articles from the arXiv preprint server, and 875,000 connected Web pages from the Internet. Furthermore, we demonstrate on large simulated networks that our algorithm accurately discovers the true community structure. This paper opens the door to using sophisticated statistical models to analyze massive networks.Keywords
This publication has 41 references indexed in Scilit:
- Robust Detection of Hierarchical Communities from Escherichia coli Gene Expression DataPLoS Computational Biology, 2012
- Finding Statistically Significant Communities in NetworksPLOS ONE, 2011
- Link communities reveal multiscale complexity in networksNature, 2010
- Mixture models and exploratory analysis in networksProceedings of the National Academy of Sciences, 2007
- Clique Percolation in Random NetworksPhysical Review Letters, 2005
- Finding community structure in very large networksPhysical Review E, 2004
- Latent Space Approaches to Social Network AnalysisJournal of the American Statistical Association, 2002
- Stochastic Blockmodels for Directed GraphsJournal of the American Statistical Association, 1987
- A Stochastic Approximation MethodThe Annals of Mathematical Statistics, 1951
- On Information and SufficiencyThe Annals of Mathematical Statistics, 1951