Det nuvarande arbetet handlar om att upptäcka samhället. Specifikt, Vi anser att en slumpmässig graf dras enligt den stokastiska blockmodellen: dess vertex uppsättning är uppdelad i block, eller samhällen, och kanter placeras slumpmässigt och oberoende av varandra med sannolikhet beroende endast på samhällen av deras två endpoints. I detta sammanhang är vårt mål att återställa gemenskapsetiketterna bättre än genom slumpmässiga gissningar, baserat endast på observationen av grafen. I det glesa fallet, där kanten sannolikheter är i O(1/n), introducerar vi en ny spektral metod baserad på avståndsmatrisen D (l), där D (l) ij = 1 iff grafavståndet mellan i och j, noterade d(i, j) är lika med l. Vi visar att när l  på c log(n) för noggrant utvalda c, de eigenvectors associerade till de största eigenvärden av D (l) ge tillräckligt med information för att utföra icke-trivial gemenskap återhämtning med hög sannolikhet, förutsatt att vi är över den så kallade Kesten-Stigum tröskeln. Detta ger en effektiv algoritm för community detektion, eftersom beräkning av matrisen D (l) kan göras i O (n 1 + ) operationer för en liten konstant σ. Vi studerar sedan känsligheten hos Eigendecomposition av D (l) när vi tillåter en kontraarial perturbation av kanterna på G. Vi visar att när den ansedda perturbation inte påverkar mer än O (n ε ) hörn för några små ε > 0, de högsta eigenvärden och deras motsvarande eigenvectors har försumbara perturbationer, vilket gör att vi fortfarande utföra effektiv återhämtning.
L. Stephan m.fl. REF-studie ett slumpmässigt diagram ritat problem med den stokastiska blockmodellen som noderna är uppdelade i samhällen och kantade placeras slumpmässigt och oberoende av varandra.
D S ] 1 4 N ov 2 01 8 Robustness of spectral methods for community detection