Att upptäcka överlappande samhällen är viktigt för att analysera och utforska naturliga nätverk som sociala nätverk, biologiska nätverk och citeringsnätverk. De flesta befintliga metoder är emellertid inte lika stora som de nätverk som vi regelbundet observerar i den verkliga världen. I detta dokument utvecklar vi en skalbar strategi för att upptäcka gemenskaper som upptäcker överlappande samhällen i massiva realworld-nätverk. Vår strategi är baserad på en Bayesian modell av nätverk som tillåter noder att delta i flera samhällen, och en motsvarande algoritm som naturligt intersampling från nätverket och uppdatera en uppskattning av dess samhällen. Vi visar hur vi kan upptäcka den dolda samhällsstrukturen i flera verkliga nätverk, inklusive 3,7 miljoner amerikanska patent, 575.000 fysik artiklar från ArXiv preprint server, och 875.000 anslutna webbsidor från Internet. Dessutom demonstrerar vi på stora simulerade nätverk att vår algoritm exakt upptäcker den sanna samhällsstrukturen. Detta papper öppnar dörren till att använda sofistikerade statistiska modeller för att analysera massiva nätverk. Detektion av gemenskapen är viktigt både för att utforska ett nät och för att förutsäga anslutningar som ännu inte observerats. Genom att till exempel hitta samhällena i ett stort citeringsdiagram över vetenskapliga artiklar kan vi göra hypoteser om de fält och delfält som de innehåller. Genom att hitta samhällen i ett stort socialt nätverk kan vi lättare göra förutsägelser till enskilda medlemmar om vem de kanske är vänner med men ännu inte är anslutna till. I den här artikeln utvecklar vi en algoritm som upptäcker samhällen i moderna verkliga nätverk. Utmaningen är att verkliga nätverk är massiva-de kan innehålla hundratusentals eller till och med miljoner noder. Vi kommer att undersöka ett nätverk av vetenskapliga artiklar som innehåller 575.000 artiklar, ett nätverk av anslutna webbsidor som innehåller 875.000 sidor, och ett nätverk av amerikanska patent som innehåller 3.700.000 patent. De flesta metoder för att upptäcka communityn kan inte hantera data på den här skalan. Det finns två grundläggande svårigheter att upptäcka samhällen i sådana nätverk. Den första är att många befintliga gemenskapliga detektionsalgoritmer antar att varje nod tillhör en enda gemenskap (1, (3) (4) (5) (6) (7) (14) (15) (16). I verkliga nätverk kommer varje nod sannolikt att tillhöra flera samhällen och dess anslutningar kommer att återspegla dessa flera medlemskap (2, (8) (9) (10) (11) (12) (13) 17). I ett stort socialt nätverk kan till exempel en medlem vara ansluten till arbetskamrater, skolkamrater och grannar. Vi behöver algoritmer som upptäcker överlappande samhällen för att fånga heterogeniteten i varje nods kontakter. Den andra svårigheten är att befintliga algoritmer är för långsamma. Många community detektion algoritmer iterativt analysera varje par av noder, oavsett om noderna i paret är anslutna i nätverket (5, 6, 10). Följaktligen, dessa algoritmer kör i tid kvadrat i antalet noder, vilket gör analysera massiva nätverk beräkningsbart intractable. Andra algoritmer undviker beräkning om oanslutna noder (2-4, 7-9, 11-17). Dessa metoder är mer effektiva, men antingen göra alltför enkla antaganden, är fortfarande svårt att skala, eller har svårt att förutsäga. Vår algoritm tar itu med dessa svårigheter. Det upptäcker de dolda överlappande samhällen i massiva nätverk, och dess resultat kan användas för att utforska, förstå och bilda förutsägelser om deras struktur. Bilda. 1 ger ett exempel. Detta är en subgraf av ett nätverk av 575.000 vetenskapliga artiklar på arXiv preprint server (21); varje länk betecknar att en artikel citerar eller citeras av en annan artikel. Vår algoritm analyserade detta nätverk, upptäcka överlappande samhällen bland citeringar. Det tilldelade flera samhällen till varje artikel och en enda gemenskap till varje länk. Många artiklar länkar mestadels till andra artiklar inom deras huvudgemenskap. Men artikeln "Ett alternativ till kompaktering" (22) är olika-det länkar till flera samhällen, vilket tyder på att det relaterar till flera fält. Att identifiera noder i stora nätverk som överbryggar flera samhällen är ett sätt som vår algoritm ger insikter i nätverkets struktur. Vår algoritm identifierar hundratals överlappande samhällen bland miljontals noder på bara några timmar. Det är snabbt på grund av sin enkla struktur: (1) delprov en subgraf från den fullständiga grafen; (2) analysera subgrafen under algoritmens aktuella uppskattning av samhällena; (3) uppdatera denna uppskattning av samhällena, baserat på analysen från föregående steg; (4) upprepa. Denna kraftfulla algoritmiska struktur är effektiv eftersom den bara analyserar en subgraf av nätverket vid varje iteration. Dessa subgrafer kan vara så stora eller så små som är möjliga att beräkna, och kan utformas för att maximera den statistiska informationen för att effektivt hitta samhällen. Dessutom kräver algoritmen inte att nätverket är fullt observerat innan man börjar uppskatta samhällen; dess algoritmiska struktur kopplar naturligt samman datainsamling med dataanalys. Vad vi kommer att visa nedan är att vår algoritm uppstår när vi tar en Bayesian strategi för att upptäcka överlappande samhällen. I synnerhet antar vi en probabilistisk modell av nätverk (23) där varje nod kan tillhöra flera samhällen (10). Vi analyserar sedan ett nätverk genom att beräkna den bakre, den villkorliga fördelningen av de dolda samhällena med tanke på det observerade nätverket. Den effektiva strukturen för algoritm-iterativt subsampling nätverket och uppdatera en uppskattning av de dolda communities-emerges när vi approximerar denna villkorade distribution med variationsmetoder (24) i kombination med stokastisk optimering (25, 26). I resten av tidningen beskriver vi en modell av överlappande samhällen (10) och presenterar vår effektiva algoritm för beräkning med den. Vi demonstrerar kapaciteten i denna analys på tre stora verkliga nätverk och rapporterar om en studie av stora simulerade nätverk där samhällsstrukturen är känd.
Gopalan och Blei REF föreslog en algoritm som naturligt interparerar subsampling från nätverket och uppdaterar en uppskattning av dess samhällen.
Efficient discovery of overlapping communities in massive networks
{'venue': 'Proceedings of the National Academy of Sciences of the United States of America', 'journal': 'Proceedings of the National Academy of Sciences of the United States of America', 'mag_field_of_study': ['Computer Science', 'Medicine']}