Täta subgrafer av glesa grafer (kommuner), som förekommer i de flesta komplexa nätverk i verkligheten, spelar en viktig roll i många sammanhang. Att beräkna dem är dock i allmänhet dyrt. Vi föreslår här ett mått av likhet mellan hörn baserade på slumpmässiga promenader som har flera viktiga fördelar: det fångar väl gemenskapens struktur i ett nätverk, det kan beräknas effektivt, och det kan användas i en agglomerativ algoritm för att beräkna effektivt gemenskapens struktur av ett nätverk. Vi föreslår en sådan algoritm, kallad Walktrap, som löper i tiden O(mn 2 ) och utrymme O(n 2 ) i värsta fall, och med tiden O(n 2 log n) och utrymme O(n 2 ) i de flesta verkliga fall (n och m är respektive antalet hörn och kanter i inmatningskurvan). Omfattande jämförelsetester visar att vår algoritm överträffar tidigare föreslagna om kvaliteten på de erhållna samhällsstrukturerna och att den står bland de bästa när det gäller körtiden.
Pons och Latapy REF införde ett mått på likhet mellan noder baserade på slumpmässiga promenader.
Computing Communities in Large Networks Using Random Walks
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}