Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

By Aurelien Decelle, Florent Krzakala, Cristopher Moore, Lenka Zdeborov'a. Physical review. E, Statistical, nonlinear, and soft matter physics, 2011

796 citations recorded by the source corpus.

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.

Subfields: Mathematical Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/d6df29390c678eff7f03a28bfd2c85bbf6a16d07

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Compressive Spectral Clustering (2016, background): “[41] show that a critical value c exists above which community detection is impossible at the large N limit: c = (s− √ s)/(s+ √ s(k − 1)).”
Community detection thresholds and the weak Ramanujan property (2013, background): “[1] conjectured the existence of a phase transition in the sparse regime where the graph’s average degree is O(1).”
Machine learning and the physical sciences (2019, background): “However, the exact solution and understanding of algorithmic limitations in the stochastic block model came from the spin glass theory in (Decelle et al., 2011a,b).”
Hierarchical block structures and high-resolution model selection in large networks (2013, methodology): “…any speciﬁc level l of the hierarchical structure is a regular block model, and, hence, the clas-siﬁcation of the B l 1 nodes of this level into B l blocks can be done via well-established methods, such as the Monte Carlo method [32, 40], simulated annealing, or belief propagation [29, 30, 56].”
Supervised Community Detection with Line Graph Neural Networks (2017, methodology): “The situation is different for k > 4, where it is conjectured that a gap emerges between the theoretical performance of MLE estimators and the performance of any polynomial-time estimation procedure (Decelle et al., 2011).”
Does robustness imply tractability? A lower bound for planted clique in the semi-random model (2017, background): “5 is the Kesten-Stigum threshold (Kesten and Stigum, 1966b;a), which is believed to be the threshold for efficient recoverability in the stochastic block model (Decelle et al., 2011).”
Spectral redemption in clustering sparse networks (2013, methodology): “This linearization was used previously to investigate phase transitions in the performance of the BP algorithm [5, 9, 10, 24].”
Pseudo-likelihood methods for community detection in large sparse networks (2012, methodology): “The parameter τ 2 n controlling consistency is the same as the one reported in [14] and [24].”
Consistency of spectral clustering in stochastic block models (2013, methodology): “…Choi et al., 2012; Zhao et al., 2012; Amini et al., 2012; Celisse et al., 2012), method of moments (Anandkumar et al., 2013), belief propagation (Decelle et al., 2011), convex optimization (Chen et al., 2012), spectral clustering (Rohe et al., 2011; Balakrishnan et al., 2011; Jin, 2012;…”
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers (2017, background): “a log(2/α) α3 , and remark on the similarity to the famous Kesten-Stigum threshold (a−b) 2 a 1 α2 , which is the conjectured threshold for computationally efficient recovery in the classical stochastic block model (see Decelle et al. (2011) for the conjecture, and Mossel et al. (2013); Massoulié (20”
Community Detection with Graph Neural Networks (2017, background): “This amounts to solving a graph coloring problem in a sparse regime, which falls above the IT threshold but below the regime where BP is able to detect (Decelle et al., 2011), asymptotically as n → ∞ .”
Scalable detection of statistically significant communities and hierarchies, using message passing for modularity (2014, background): “Using [5], we find that ∂ψ i→k t =∂ψ j→i s = Tst , where Tst is the q×q matrix”
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery (2015, background): “A gap is conjectured to take place for weak recovery for more than 4 communities [36].”
Mean-field theory of graph neural networks in graph partitioning (2018, methodology): “(2) becomes exactly the update equation of the BP algorithm4 [13].”