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.
Men komplexiteten i det mest effektiva slumpmässiga arbetssättet hittills är Oðn 2 Á log n på ett nätverk med n hörn REF.
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']}