The DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
Efficient and principled method for detecting communities in networks
Open accessAbstract
A fundamental problem in the analysis of network data is the detection of network communities, groups of densely interconnected nodes, which may be overlapping or disjoint. Here we describe a method for finding overlapping communities based on a principled statistical approach using generative network models. We show how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasonable running times. We test the method both on real-world networks and on synthetic benchmarks and find that it gives results competitive with previous methods. We also show that the same approach can be used to extract nonoverlapping community divisions via a relaxation method, and demonstrate that the algorithm is competitively fast and accurate for the nonoverlapping problem.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A new look at the statistical model identification
Akaike, H. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100705 · Cited by 51,879
Estimating the Dimension of a Model
Schwarz, G. (1978) · The Annals of Statistics · doi:10.1214/aos/1176344136 · Cited by 47,033
(2003) · Journal of Machine Learning Research · doi:10.5555/944919.944937 · Cited by 32,337
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502
Self-citationFinding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931
Self-citationLearning the parts of objects by non-negative matrix factorization
Lee, D. D., & Seung, H. S. (1999) · Nature · doi:10.1038/44565 · Cited by 13,868
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · cited 2×
“A fundamental problem in the theory of networks, and one that has attracted substantial interest among researchers in the last decade, is how to detect such communities in empirical network data [2, 3].”
BackgroundUncovering the overlapping community structure of complex networks in nature and society
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005) · Nature · doi:10.1038/nature03607 · Cited by 5,373 · cited 1×
“Early efforts at community detection, going back to the 1970s, assumed nonoverlapping or disjoint communities [1, 4, 5], but as many researchers have argued in the last few years, it is common in practical situations for communities to overlap [6].”
BackgroundAn Efficient Heuristic Procedure for Partitioning Graphs
Kernighan, B. W., & Lin, S. (1970) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1970.tb01770.x · Cited by 5,305
Finding community structure in networks using the eigenvectors of matrices
Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.74.036104 · Cited by 4,761
Self-citationAn Information Flow Model for Conflict and Fission in Small Groups
Zachary, W. W. (1977) · Journal of Anthropological Research · doi:10.1086/jar.33.4.3629752 · Cited by 4,704
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2001) · Physical Review E · doi:10.1103/physreve.64.026118 · Cited by 3,648
Self-citationBenchmark graphs for testing community detection algorithms
Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008) · Physical Review E · doi:10.1103/physreve.78.046110 · Cited by 3,051
Resolution limit in community detection
Fortunato, S., & Barthélemy, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0605965104 · Cited by 3,024
Comparing community structure identification
Danon, L., Díaz-Guilera, A., Duch, J., & Arenas, A. (2005) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2005/09/p09008 · Cited by 2,872
Stochastic blockmodels: First steps
Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983) · Social Networks · doi:10.1016/0378-8733(83)90021-7 · Cited by 2,755
Barthélemy, M. (2011) · Physics Reports · doi:10.1016/j.physrep.2010.11.002 · Cited by 2,469
Unsupervised Learning by Probabilistic Latent Semantic Analysis
Hofmann, T. (2001) · Machine Learning · doi:10.1023/a:1007617005950 · Cited by 2,456
A critical point for random graphs with a given degree sequence
Molloy, M., & Reed, B. (1995) · Random Structures & Algorithms · doi:10.1002/rsa.3240060204 · Cited by 2,351
Community detection algorithms: A comparative analysis
Lancichinetti, A., & Fortunato, S. (2009) · Physical Review E · doi:10.1103/physreve.80.056117 · Cited by 2,177
Hierarchical structure and the prediction of missing links in networks
Clauset, A., Moore, C., & Newman, M. E. J. (2008) · Nature · doi:10.1038/nature06830 · Cited by 2,171 · cited 1×
“This approach, which applies methods of statistical inference to networks, has been explored by a number of authors for the nonover-lapping case, including some work that goes back several decades [4–7].”
MethodSelf-citationThe dynamics of viral marketing
Leskovec, J., Adamic, L. A., & Huberman, B. A. (2007) · ACM Transactions on the Web · doi:10.1145/1232722.1232727 · Cited by 2,032
Stochastic blockmodels and community structure in networks
Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.83.016107 · Cited by 2,025
Self-citationLink communities reveal multiscale complexity in networks
Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010) · Nature · doi:10.1038/nature09182 · Cited by 1,949
Latent semantic models for collaborative filtering
Hofmann, T. (2004) · ACM Transactions on Information Systems · doi:10.1145/963770.963774 · Cited by 1,378
Performance of modularity maximization in practical contexts
Good, B. H., de Montjoye, Y.-A., & Clauset, A. (2010) · Physical Review E · doi:10.1103/physreve.81.046106 · Cited by 937
Stanford GraphBase: A Platform for Combinatorial Computing, The
Knuth, D. E. (1993) · Cited by 927
From the Cover: The structure of scientific collaboration networks
Newman, M. E. J. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.021544898 · Cited by 837
Self-citationBreiger, R. L., Boorman, S. A., & Arabie, P. (1975) · Journal of Mathematical Psychology · doi:10.1016/0022-2496(75)90028-0 · Cited by 820
Mixed membership stochastic blockmodels
Airoldi, E. M., Blei, D. M., Fienberg, S. E., & Xing, E. P. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0705.4485 · Cited by 781
A nonparametric view of network models and Newman–Girvan and other modularities
Bickel, P. J., & Chen, A. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0907096106 · Cited by 765
Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure
Snijders, T. A. B., & Nowicki, K. (1997) · Journal of Classification · doi:10.1007/s003579900004 · Cited by 653
Line graphs, link partitions, and overlapping communities
Evans, T. S., & Lambiotte, R. (2009) · Physical Review E · doi:10.1103/physreve.80.016105 · Cited by 615
Stochastic blockmodels for directed graphs.
Wang, Y. J., & Wong, G. Y. (1987) · Journal of the American Statistical Association · doi:10.1080/01621459.1987.10478385 · Cited by 480
The spatial structure of networks
Gastner, M. T., & Newman, M. E. J. (2006) · The European Physical Journal B - Condensed Matter and Complex Systems · doi:10.1140/epjb/e2006-00046-8 · Cited by 475
Self-citationCommunity discovery using nonnegative matrix factorization
Wang, F., Li, T., Wang, X., Zhu, S., & Ding, C. (2011) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0181-y · Cited by 446
Overlapping community detection using Bayesian non-negative matrix factorization
Psorakis, I., Roberts, S., Ebden, M., & Sheldon, B. (2011) · Physical Review E · doi:10.1103/physreve.83.066114 · Cited by 399
Ding, C., Li, T., & Peng, W. (2008) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2008.01.011 · Cited by 274
Evaluating local community methods in networks
Bagrow, J. P. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/05/p05001 · Cited by 198
Modularity optimization in community detection of complex networks
Zhang, X., Wang, R., Wang, Y., Wang, J., Qiu, Y., Wang, L., & Chen, L. (2009) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/87/38002 · Cited by 107
Detecting overlapping community structure of networks based on vertex–vertex correlations
Zarei, M., Izadi, D., & Samani, K. A. (2009) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2009/11/p11013 · Cited by 36
Cited by
Newman, M. (2018) · doi:10.1093/oso/9780198805090.001.0001 · Cited by 2,297
Self-citationCommunity detection in networks: a user guide
Fortunato, S., & Hric, D. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.09.002 · Cited by 2,086
Networks beyond pairwise interactions: Structure and dynamics
Battiston, F., Cencetti, G., Iacopini, I., Latora, V., Lucas, M., Patania, A., Young, J.-G., & Petri, G. (2020) · Physics Reports · doi:10.1016/j.physrep.2020.05.004 · Cited by 1,602
Overlapping community detection in networks: The state-of-the-art and comparative study
Xie, J., Kelley, S., & Szymanski, B. K. (2013) · ACM Computing Surveys · doi:10.1145/2501654.2501657 · Cited by 930
Overlapping Community Detection in Networks: the State of the Art and Comparative Study
Xie, J., Kelley, S., & Szymanski, B. K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1110.5813 · Cited by 865
Metadata
- Authors
- Ball, B., Karrer, B., & Newman, M. E. J.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2011-09-08
- Volume
- 84
- Issue
- 3
- Pages
- 036103-036103
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W1972675431
- Cited by
- 386
- References
- 41
- FWCI
- 24.15
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.