Flera forskningsstudier har visat att komplexa nätverk som modellerar verkliga fenomen kännetecknas av slående egenskaper: (i) de är organiserade enligt samhällsstruktur, och (ii) deras struktur utvecklas med tiden. Många forskare har arbetat med metoder som effektivt kan avtäcka substrukturer i komplexa nätverk, vilket ger upphov till området för samhällsupptäckt. Ett nytt och fascinerande problem började fånga forskarintresset nyligen: identifiering av framväxande samhällen. Dynamiska nätverk kan användas för att modellera utvecklingen av ett system: noder och kanter är muterbara, och deras närvaro, eller frånvaro, djupt påverkar den samhällsstruktur som komponerar dem. Syftet med denna undersökning är att presentera de utmärkande dragen och utmaningarna med dynamiska upptäckter i samhället och föreslå en klassificering av publicerade metoder. Som en "användarmanual" organiserar detta arbete state-of-the-art metoder i en taxonomi, baserat på deras logik, och deras specifika momentiation. Med tanke på en definition av nätverksdynamik, önskvärda samhällsegenskaper och analytiska behov kommer denna undersökning att stödja forskare för att identifiera vilka strategier som bäst passar deras behov. Den föreslagna klassificeringen kan också hjälpa forskare att välja i vilken riktning de ska orientera sin framtida forskning. är några exempel på observerbara händelser som ofta undersöks med hjälp av instrument som lånats från grafteori. En viktig fråga att ta itu med när man studerar denna typ av verkliga händelser ligger i identifieringen av meningsfulla understrukturer gömda inom det övergripande komplexa systemet. Hur man delar upp ett komplext nätverk i samhällen är ett brett studerat problem (Fortunato 2010; Coscia et al. 2011) : flera arbeten, från en bred uppsättning discipliner, föreslog olika gemenskapsdefinitioner och tillvägagångssätt som kan hämta sådana strukturer automatiskt. Omfattningen av verk som täcker detta fascinerande ämne belyser dess allmängiltighet: samhällen kan fånga grupper av starkt anslutna online-dokument, individer som delar en social miljö samt produkter som ofta köps tillsammans. Det mesta av den vetenskapliga litteraturen tillägnad samhällsupptäcktsproblemet (CD) utgår från ett mycket strikt antagande: verkliga fenomen kan modelleras med statiska nätverk - det vill säga matematiska objekt frusna i tiden. Tyvärr passar ett sådant förenklat scenario sällan in på den föränderliga naturen i den värld vi lever i. En av de viktigaste egenskaperna som kännetecknar interaktionsfenomen är att de naturligt utvecklas genom tiden: sociala interaktioner utvecklas, telefonsamtal har en begränsad varaktighet, och mänsklig rörlighet förändras allteftersom tiden går. Den timliga dimensionen förmedlar mycket värdefull information som analytikern behöver för att bättre förstå den verklighet som han eller hon observerar. Behovet av att inkludera sådan kunskap i de verktyg som erbjuds av grafteorin har varit en av grundbultarna i ett helt nytt undersökningsområde som vuxit fram under det senaste årtiondet: dynamisk nätverksanalys. Inom detta nya område omformulerades välkända problem som definierades i statiska miljöer, och man föreslog tidsmedvetna metoder för att lösa dem. Bland dem är dynamisk samhällsupptäckt (DCD) ett av de mest utmanande problemen. Allteftersom tiden går kan noder och kanter förenas och lämna ett dynamiskt nätverk som producerar relevanta perturbationer på sin topologi: samhällen är de grundläggande tegelstenarna i denna komplexa struktur och som sådana påverkas djupt av lokala förändringar. Medan klassiska CD-algoritmer syftar till att identifiera dolda understrukturer, dynamiska metoder ägnas åt att spåra sådana lokala topologier och deras mutationer, ett mål som kan uppfyllas med olika strategier och modellering val. I denna undersökning har vi därför valt att utforma en taxonomi av DCD algoritmer inte genom att överväga den tekniska lösning de använder för att hitta dem utan snarare den strategi de använder för att identifiera tidsmedvetna meningsfulla nätverk understrukturer. Vårt mål är att hjälpa forskare och analytiker att välja den metod, eller åtminstone den klass av metoder, som bättre passar deras behov och data. För var och en av de föreslagna klasserna av DCD algoritmer, diskuterar vi både fördelar och nackdelar. Dessutom ger vi en kort beskrivning av de metoder som genomför deras logik. För att ge en heltäckande bild av detta forskningsområde diskuterar vi också frågor relaterade till utvärderingen av DCD algoritmer, vilket kräver ändringar jämfört med statiska fallet; dessutom sammanfattar vi andra arbeten på DCD, såsom dynamiska gemenskap visualiseringsmetoder, och analytiska tillämpningar till verkliga problem. Undersökningen är organiserad enligt följande. I Avsnitt 2 diskuterar vi de allmänna begreppen bakom dynamisk nätverksanalys och de matematiska modeller som används för att beskriva, i grafteoretiska termer, temporalt föränderliga fenomen. I Avsnitt 3 formaliserar vi CD-problemet på dynamiska nätverk och diskuterar samhällslivscykel och instabilitet. I Avsnitt 4, presenterar vi vår DCD taxonomi beskriver egenhet, fördelar och nackdelar för varje klass av tillvägagångssätt. En detaljerad beskrivning av metoderna görs sedan tillgänglig i bilagan. I avsnitt 5 introducerar och diskuterar vi två klasser av tekniker som ofta används för att jämföra och karakterisera samhällen som identifierats av DCD-algoritmer, nämligen intern och extern kvalitetsbedömning. I Avsnitt 6 går vi igenom några verkliga scenarier som har studerats genom linser av dynamisk samhällsbrytning och tar itu med problemet med att visualisera analytiska resultat. Avsnitt 7 avslutar undersökningen och ger insikter i DCD-relaterade öppna frågor. Bilda. 1. Vad är det för fel på dig? Nätverksrepresentationer. Genom att gå från ett statiskt diagram till ett annat, ökar modellens komplexitet medan kärnan i den tidsbundna information som finns tillgänglig minskar (Rossetti 2015). 2 DYNAMIC NÄT Sedan starten har forskare kontaktat komplexa nätverksanalyser genom att definiera mycket specifika gruvproblem. Bland dem, CD (Fortunato 2010; Coscia et al. 2011), länkbaserad objektrankning (Getoor och Diehl 2005; Duhan et al. 2009), och frekvent mönsterbrytning (Milo et al. 2002; Alon 2007) är exempel på analytiska uppgifter som ursprungligen definierades på nät som frystes i tid. Frånvaron av tidsdimensionen kommer från historiska orsaker: fältets grafteori och bristen på befintliga dynamiska data vid den tidpunkt då området komplexa nätverk uppstod. Med explosionen av mänskliga-genererade data, som ofta samlas in av sociotekniska plattformar, fler och fler dataset med rik tidsinformation som kan studeras som dynamiska nätverk blir tillgängliga. Många verk försökte införliva välkända grafbrytningsproblem från statiska nätverk till temporalnät: temporalmotivbrytning (Kovanen et al. 2011), spridning (Lee et al. 2012), länkförutsägelse (Tabourier et al. 2016), och så vidare. För att bättre ta itu med den centrala frågan i denna undersökning introducerar vi i avsnitt 2.1 de mest använda formalismerna för att representera dynamiska nätverk, och i avsnitt 2.2 diskuterar vi en av de ledande frågorna som uppstår när man hanterar tidsmässigt annoterade nätverk: nätverksminne. Tiden spelar en avgörande roll när det gäller att utforma nättopologier. En av de viktigaste frågorna att ta itu med för att resonera om tidevolverande nätverk är därför relaterade till den matematiska formalism som används för att beskriva dem. Figur 1 visar fyra olika konceptuella lösningar som gradvis introducerar tidsdimensionen i nätverksmodelleringsprocessen. I ett avseende finner vi det fullständiga atemporala scenariot (dvs. en enda nätverksögonblicksbild som fångar en statisk glimt av ett dynamiskt fenomen): nätverksdynamiken kan gradvis införas genom att anta etiketter som väger noder och kanter och därmed fånga ett aggregerat nätverk. Efter detta tillvägagångssätt modellerar vikter antalet förekomst av en given nod/kant i ett förutbestämt observationsfönster: med denna lilla ökning i modellens komplexitet, flera tidsberoende analyser försummas innan det blir möjligt (dvs., binda styrka uppskattning). Aggregeringsstrategier har dock en allvarlig begränsning: de fångar inte upp dynamiken. Därför modellerar flera verk dynamiska fenomen med tidsbeställda serier av nätverksögonblicksbilder. Detta enkla modelleringsval gör att man effektivt kan hålla reda på de perturbationer som förekommer på nätverkets topologi. Samtidigt som modellens uttryckskraft ökar ökar den analytiska komplexiteten också. Vid hantering av nätverksögonblicksbilder för att utföra tid-medveten gruvdrift uppgifter, två frågor måste tas upp: i) hur man håller reda på flera stadier av nätverkets livslängd och ii) hur man harmonisera de analytiska resultat som erhållits i en ögonblicksbild med resultatet av följande. Dynamisk nätverkspartition, liksom aggregering, lider av ett trängande problem: att utföras, en temporal granularity-en tröskel för att omvandla de ursprungliga dynamiska system-behoven som ska fastställas. Eftersom identifieringen av en sådan tröskel inte är trivial-det är, faktiskt, sammanhangsberoende och ofta djupt påverkar analytiska resultat-recent verk föreslår modellering dynamiska fenomen utan någon aggregering, hålla alla timliga detaljer. Sådana studier brukar bryta ner ett dynamiskt nätverk i dess elementära tegelstenar: tidsmässigt beställda, tidsstämplade, interaktioner eller relationer. Vi kommer mer i detalj att beskriva ett sådant tillvägagångssätt, nämligen modellering av tidsbundna nätverk, i nästa avsnitt. Temporala nätverk, undvika aggregering, möjliggöra en fullständig och finkornig beskrivning av nätverkets dynamik: som en nackdel, ökar denna lösning komplexiteten i nätverksmodellen och kräver definition av nya analytiska metoder. Olika problem, liksom tillgängliga data, kräver olika modellering val: statiska nätverk, liksom viktade sådana, används ofta för att identifiera stabila mönster och beskriva den faktiska statusen för ett nätverk, medan ögonblicksbilder och interaktioner är proxies för studien av allt mer dynamiska scenarier. Naturligtvis, med utgångspunkt från finkorniga tidsdata, är det möjligt att generera alla de andra modellerna genom efterföljande aggregeringar. Eftersom vi är intresserade av community detektion metoder som behandlar temporalt kommenterade grafer, i följande kommer vi att belysa de viktigaste styrkorna och nackdelarna med de mest använda modellerna i detta sammanhang: timliga nätverk och nätverksögonblicksbilder. I denna undersökning kommer vi inte att diskutera statiska och viktade nätverk, eftersom de per definition inte tillåter någon att direkt använda tidsinformation, vilket minskar dynamiska problem till statiska sådana: för en fördjupad översikt över CD-metoder som definieras för sådana scenarier, se Fortunato (2010), Fortunato och Hric (2016), Xie et al. (2013b) och Coscia et al. (2011)............................................................................................................................ 2.1.1 Temporära nätverk. Flera formalismer har föreslagits för att representera framväxande nätverk utan att förlora information: temporalnätverk (Holme och Saramäki 2012), tidsvariationsdiagram (Casteigts m.fl. 2012), interaktionsnätverk (Rossetti m.fl. 2015), och länk strömmar och stream grafer (Viard et al. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. 2017), för att nämna de mest populära. Härefter använder vi termen tidsbundna nätverk med en allmän definition som omfattar alla dessa formalismer. Ett temporalt nätverk modellerar en dynamisk struktur där både noder och kanter kan visas och försvinna allteftersom tiden går. Mer formellt har vi följande definition. Ett temporalt nätverk är en graf G = (V, E, T ), där V är en uppsättning trillingar av formen (v, t s, t e ), med v en vertex av grafen och t s, t e T respektive vara födelse-och död tidertamps av motsvarande vertex (med ts ≤ t e ); E är en uppsättning av quadruplets (u, v, t s, t e ), med u, v  på V är hörn av grafen, och t s, t e. T respektive vara födelse- och död tidertamps av motsvarande kant (med t ≤ t e ).
En grundligare undersökning av dynamiska detekteringsmetoder för samhället presenteras i REF.
Community Discovery in Dynamic Networks: A Survey
{'venue': 'CSUR', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}