Vi är intresserade av att spåra förändringar i storskaliga data genom att periodvis skapa en agglomerativ klusterbildning och undersöka utvecklingen av kluster (kommuner) över tiden. Vi undersöker en stor verklig datauppsättning: NEC CiteSeer databas, ett länkat nätverk av > 250 000 papper. För att spåra förändringar över tid krävs en klusteralgoritm som producerar kluster stabila under små perturbationer av indata. Små störningar av CiteSeer-data leder dock till betydande förändringar i de flesta kluster. Ett skäl till detta är att den ordning i vilken handlingar i samhällen kombineras är något godtycklig. Emellertid, vissa undergrupper av papper, som kallas naturliga samhällen, motsvarar verklig struktur i CiteSeer databasen och därmed visas i någon klusterbildning. Genom att identifiera den delmängd av kluster som förblir stabila under flera klusterkörningar, får vi den uppsättning naturliga samhällen som vi kan spåra över tiden. Vi visar att sådana naturliga samhällen gör det möjligt för oss att identifiera framväxande samhällen och spåra tidsmässiga förändringar i den underliggande strukturen av våra nätverksdata. E sammanslagning av egenskaper hos stora sammankopplade nätverk har nyligen blivit fokus för intensiva studier. Denna forskning drivs av den ökande komplexiteten och betydelsen av stora nätverk, såsom World Wide Web, elnätet, och stora sociala nätverk som fångar relationer mellan individer. Realworld-nätverk uppvisar i allmänhet egenskaper som ligger någonstans mellan dem i mycket strukturerade nätverk och rent slumpmässiga (1-4). Hittills har de flesta forskningen fokuserat på att använda statiska egenskaper, såsom anslutning av noderna i nätverket och det genomsnittliga avståndet mellan två noder, för att förklara den komplexa strukturen. Dessa nätverk utvecklas dock i allmänhet över tiden och därför är tidsbundna egenskaper en viktig källa till intresse. Vårt mål i detta dokument är att tillhandahålla tekniker för att studera utvecklingen av stora sammankopplade nätverk. I vår strategi använder vi agglomerativa kluster av det länkade nätverket. Genom att samla nätverket vid olika tidpunkter studerar vi dess tidsutveckling. Detta tillvägagångssätt lägger en ny börda på den underliggande klustermetoden. Klustermetoder kan vara förvånansvärt känsliga för mindre ändringar av indata. För att få en statisk bild av uppgifternas struktur på högre nivå, kan sådana instabiliteter vara godtagbara eftersom den resulterande hierarkin ofta redan avslöjar intressant struktur. När det gäller att spåra förändringar över tid måste vi dock kunna hitta motsvarande gemenskaper i kluster som tagits från data vid olika tidpunkter. Om klustren är mycket känsliga för små störningar av indata, blir det svårt, om inte omöjligt, att skilja mellan "verkliga" förändringar jämfört med "oavsiktliga" förändringar i strukturen på högre nivå. I klustren av våra länkade nätverksdata fann vi att det finns ett stort antal relativt slumpmässiga kluster som inte motsvarar verkliga samhällsstrukturer. Dessa slumpmässiga kluster skymmer de verkliga temporalförändringarna. Lyckligtvis fann vi att när man utför en serie agglomerativa klusterkörningar, varje körning på något perturbed indata, kan man identifiera en stabil uppsättning kluster som förekommer i en betydande andel av kluster. Dessutom förefaller dessa stabila kluster motsvara nätverkets verkliga underliggande samhällsstruktur. Vi hänvisar till sådana stabila kluster som naturliga samhällen. Vi använder begreppet naturliga samhällen för att visa att vi kan spåra dessa naturliga samhällen effektivt över tiden, och kan därför karakterisera den timliga utvecklingen av nätverket.
Å andra sidan spårade REF under utveckling samhällen i hela CiteSeer papper citering diagram.
Tracking evolving communities in large linked 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']}