Spektrala algoritmer är klassiska metoder för klusterbildning och community detektion i nätverk. Men för glesa nätverk är standardversionerna av dessa algoritmer suboptimala, i vissa fall helt misslyckade att upptäcka samhällen även när andra algoritmer såsom trosutbredning kan göra det. Här introducerar vi en ny klass av spektralalalgoritmer baserade på en icke-backtracking gång på de riktade kanterna av grafen. Denna operatörs spektrum är mycket bättre skött än adjacensmatrisen eller andra vanliga matriser, vilket upprätthåller en stark separation mellan massegenvärden och eigenvärden som är relevanta för samhällsstrukturen även i det glesa fallet. Vi visar att vår algoritm är optimal för grafer som genereras av den stokastiska blockmodellen, att upptäcka samhällen hela vägen ner till den teoretiska gränsen. Vi visar också spektrumet av den icke-backtracking operatör för vissa verkliga nätverk, illustrerar dess fördelar jämfört med traditionella spektral kluster. Att upptäcka samhällen eller moduler är en central uppgift i studiet av sociala, biologiska och tekniska nätverk. Två av de mest populära tillvägagångssätten är statistiska slutsatser, där vi fastställer en generativ modell såsom den stokastiska blockmodellen till nätverket [1, 2], och spektralmetoder, där vi klassificerar hörn enligt eigenvectors av en matris som är associerad med nätverket såsom dess adjakensmatris eller Laplacian [3]. Både statistiska inferens- och spektralmetoder har visat sig fungera bra i nätverk som är tillräckligt täta eller när grafen är regelbunden [4] [5] [6] [7] [8]. Men för glesa nätverk med mycket varierande grad är problemet med att upptäcka samhället svårare. Det visades nyligen [9] [10] [11] att det finns en fasövergång under vilken samhällen som finns i den underliggande blockmodellen är omöjliga att upptäcka för någon algoritm. Medan standard spektral algoritmer lyckas ner till denna övergång när nätverket är tillräckligt tät, med en genomsnittlig grad som växer som en funktion av nätverksstorlek [8], i det fall den genomsnittliga graden är konstant dessa metoder misslyckas betydligt över övergången [12]. Således finns det en stor regim där statistiska slutsatser lyckas upptäcka samhällen, men där nuvarande spektralalalgoritmer misslyckas. Det förmodades i [11] att detta gap är artificiellt och att det finns en spektral algoritm som lyckas hela vägen till detekterbarhet övergången även i det glesa fallet. Här föreslår vi en algoritm baserad på en linjär operatör som skiljer sig avsevärt från adjacensmatrisen eller dess varianter: nämligen en matris som representerar en promenad på nätets riktade kanter, med bakåtspårning förbjuden. Vi ger starka bevis för att denna algoritm verkligen minskar klyftan. Det faktum att denna operatör har bättre spektralegenskaper än exempelvis den vanliga slumpmässiga gångoperatören har tidigare använts i samband med slumpmässiga matriser och slumpmässiga grafer [13] [14] [15]. I teorin om zeta funktioner grafer, är det känt som kanten adjacency operatör, eller Hashimoto matris [16]. Det har använts för att visa snabb blandning för icke-backtracking slumpmässig gång [17], och uppstår i samband med tro förökning [18, 19], särskilt för att noggrant analysera beteendet hos tro förökning för klusterproblem på regelbundna grafer [5]. Det har också använts som en funktion vektor för att klassificera grafer [20]. Men att använda denna operatör som grund för spektral klustring och community detektion verkar vara nytt. Vi visar att de resulterande spektralalalgoritmer är optimala för nätverk som genereras av den stokastiska blockmodellen, att hitta samhällen hela vägen ner till detekterbarhet övergången. Det vill säga, när som helst ovanför denna övergång finns det en klyfta mellan eigenvärden relaterade till samhällsstrukturen och den huvudsakliga fördelningen av eigenvärden som kommer från den slumpmässiga grafstrukturen, vilket gör att vi kan hitta en märkning korrelerad med de sanna samhällena. Förutom våra analysresultat på stokastiska blockmodeller illustrerar vi också fördelarna med en icke-backtracking operatör jämfört med befintliga metoder för vissa verkliga nätverk.
Krzakala m.fl. REF förmodade att en spektralmetod baserad på "icke-backtracking"-matrisen ger positiv överlappning när den överskrider tröskelvärdet.
Spectral redemption: clustering sparse networks
{'venue': 'Proceedings of the National Academy of Sciences 110, no. 52 (2013): 20935-20940', 'journal': None, 'mag_field_of_study': ['Medicine', 'Computer Science', 'Physics', 'Mathematics']}