Samfunnsstruktur - Community structure

I studiet av komplekse nettverk sies det at et nettverk har en samfunnsstruktur hvis nodene i nettverket enkelt kan grupperes i (potensielt overlappende) sett med noder slik at hvert sett med noder er tett forbundet internt. I det spesielle tilfellet med ikke-overlappende samfunnsfunn, innebærer dette at nettverket deler seg naturlig i grupper av noder med tette forbindelser internt og sparsommere forbindelser mellom grupper. Men overlappende fellesskap er også tillatt. Den mer generelle definisjonen er basert på prinsippet om at par med noder er mer sannsynlig å være koblet sammen hvis de begge er medlemmer av det samme fellesskapet (e), og mindre sannsynlig at de er koblet sammen hvis de ikke deler fellesskap. Et beslektet, men annerledes problem er fellesskapssøk , der målet er å finne et fellesskap som et bestemt toppunkt tilhører.

Egenskaper

Fig. 1: En skisse av et lite nettverk som viser fellesskapsstruktur , med tre grupper av noder med tette interne forbindelser og sparsommere forbindelser mellom grupper.

I studiet av nettverk , for eksempel datamaskinen og informasjon nettverk, sosiale nettverk og biologiske nettverk, har en rekke ulike egenskaper er funnet å skje ofte, inkludert små-verden eiendom , tunge-tailed graders distribusjoner , og clustering , blant andre. En annen felles egenskap er samfunnsstruktur. I nettverkssammenheng refererer samfunnsstruktur til forekomsten av grupper av noder i et nettverk som er tettere koblet internt enn med resten av nettverket, som vist i eksempelbildet til høyre. Denne inhomogeniteten av forbindelser antyder at nettverket har visse naturlige inndelinger i seg.

Fellesskap er ofte definert i form av partisjonen av settet med hjørner, det vil si at hver node blir satt inn i et og bare ett fellesskap, akkurat som på figuren. Dette er en nyttig forenkling, og de fleste fellesskapsdeteksjonsmetoder finner denne typen samfunnsstruktur. Imidlertid kan en bedre representasjon i noen tilfeller være en der hjørner er i mer enn ett fellesskap. Dette kan skje i et sosialt nettverk der hvert toppunkt representerer en person, og samfunnene representerer de forskjellige vennegruppene: ett fellesskap for familien, et annet fellesskap for medarbeidere, ett for venner i samme idrettsklubb, og så videre. Bruken av klikk for å identifisere fellesskap som er diskutert nedenfor, er bare ett eksempel på hvordan en slik overlappende samfunnsstruktur kan bli funnet.

Noen nettverk har kanskje ingen meningsfylt samfunnsstruktur. Mange grunnleggende nettverksmodeller, for eksempel tilfeldig graf og Barabási – Albert -modellen , viser ikke samfunnsstruktur.

Betydning

Samfunnsstrukturer er ganske vanlige i virkelige nettverk. Sosiale nettverk inkluderer samfunnsgrupper (opprinnelsen til begrepet, faktisk) basert på felles beliggenhet, interesser, yrke, etc.

Å finne en underliggende samfunnsstruktur i et nettverk, hvis det eksisterer, er viktig av flere årsaker. Fellesskap tillater oss å lage et stort kart over et nettverk siden individuelle fellesskap fungerer som meta-noder i nettverket, noe som gjør studien enklere.

Individuelle fellesskap kaster også lys over funksjonen til systemet representert av nettverket siden fellesskap ofte tilsvarer funksjonelle enheter i systemet. I metabolske nettverk tilsvarer slike funksjonelle grupper sykluser eller veier, mens i proteininteraksjonsnettverket tilsvarer lokalsamfunn proteiner med lignende funksjonalitet inne i en biologisk celle. På samme måte danner siteringsnettverk fellesskap etter forskningsemne. Å kunne identifisere disse understrukturene i et nettverk kan gi innsikt i hvordan nettverksfunksjon og topologi påvirker hverandre. Slik innsikt kan være nyttig for å forbedre noen algoritmer på grafer, for eksempel spektralgruppering .

En veldig viktig grunn som gjør fellesskap viktige er at de ofte har svært forskjellige egenskaper enn gjennomsnittlige egenskaper for nettverkene. Dermed går det bare å konsentrere seg om gjennomsnittsegenskapene vanligvis mange viktige og interessante funksjoner inne i nettverkene. For eksempel kan det i et gitt sosialt nettverk eksistere både grupper og tilbakeholdne grupper samtidig.

Eksistensen av lokalsamfunn påvirker også generelt ulike prosesser som ryktespredning eller epidemisk spredning som skjer på et nettverk. Derfor for å forstå slike prosesser riktig, er det viktig å oppdage lokalsamfunn og også å studere hvordan de påvirker spredningsprosessene i forskjellige innstillinger.

Til slutt, en viktig applikasjon som fellesskapsdeteksjon har funnet i nettverksvitenskap, er prediksjon om manglende koblinger og identifisering av falske koblinger i nettverket. Under måleprosessen kan det hende at noen koblinger ikke blir observert av flere årsaker. På samme måte kan noen lenker falskt komme inn i dataene på grunn av feilene i målingen. Begge disse sakene håndteres godt av samfunnsdeteksjonsalgoritme siden den lar en tildele sannsynligheten for eksistens av en kant mellom et gitt par noder.

Algoritmer for å finne fellesskap

Å finne fellesskap i et vilkårlig nettverk kan være en beregningsmessig vanskelig oppgave. Antall lokalsamfunn, om noen, i nettverket er vanligvis ukjent, og samfunnene er ofte av ulik størrelse og/eller tetthet. Til tross for disse vanskelighetene har imidlertid flere metoder for å finne fellesskap blitt utviklet og ansatt med varierende suksess.

Minimumskuttmetode

En av de eldste algoritmene for å dele nettverk i deler er minimumskuttmetoden (og varianter som forholdskutt og normalisert kutt). Denne metoden ser for eksempel bruk i lastbalansering for parallell databehandling for å minimere kommunikasjonen mellom prosessornoder.

I minimumskuttmetoden er nettverket delt inn i et forhåndsbestemt antall deler, vanligvis av omtrent samme størrelse, valgt slik at antallet kanter mellom grupper minimeres. Metoden fungerer bra i mange av applikasjonene den opprinnelig var beregnet på, men er mindre enn ideell for å finne samfunnsstruktur i generelle nettverk siden den vil finne fellesskap uansett om de er implisitte i strukturen, og den vil bare finne et fast antall av dem.

Hierarkisk klynge

En annen metode for å finne fellesskapsstrukturer i nettverk er hierarkisk gruppering . I denne metoden definerer man et likhetsmål som kvantifiserer en (vanligvis topologisk) type likhet mellom nodepar. Vanlige målinger inkluderer cosinus -likheten , Jaccard -indeksen og Hamming -avstanden mellom radene i adjacensmatrisen . Deretter grupperer man lignende noder i fellesskap i henhold til dette tiltaket. Det er flere vanlige ordninger for å utføre grupperingen, de to enkleste er enkeltkoblingsklynger , der to grupper betraktes som separate fellesskap hvis og bare hvis alle par noder i forskjellige grupper har likhet lavere enn en gitt terskel, og fullstendig koblingsklynger , der alle noder i hver gruppe har likhet større enn en terskel. Et viktig trinn er hvordan man bestemmer terskelen for å stoppe den agglomerative klyngingen, noe som indikerer en nærmest optimal samfunnsstruktur. En felles strategi består i å bygge en eller flere beregninger som overvåker de globale egenskapene til nettverket, som topper på et gitt trinn i klyngen. En interessant måte i denne retning er anvendelsen av forskjellige likhet eller ulikhet tiltak samt gjennom konvekse summer ,. En annen tilnærming er beregningen av en mengde som overvåker tettheten av kanter i klynger med hensyn til tettheten mellom klynger, for eksempel partisjonstettheten, som har blitt foreslått når likhetsmetrikken er definert mellom kantene (noe som tillater definisjonen av overlappende fellesskap) , og utvides når likheten er definert mellom noder, noe som gjør det mulig å vurdere alternative definisjoner av fellesskap som laug (dvs. grupper av noder som deler et lignende antall lenker med hensyn til de samme naboene, men ikke nødvendigvis koblet seg selv). Disse metodene kan utvides til å vurdere flerdimensjonale nettverk, for eksempel når vi har å gjøre med nettverk som har noder med forskjellige typer lenker.

Girvan - Newman -algoritme

En annen vanlig algoritme for å finne lokalsamfunn er Girvan - Newman -algoritmen . Denne algoritmen identifiserer kanter i et nettverk som ligger mellom lokalsamfunn og fjerner dem deretter, og etterlater bare fellesskapene selv. Identifikasjonen utføres ved å bruke det grafteoretiske målet mellom sentralitet , som tildeler et tall til hver kant som er stor hvis kanten ligger "mellom" mange par noder.

Algoritmen Girvan – Newman gir resultater av rimelig kvalitet og er populær fordi den er implementert i en rekke standard programvarepakker. Men den går også sakte og tar tid O ( m ²n ) på et nettverk av n hjørner og m kanter, noe som gjør det upraktisk for nettverk på mer enn noen få tusen noder.

Maksimalisering av modularitet

Til tross for de kjente ulempene, er en av de mest brukte metodene for samfunnsdeteksjon maksimalisering av moduler. Modularitet er en fordelfunksjon som måler kvaliteten på en bestemt inndeling av et nettverk i lokalsamfunn. Modularitetsmaksimeringsmetoden oppdager lokalsamfunn ved å søke over mulige divisjoner i et nettverk etter en eller flere som har spesielt høy modularitet. Siden uttømmende søk over alle mulige divisjoner vanligvis er vanskelig, er praktiske algoritmer basert på omtrentlige optimaliseringsmetoder som grådige algoritmer, simulert annealing eller spektraloptimalisering, med forskjellige tilnærminger som tilbyr forskjellige balanser mellom hastighet og nøyaktighet. En populær tilnærming til maksimalisering av modularitet er Louvain -metoden , som iterativt optimaliserer lokalsamfunn inntil global modularitet ikke lenger kan forbedres gitt forstyrrelser i den nåværende samfunnsstaten. En algoritme som bruker RenEEL -opplegget, som er et eksempel på Extremal Ensemble Learning (EEL) -paradigmet, er for tiden den beste modularitetsmaksimerende algoritmen.

Nytteligheten av modularitetsoptimalisering er tvilsom, ettersom det har blitt vist at modularitetsoptimalisering ofte ikke klarer å oppdage klynger som er mindre enn noen skala, avhengig av størrelsen på nettverket ( oppløsningsgrense ); på den annen side er landskapet med modularitetsverdier preget av en enorm degenerasjon av partisjoner med høy modularitet, nær det absolutte maksimum, som kan være veldig forskjellige fra hverandre.

Statistisk slutning

Metoder basert på statistisk slutning prøver å tilpasse en generativ modell til nettverksdataene, som koder for fellesskapsstrukturen. Den generelle fordelen med denne tilnærmingen sammenlignet med alternativene er dens mer prinsipielle natur og evnen til iboende å ta opp spørsmål av statistisk betydning . De fleste metodene i litteraturen er basert på den stokastiske blokkmodellen samt varianter, inkludert blandet medlemskap, gradskorreksjon og hierarkiske strukturer. Modellvalg kan utføres ved hjelp av prinsipielle tilnærminger som minimum beskrivelseslengde (eller tilsvarende Bayesiansk modellvalg ) og sannsynlighetsforholdstest . For tiden eksisterer mange algoritmer for å utføre effektiv slutning av stokastiske blokkmodeller, inkludert trosformidling og agglomerativ Monte Carlo .

I motsetning til fremgangsmåter som forsøker å klynge et nettverk gitt en objektiv funksjon, er denne klasse av metoder basert på generative modeller, som ikke bare tjener som en beskrivelse av den store strukturen av nettverket, men også kan brukes til å generalisere den data og forutsi forekomsten av manglende eller falske koblinger i nettverket.

Klikkbaserte metoder

Cliques er undergrafer der hver node er koblet til hver annen node i clique. Siden noder ikke kan være tettere forbundet enn dette, er det ikke overraskende at det er mange tilnærminger til fellesskapsdeteksjon i nettverk basert på deteksjon av klikk i en graf og analyse av hvordan disse overlapper hverandre. Vær oppmerksom på at et knutepunkt kan være medlem av mer enn én klikk, og en node kan være medlem av mer enn ett fellesskap i disse metodene som gir en " overlappende fellesskapsstruktur ".

En tilnærming er å finne de " maksimale klikkene ". Det vil si å finne klikker som ikke er undergrafen til noen annen klikk. Den klassiske algoritmen for å finne disse er Bron – Kerbosch -algoritmen . Overlappingen av disse kan brukes til å definere fellesskap på flere måter. Det enkleste er å vurdere bare maksimale klikk som er større enn en minimumsstørrelse (antall noder). Foreningen av disse klikkene definerer deretter et undergraf hvis komponenter (frakoblede deler) deretter definerer fellesskap. Slike tilnærminger implementeres ofte i analyseprogramvare for sosiale nettverk som UCInet.

Den alternative tilnærmingen er å bruke klikker av fast størrelse . Overlappingen av disse kan brukes til å definere en type -regelmessig hypergraf eller en struktur som er en generalisering av linjediagrammet (tilfellet når ) kjent som en " Clique -graf ". Klikkediagrammene har hjørner som representerer klikkene i den originale grafen, mens kantene på klikkegrafen registrerer overlappingen av klikken i den originale grafen. Ved å bruke noen av de tidligere metodene for samfunnsdeteksjon (som tildeler hver node til et fellesskap) på klikkediagrammet, tilordner deretter hver klikk til et fellesskap. Dette kan deretter brukes til å bestemme fellesskapsmedlemskap for noder i klikkene. Ettersom en node kan være i flere klikk, kan den være medlem av flere lokalsamfunn. For eksempel definerer clique percolation -metoden samfunn som perkolasjonsklynger av -cliques . For å gjøre dette finner den alle -klik i et nettverk, det vil si alle de komplette undergrafene til -noder . Den definerer deretter to -klikk for å være tilstøtende hvis de deler noder, det vil si at denne brukes til å definere kanter i en klikkgraf. Et fellesskap er da definert for å være den maksimale foreningen av -klikker der vi kan nå hvilken som helst -klikk fra hvilken som helst annen -klikk gjennom serier av -clique -tilstøtninger. Det vil si at fellesskap bare er de tilkoblede komponentene i klikkediagrammet. Siden en node kan tilhøre flere forskjellige -klikk -klyngeklynger samtidig, kan fellesskapene overlappe hverandre. ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k = 2}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k-1}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k}$

Testemetoder for å finne fellesskapsalgoritmer

Evalueringen av algoritmer, for å oppdage hvilke som er bedre til å oppdage samfunnsstruktur, er fortsatt et åpent spørsmål. Den må være basert på analyser av nettverk av kjent struktur. Et typisk eksempel er "fire grupper" -testen, der et nettverk er delt inn i fire like store grupper (vanligvis med 32 noder hver) og sannsynligheten for tilkobling innenfor og mellom grupper varierte for å skape mer eller mindre utfordrende strukturer for deteksjonen algoritme. Slike referansediagrammer er et spesielt tilfelle av den plantede l-partisjonsmodellen til Condon og Karp , eller mer generelt til " stokastiske blokkmodeller ", en generell klasse av tilfeldige nettverksmodeller som inneholder samfunnsstruktur. Andre mer fleksible benchmarks har blitt foreslått som gir mulighet for varierende gruppestørrelser og ikke -private gradfordelinger, for eksempel LFR -referanse som er en forlengelse av referansepunktet for fire grupper som inkluderer heterogene fordelinger av nodegrad og fellesskapsstørrelse, noe som gjør det til en mer alvorlig test av samfunnet deteksjonsmetoder.

Vanlige datamaskingenererte referanser starter med et nettverk av veldefinerte fellesskap. Deretter ødelegges denne strukturen ved å koble til eller fjerne koblinger, og det blir vanskeligere og vanskeligere for algoritmene å oppdage den opprinnelige partisjonen. På slutten når nettverket et punkt der det i hovedsak er tilfeldig. Denne typen referanse kan kalles "åpen". Ytelsen på disse referansene evalueres ved hjelp av tiltak som normalisert gjensidig informasjon eller variasjon av informasjon . De sammenligner løsningen oppnådd av en algoritme med den opprinnelige samfunnsstrukturen, og evaluerer likheten mellom begge partisjonene.

Detekterbarhet

I løpet av de siste årene har et ganske overraskende resultat blitt oppnådd av forskjellige grupper som viser at det eksisterer en faseovergang i deteksjonsproblemet, som viser at etter hvert som tettheten av forbindelser i lokalsamfunn og mellom lokalsamfunn blir mer og mer like eller begge blir mindre (tilsvarende , ettersom samfunnsstrukturen blir for svak eller nettverket blir for sparsomt), blir plutselig fellesskapene ikke oppdagbare. På en måte eksisterer samfunnene selv fremdeles, siden tilstedeværelse og fravær av kanter fortsatt er korrelert med fellesskapsmedlemskapene til deres endepunkter; men det blir informasjonsteoretisk umulig å merke nodene bedre enn tilfeldigheter, eller til og med skille grafen fra en generert av en nullmodell som Erdos-Renyi-modellen uten samfunnsstruktur. Denne overgangen er uavhengig av hvilken type algoritme som brukes til å oppdage fellesskap, noe som innebærer at det eksisterer en grunnleggende grense for vår evne til å oppdage lokalsamfunn i nettverk, selv med optimal Bayesisk slutning (dvs. uavhengig av våre beregningsressurser).

Vurder en stokastisk blokkmodell med totale noder, grupper av like størrelse, og la og være forbindelsessannsynligheter i henholdsvis og mellom gruppene. Hvis , ville nettverket ha en samfunnsstruktur siden koblingstettheten inne i gruppene ville være mer enn tettheten av koblinger mellom gruppene. I det sparsomme tilfellet, og skalaen slik at gjennomsnittlig grad er konstant: ${\ displaystyle n}$ ${\ displaystyle q = 2}$ ${\ displaystyle p _ {\ tekst {i}}}$ ${\ displaystyle p _ {\ text {out}}}$ ${\ displaystyle p _ {\ text {in}}> p _ {\ text {out}}}$ ${\ displaystyle p _ {\ tekst {i}}}$ ${\ displaystyle p _ {\ text {out}}}$ ${\ displaystyle O (1/n)}$

{\ displaystyle p _ {\ text {in}} = c _ {\ text {in}}/n}

og

{\ displaystyle p _ {\ text {out}} = c _ {\ text {out}}/n}

Da blir det umulig å oppdage lokalsamfunnene når:

{\ displaystyle c _ {\ text {in}}-c _ {\ text {out}} = {\ sqrt {2 (c _ {\ text {in}}+c _ {\ text {out}})}}}}}

Motstandsdyktighet til modulære nettverk

Motstandsdyktigheten til modulære nettverk på grunn av node- eller koblingsfeil studeres vanligvis ved hjelp av perkolasjonsteori. Nettverkets struktur mens du angriper inter-noder (dvs. noder som forbinder lokalsamfunn) har blitt studert. En nylig studie analyserte også hvordan sammenhengen mellom fellesskap styrker motstanden til lokalsamfunnene. En nylig studie av Gaogao Dong et al identifiserte modulære strukturer for optimal motstandskraft.

Epidemier på modulære nettverk

Studien av epidemimodeller på modulære nettverk har blitt studert av Valdez et al. Disse forfatterne studerte også kriteriet for å erklære pandemi.

Romlige modulære nettverk

Illustrasjon av modellen. Den romlige modulmodellen representerer en struktur av et nettverk av infeksjonskanaler inne i byer (moduler) og mellom byer. Inne i en by er infeksjonskanalene tette og spredt tilfeldig mellom forskjellige områder av byen (grønne lenker) som i et Erdős - Rényi -nettverk som har tilfeldig lignende struktur mens infeksjonskanalene fra en by til en annen vanligvis er mulig mellom nabobyene (rødt lenker) som har romlig struktur

En modell for romlig modulære nettverk er utviklet av Gross et al. Modellen beskriver f.eks. Infrastrukturer i et land der lokalsamfunn (moduler) representerer byer med mange forbindelser plassert i todimensjonalt rom. Koblingen mellom lokalsamfunn (byer) er mindre og vanligvis til nærmeste naboer (se fig. 2). Epidemisk spredning på slike nettverk har blitt studert i Gross og Havlin.

Languages

In other projects