2015/12/30 by Emmanuel Abbé, Abbe, Emmanuel, Colin Sandon +1 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Social and Information Networks (cs.SI) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1512.09080
openalex publication_date 2015/12/30 · openalex created_date 2021/12/06 · openalex updated_date 2026/07/28
In a paper that initiated the modern study of the stochastic block model,\nDecelle et al., backed by Mossel et al., made the following conjecture: Denote\nby k the number of balanced communities, a/n the probability of connecting\ninside communities and b/n across, and set\n\SNR=(a-b)2/(k(a+(k-1)b); for any k \≥ 2, it is possible to\ndetect communities efficiently whenever \SNR>1 (the KS threshold),\nwhereas for k\≥ 4, it is possible to detect communities\ninformation-theoretically for some \SNR<1. Massouli 'e, Mossel et\nal. and Bordenave et al. succeeded in proving that the KS threshold is\nefficiently achievable for k=2, while Mossel et al. proved that it cannot be\ncrossed information-theoretically for k=2. The above conjecture remained open\nfor k \≥ 3.\n This paper proves this conjecture, further extending the efficient detection\nto non-symmetrical SBMs with a generalized notion of detection and KS\nthreshold. For the efficient part, a linearized acyclic belief propagation\n(ABP) algorithm is developed and proved to detect communities for any k down\nto the KS threshold in time O(n \log n). Achieving this requires showing\noptimality of ABP in the presence of cycles, a challenge for message passing\nalgorithms. The paper further connects ABP to a power iteration method with a\nnonbacktracking operator of generalized order, formalizing the interplay\nbetween message passing and spectral methods. For the information-theoretic\n(IT) part, a non-efficient algorithm sampling a typical clustering is shown to\nbreak down the KS threshold at k=4. The emerging gap is shown to be large in\nsome cases; if a=0, the KS threshold reads b gtrsim k2 whereas the IT\nbound reads b gtrsim k \ln(k), making the SBM a good study-case for\ninformation-computation gaps.\n