Vi föreslår en ny metod för att hitta samhällsstrukturen i komplexa nätverk baserat på en extrem optimering av värdet av modularitet. Metoden överträffar den optimala modularitet som finns i de befintliga algoritmerna i litteraturen. Vi presenterar resultaten av algoritmen för dator simulerade och verkliga nätverk och jämför dem med andra metoder. Metodens effektivitet och noggrannhet gör det möjligt att använda den för korrekt identifiering av samhällsstrukturen i stora komplexa nätverk. Beskrivningen av strukturen i komplexa nätverk har under de senaste åren varit en av fokuserna för fysikersamhällets uppmärksamhet. Beskrivningsnivåerna sträcker sig från mikroskopisk (grad, klustringskoefficient, centralitetsmått etc., enskilda noder) till makroskopisk beskrivning av hela nätverkets statistiska egenskaper (gradfördelning, total klustringskoefficient, grad-grad korrelationer etc.) [1, 2, 3, 4]. Mellan dessa två ytterligheter finns en "mesoskopisk" beskrivning av nätverk som försöker förklara sin samhällsstruktur. Den allmänna uppfattningen om samhällsstruktur i komplexa nätverk påpekades först i fysiklitteraturen av Girvan och Newman [5], och hänvisar till det faktum att noder i många verkliga nätverk verkar gruppera i subgrafer där densiteten av interna anslutningar är större än kopplingarna med resten av noder i nätverket. Samhällets struktur har empiriskt hittats i många verkliga teknologiska, biologiska och sociala nätverk [6, 7, 8, 9, 10] och dess uppkomst verkar vara i centrum för nätverksbildningsprocessen [11]. De befintliga metoderna för att utforma gemenskapsstrukturen i komplexa nätverk har nyligen granskats [10]. Alla dessa metoder kräver en definition av gemenskap som fastställer den gräns upp till vilken en grupp bör betraktas som en gemenskap. Begreppet gemenskap är emellertid kvalitativt: noder måste vara mer sammankopplade inom sin gemenskap än med resten av nätverket, och dess kvantifiering är fortfarande föremål för debatt. Några kvantitativa definitioner som kom från sociologi har använts i de senaste studierna [12], men i allmänhet, fysik gemenskapen har allmänt accepterat en nyligen åtgärd för samhällsstrukturen baserat på begreppet modularitet Q infördes av Newman och Girvan [13] : där e rr är den bråkdel av länkar som förbinder två noder inne i samhället r, en r den bråkdel av länkar som har en eller båda hörn inom gemenskapen r, och summan sträcker sig till alla samhällen r i ett givet nätverk. Observera att denna åtgärd ger ett sätt att avgöra om en viss mesoskopisk beskrivning av grafen i termer av samhällen är mer eller mindre exakt. Ju större Q-värdena är, desto noggrannare är en uppdelning i samhällen. Sökandet efter det optimala (största) modularitetsvärdet är ett NP-hårdt problem på grund av att utrymmet för möjliga partitioner växer snabbare än någon effekt i systemets storlek. Därför är en heuristisk sökstrategi obligatorisk för att begränsa sökutrymmet samtidigt som optimeringsmålet [14] bevaras. Det är faktiskt möjligt att relatera det nuvarande optimeringsproblemet för Q med klassiska problem inom statistisk fysik, t.ex. Problemet med att hitta markens tillståndsenergi [15], där algoritmer inspirerades av naturliga optimeringsprocesser som simulerad glödgning [16] och genetiska algoritmer [17] har använts med framgång. I detta brev föreslår vi en ny splittrande algoritm som optimerar modularitet Q med hjälp av en heuristisk sökning baserad på den Extrema Optimization (EO) algoritm som föreslås av Boettcher och Percus [18, 19]. Denna algoritm är inspirerad i sin tur i evolutionsmodellen av, och fungerar i princip optimera en global variabel genom att förbättra extrem lokala variabler som involverar coevolutionary lavinches. EO-algoritmers prestanda har visat sig övervinna effektiviteten hos klassisk simulerad glödgning och genetiska algoritmer som ger konkurrenskraftig noggrannhet [21]. I vårt fall är den globala variabeln att optimera Q enligt definitionen i ekv.(1). Definitionen av de lokala variabler som används i problemet med extremoptimering bör därför relateras till bidraget från enskilda noder i till summan i ekv.(1) med tanke på en viss uppdelning i samhällen där r(i) är antalet länkar som en nod i tillhör en gemenskap r har med noder in i samma gemenskap, och k i är graden av nod i. Observera att Q = i q i där jag hänvisar till alla noder i nätverket givet en viss uppdelning i gemenskaper och L är det totala antalet länkar i nätverket. Eq. Vad är det?(2) ger en
I REF föreslogs en ny metod för gemenskapens upptäckt i komplexa nätverk baserat på en extrem modulär optimeringsram.
Community detection in complex networks using extremal optimization.
{'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']}