Abstrakt. Den stokastiska blockmodellen är en naturlig modell för att studera community detektering i slumpmässiga nätverk. Dess klusteregenskaper har studerats ingående i statistik, fysik och datavetenskap. Nyligen har detta område upplevt stora matematiska genombrott, särskilt för den binära (två-community) versionen, se [26, 27, 21]. I detta papper introducerar vi en variant av den binära modellen som vi kallar den vanliga stokastiska blockmodellen (RSBM). Vi visar stelhet genom att visa att med stor sannolikhet en exakt återhämtning av samhällsstrukturen är möjlig. Spektrala metoder uppvisar en regim där detta kan göras effektivt. Dessutom bevisar vi också att varje lämplig god partiell återhämtning i detta sammanhang kan fångas upp av boots för att uppnå en fullständig återhämtning av samhällena. Den stokastiska blockmodellen (SBM) är en klassisk slumpmässig grafmodell som har studerats ingående, både empiriskt och rigoröst, över många fält. SBM är i sin enklaste form en modell av slumpmässiga grafer på 2n noder med två lika stora kluster A och B så att  och B = n och A B = ∅. Kanter mellan olika par hörn visas oberoende med sannolikhet p = p n om de två hörnen tillhör samma kluster och med sannolikhet q = q n annars. Således, för alla vertex, det förväntade antalet av samma klass grannar är a := a n := p(n − 1) pn, och det förväntade antalet överklass grannar är b := b n := qn. Med tanke på ett förverkligande av grafen, är det breda målet att avgöra om det är möjligt (med hög sannolikhet) att hitta partitionen A, B; och om svaret är ja, om det är möjligt att göra det med hjälp av en effektiv algoritm. Annars, det bästa man kan hoppas på är förekomsten av en algoritm som kommer att producera en partition som är mycket (eller åtminstone positivt) korrelerad med den underliggande kluster. För detta ändamål, överväga utrymmet M av alla algoritmer som tar som inmatning en ändlig graf på 2n hörn och utdata en partition av vertex inställd i två uppsättningar. Informellt säger vi att en algoritm i M gör det möjligt för svag återhämtning om, med sannolikhet att gå till 1 som n går till oändlighet, det utdata en partition (A, B ) sådan att  till A till A +  på B till B = o(n) (här  påvisar den symmetriska skillnaden). Vi säger att en algoritm möjliggör stark återhämtning om, med sannolikhet att gå till 1 som n går till oändlighet, det ger partitionen (A, B). Slutligen, en algoritm i M kommer att kallas effektiv om dess körtid är polynom i n. Problemet med gemenskap upptäckt beskrivs ovan är nära relaterad till min-bisektion problem, där man letar efter en partition av vertex uppsättning av en given graf i två undergrupper av lika storlek så att antalet kanter över undergrupper är minimal. I allmänhet är detta problem känt för att vara NP-hård [12]; dock, om min-bisektion är mindre än de flesta av de andra bisektionerna, problemet är känd för att vara enklare. Detta märktes för några årtionden sedan, med införandet av studien av minbisektion i samband med SBM. I synnerhet, Dyer och Frieze [9] producerade ett av de tidigaste resultaten när de visade att om p > q är fast som n → ∞ då min-bisektion är den som skiljer de två klasserna, och det kan hittas i förväntad O(n 3 ) tid. Resultaten förbättrades av Jerrum och Sorkin [16] samt Condon och Karp [7]. Var och en av dessa papper var 1 arXiv:1507.00930v3 [math.PR]
I synnerhet Brito et al. REF visar att stark återuppbyggnad är möjlig i polynom-tid
Recovery and Rigidity in a Regular Stochastic Block Model
{'venue': 'SODA 2016', 'journal': 'arXiv: Probability', 'mag_field_of_study': ['Computer Science', 'Mathematics']}