Critical-SNR conjecture for the 2-WSBM

About 7 years old · traced to

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(log⁡N)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=2k−1.\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.

References

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.