Critical-SNR conjecture for the 2-WSBM

In the 2-WSBM, let NN be the number of vertices, kk the community size, and let γ\gamma denote the signal-to-noise ratio; assume k=o(logN)k=o(\log N). For k=2k=2, the model is equivalent to the 1-P-REM with M=(N2)N2M=\binom{N}{2}\approx N^2 states, yielding the benchmark γc=2\gamma_c=\sqrt{2}. Critical-SNR conjecture. The critical signal-to-noise ratio for the 2-WSBM is

γc=2k1.\gamma_c=\sqrt{\frac{2}{k-1}}.

The conjecture extends the exactly identified k=2k=2 case to communities of size sublogarithmic in NN and predicts the recoverability threshold in this regime. Its proof is left for future work.

Sources & referencesView supporting material

Primary source

Luca Corinzia, Paolo Penna, Luca Mondada and Joachim M. Buhmann, “Exact Recovery for a Family of Community-Detection Generative Models”, arXiv:1901.06799 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.