Även om den globala samhällsstrukturens slutsatser i nätverk nyligen har blivit ett ämne av stort intresse för fysikgemenskapen, kräver alla sådana algoritmer att grafen är fullständigt känd. Här definierar vi både ett mått på lokal samhällsstruktur och en algoritm som innehåller hierarkin av samhällen som omger en given vertex genom att utforska grafen en vertex i taget. Denna algoritm körs i tid O(k 2 d) för allmänna grafer när d är medelgraden och k är antalet hörn som ska utforskas. För grafer där utforska en ny vertex är tidskrävande, är körtiden linjär, O(k). Vi visar att på datorgenererade grafer jämförs denna teknik gynnsamt med algoritmer som kräver global kunskap. Vi använder också denna algoritm för att extrahera meningsfull lokal klusterinformation i det stora rekommenderade nätverket av en online återförsäljare och visa förekomsten av mesoskopisk struktur.
REF har definierat ett mått på lokala samhällsstrukturer och en algoritm som leder till hierarkin av samhällen genom att bifoga en given vertex genom att utforska grafen åt gången.
Finding local community structure in networks.
{'venue': 'Physical review. E, Statistical, nonlinear, and soft matter physics', 'journal': 'Physical review. E, Statistical, nonlinear, and soft matter physics', 'mag_field_of_study': ['Mathematics', 'Physics', 'Medicine']}