English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In a paper that initiated the modern study of the stochastic block model,Decelle et al., backed by Mossel et al., made the following conjecture: Denoteby $k$ the number of balanced communities, $a/n$ the probability of connectinginside communities and $b/n$ across, and set$\mathrm{SNR}=(a-b)^2/(k(a+(k-1)b)$; for any $k \geq 2$, it is possible todetect communities efficiently whenever $\mathrm{SNR}>1$ (the KS threshold),whereas for $k\geq 4$, it is possible to detect communitiesinformation-theoretically for some $\mathrm{SNR}<1$. Massouli\'e, Mossel etal.\ and Bordenave et al.\ succeeded in proving that the KS threshold isefficiently achievable for $k=2$, while Mossel et al.\ proved that it cannot becrossed information-theoretically for $k=2$. The above conjecture remained openfor $k \geq 3$.  This paper proves this conjecture, further extending the efficient detectionto non-symmetrical SBMs with a generalized notion of detection and KSthreshold. For the efficient part, a linearized acyclic belief propagation(ABP) algorithm is developed and proved to detect communities for any $k$ downto the KS threshold in time $O(n \log n)$. Achieving this requires showingoptimality of ABP in the presence of cycles, a challenge for message passingalgorithms. The paper further connects ABP to a power iteration method with anonbacktracking operator of generalized order, formalizing the interplaybetween message passing and spectral methods. For the information-theoretic(IT) part, a non-efficient algorithm sampling a typical clustering is shown tobreak down the KS threshold at $k=4$. The emerging gap is shown to be large insome cases; if $a=0$, the KS threshold reads $b \gtrsim k^2$ whereas the ITbound reads $b \gtrsim k \ln(k)$, making the SBM a good study-case forinformation-computation gaps.

Detection in the stochastic block model with multiple clusters: proof of  the achievability conjectures, acyclic BP, and the information-computation  gap