Vi studerar problemet med att lära samhällen i närvaro av modelleringsfel och ger robusta återhämtningsalgoritmer för Stochastic Block Model (SBM). Denna modell, som också är känd som Planted Partition Model, används i stor utsträckning för community detection och graf partitionering inom olika områden, inklusive maskininlärning, statistik och samhällsvetenskap. Många algoritmer finns för att lära samhällen i Stochastic Block Model, men de fungerar inte bra i närvaro av fel. I detta dokument initierar vi studien av robusta algoritmer för partiell återställning i SBM med modellering fel eller buller. Vi betraktar grafer som genereras enligt Stochastic Block Model och sedan modifieras av en motståndare. Vi tillåter två typer av kontradiktoriska fel, Feige-Kilian eller monotonfel, och kantavvikelser. Mossel, Neeman och Sly (STOC 2015) ställde en öppen fråga om en nästan exakt återhämtning är möjlig när motståndaren tillåts lägga till o(n) kanter. Vårt arbete besvarar denna fråga positivt även när det gäller k > 2 samhällen. Vi visar sedan att våra algoritmer fungerar inte bara när instanserna kommer från SBM, men också när instanserna kommer från någon distribution av grafer som är εm nära SBM i Kullback-Leibler divergens. Detta resultat fungerar också i närvaro av kontradiktoriska fel. Slutligen presenterar vi nästan snäva nedre gränser för två samhällen.
Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. REF gav en algoritm för partiell återhämtning för den stokastiska blockmodellen med en monotona kontradiktoriska fel och ett litet antal godtyckliga fel (dvs. icke-monotonfel).
Learning Communities in the Presence of Errors