Abstract-Den stokastiska blockmodellen med två samhällen, eller motsvarande planterade bisektionsmodellen, är en populär modell av slumpmässig graf som uppvisar ett kluster beteende. I det symmetriska fallet har grafen två lika stora kluster och hörn ansluter med sannolikhet p inom kluster och q över kluster. Under de senaste två decennierna har en stor mängd litteratur inom statistik och datavetenskap fokuserat på att ge lägre gränser för skalning av  på p − q på att säkerställa exakt återhämtning. I detta dokument identifierar vi ett skarpt tröskelfenomen för exakt återhämtning: om α = pn/ log(n) och β = qn/ log(n) är konstant (med α > β), är det möjligt att återställa samhällen med hög sannolikhet om (α + β/2) − αβ > 1 och är omöjligt om (α + β/2) − αβ < 1. Detta förbättrar i synnerhet de befintliga gränserna. Detta ger också en ny synlinje för effektiva klusteralgoritmer. Även om maximal sannolikhet (ML) uppnår den optimala tröskeln (per definition), är det i värsta fall NP-hård. I detta dokument föreslås en effektiv algoritm baserad på en semidefinit programmeringsuppmjukning av ML, som har visat sig lyckas återställa samhällen nära tröskeln, medan numeriska experiment tyder på att den kan uppnå tröskeln. En effektiv algoritm som lyckas hela vägen ner till tröskeln erhålls också med hjälp av en partiell återställningsalgoritm i kombination med ett lokalt förbättringsförfarande.
Ett skarpt tröskelvärde för exakt återvinning erhölls i REF MNS14a, vilket visar att för p = α log(n)/n, q n = β log(n)/n, α, β > 0, är exakt återvinning möjlig (och effektivt så) om och endast om ε α − β ≥ 2.
Exact Recovery in the Stochastic Block Model
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}