The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
Open accessAbstract
In this paper we extend our previous work on the stochastic block model, a commonly used generative model for social and biological networks, and the problem of inferring functional groups or communities from the topology of the network. We use the cavity method of statistical physics to obtain an asymptotically exact analysis of the phase diagram. We describe in detail properties of the detectability-undetectability phase transition and the easy-hard phase transition for the community detection problem. Our analysis translates naturally into a belief propagation algorithm for inferring the group memberships of the nodes in an optimal way, i.e., that maximizes the overlap with the underlying group memberships, and learning the underlying parameters of the block model. Finally, we apply the algorithm to two examples of real-world networks and discuss its performance.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Maximum Likelihood from Incomplete Data Via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444
Finding 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
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Erdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
An 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
Maximum likelihood estimation from incomplete data via the EM algorithm
Dempster, A. P. (1977) · Journal of the Royal Statistical Society Series A (Statistics in Society) · Cited by 4,543
Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications
Mezard, M., Parisi, G., & Virasoro, M. (1986) · World Scientific Lecture Notes in Physics · doi:10.1142/0271 · Cited by 3,653
Benchmark 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
The Nature of the Glassy State and the Behavior of Liquids at Low Temperatures.
Kauzmann, W. (1948) · Chemical Reviews · doi:10.1021/cr60135a002 · Cited by 2,834
Mezard, M., Parisi, G., Virasoro, M. A., & Thouless, D. J. (1988) · Physics Today · doi:10.1063/1.2811676 · Cited by 2,682
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
Self-citationStability of the Sherrington-Kirkpatrick solution of a spin glass model
Almeida, J. R. L. D., & Thouless, D. J. (1978) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/11/5/028 · Cited by 2,061
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
Information, Physics, and Computation
Mézard, M., & Montanari, A. (2009) · doi:10.1093/acprof:oso/9780198570837.001.0001 · Cited by 1,913
Community detection in complex networks using extremal optimization
Duch, J., & Arenas, A. (2005) · Physical Review E · doi:10.1103/physreve.72.027104 · Cited by 1,549
Statistical Physics of Spin Glasses and Information Processing: An Introduction
Nishimori, H. (2001) · doi:10.1093/acprof:oso/9780198509417.001.0001 · Cited by 1,182
Estimation and Prediction for Stochastic Blockstructures
Nowicki, K., & Snijders, T. A. B. (2001) · Journal of the American Statistical Association · doi:10.1198/016214501753208735 · Cited by 1,148
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
The Bethe lattice spin glass revisited
Mézard, M., & Parisi, G. (2001) · The European Physical Journal B · doi:10.1007/pl00011099 · Cited by 818
Missing and spurious interactions and the reconstruction of complex networks
Guimerà, R., & Sales-Pardo, M. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0908366106 · Cited by 797
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
Statistical physics of spin glasses and information processing : an introduction
Nishimori, H. (2001) · Cited by 617
Mixture models and exploratory analysis in networks
Newman, M. E. J., & Leicht, E. A. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0610537104 · Cited by 554
Gibbs states and the set of solutions of random constraint satisfaction problems
Krz̧akała, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G., & Zdeborová, L. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0703685104 · Cited by 546
Self-citationExploring artificial intelligence in the new millennium
Lakemeyer, G. (2003) · Cited by 480
Algorithms for graph partitioning on the planted partition model
Condon, A., & Karp, R. M. (2001) · Random Structures and Algorithms · doi:10.1002/1098-2418(200103)18:2<116::aid-rsa1001>3.0.co;2-2 · Cited by 429
Inference and Phase Transitions in the Detection of Modules in Sparse Networks
Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011) · Physical Review Letters · doi:10.1103/physrevlett.107.065701 · Cited by 392
Self-citationEfficient and principled method for detecting communities in networks
Ball, B., Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.84.036103 · Cited by 386
Phase transitions in the coloring of random graphs
Zdeborová, L., & Krząkała, F. (2007) · Physical Review E · doi:10.1103/physreve.76.031131 · Cited by 306
Self-citationBayesian Approach to Network Modularity
Hofman, J. M., & Wiggins, C. H. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.258701 · Cited by 298
Community detection as an inference problem
Hastings, M. B. (2006) · Physical Review E · doi:10.1103/physreve.74.035102 · Cited by 213
The solution of some random NP-hard problems in polynomial expected time
Dyer, M., & FRIEZE, A. M. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90001-1 · Cited by 189
The Nishimori line and Bayesian statistics
Iba, Y. (1999) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/32/21/302 · Cited by 171
Statistical-mechanical approach to image processing
Tanaka, K. (2002) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/35/37/201 · Cited by 162
A ferromagnet with a glass transition
Franz, S., Mézard, M., Ricci‐Tersenghi, F., Weigt, M., & Zecchina, R. (2001) · Europhysics Letters (EPL) · doi:10.1209/epl/i2001-00438-4 · Cited by 129
Generalization of the cavity method for adiabatic evolution of Gibbs states
Zdeborová, L., & Krząkała, F. (2010) · Physical Review B · doi:10.1103/physrevb.81.224205 · Cited by 78
Self-citation(Un)detectable Cluster Structure in Sparse Networks
Reichardt, J., & Leone, M. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.078701 · Cited by 74
The Nishimori line and Bayesian StatisticsPreprint
Iba, Y. (n.d.) · Cited by 71
Estimating random variables from random sparse observations
Andrea Montanari, A. (2008) · European Transactions on Telecommunications · doi:10.1002/ett.1289 · Cited by 60
Belief propagation for graph partitioning
Šulc, P., & Zdeborová, L. (2010) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/43/28/285003 · Cited by 21
Self-citation
Cited by
Machine learning and the physical sciences
Carleo, G., Cirac, I., Cranmer, K., Daudet, L., Schuld, M., Tishby, N., Vogt-Maranto, L., & Zdeborová, L. (2019) · Reviews of Modern Physics · doi:10.1103/revmodphys.91.045002 · Cited by 2,417
Self-citationNewman, M. (2018) · doi:10.1093/oso/9780198805090.001.0001 · Cited by 2,297
Spectral redemption in clustering sparse networks
Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L., & Zhang, P. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1312486110 · Cited by 638
Self-citationCommunity Detection and Stochastic Block Models
Abbe, E. (2018) · now publishers, Inc. eBooks · doi:10.1561/9781680834772 · Cited by 544
Statistical physics of inference: thresholds and algorithms
Zdeborová, L., & Krzakala, F. (2016) · Advances in Physics · doi:10.1080/00018732.2016.1211393 · Cited by 440
Self-citation
Metadata
- Authors
- Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2011-12-12
- Volume
- 84
- Issue
- 6
- Pages
- 066106-066106
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W2004531067
- Cited by
- 747
- References
- 42
- FWCI
- 17.18
- 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.