Mellom sentralitet - Betweenness centrality

En uorientert graf farget basert på sentraliteten mellom hvert toppunkt fra minst (rød) til størst (blå).

I grafteori er mellomstatssentralitet (eller "mellomessentralitet") et mål på sentralitet i en graf basert på korteste veier . For hvert par hjørner i en tilkoblet graf eksisterer det minst én korteste bane mellom hjørnene slik at enten antall kanter banen går gjennom (for uvekte grafer) eller summen av kantene (for vektede grafer) ) er minimert. Mellom sentraliteten for hvert toppunkt er antallet av disse korteste veiene som passerer gjennom toppunktet.

Mellomliggende sentralitet ble utviklet som et generelt mål for sentralitet: det gjelder et bredt spekter av problemer innen nettverksteori, inkludert problemer knyttet til sosiale nettverk , biologi, transport og vitenskapelig samarbeid. Selv om tidligere forfattere intuitivt har beskrevet sentralitet som basert på mellomrom, ga Freeman (1977) den første formelle definisjonen av sentralitet mellom.

Mellomliggende sentralitet finner bred anvendelse i nettverksteorien ; det representerer i hvilken grad noder står mellom hverandre. For eksempel, i et telekommunikasjonsnettverk , ville en node med høyere sentralitet mellom sentralene ha mer kontroll over nettverket, fordi mer informasjon vil passere gjennom den noden.

Definisjon

Sentraliteten mellom en node er gitt av uttrykket: ${\ displaystyle v}$

${\ displaystyle g (v) = \ sum _ {s \ neq v \ neq t} {\ frac {\ sigma _ {st} (v)} {\ sigma _ {st}}}}$

hvor er det totale antallet korteste stier fra node til node og er antallet av de banene som passerer gjennom . ${\ displaystyle \ sigma _ {st}}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle \ sigma _ {st} (v)}$${\ displaystyle v}$

Legg merke til at sentraliteten mellom en node skaleres med antall par noder som antydet av summeringsindeksene. Derfor kan beregningen reskaleres ved å dividere gjennom antall par noder som ikke inkluderer , slik at . Inndelingen gjøres av for dirigerte grafer og for uorienterte grafer, hvor er antall noder i den gigantiske komponenten. Vær oppmerksom på at denne skalerer for høyest mulig verdi, hvor én node krysses av hver eneste korteste bane. Dette er ofte ikke tilfelle, og en normalisering kan utføres uten tap av presisjon ${\ displaystyle v}$${\ displaystyle g \ i [0,1]}$${\ displaystyle (N-1) (N-2)}$${\ displaystyle (N-1) (N-2)/2}$${\ displaystyle N}$

${\ displaystyle {\ mbox {normal}} (g (v)) = {\ frac {g (v)-\ min (g)} {\ max (g)-\ min (g)}}}$

som resulterer i:

${\ displaystyle \ max (normal) = 1}$

${\ displaystyle \ min (normal) = 0}$

Vær oppmerksom på at dette alltid vil være en skalering fra et mindre område til et større område, så ingen presisjon går tapt.

Vektede nettverk

I et vektet nettverk blir koblingene som forbinder nodene ikke lenger behandlet som binære interaksjoner, men veies i forhold til deres kapasitet, innflytelse, frekvens, etc., noe som tilfører en annen dimensjon av heterogenitet i nettverket utover de topologiske effektene. En nodes styrke i et vektet nettverk er gitt av summen av vektene på de tilstøtende kantene.

${\ displaystyle s_ {i} = \ sum _ {j = 1}^{N} a_ {ij} w_ {ij}}$

With and being adjacency and weight matrices between nodes and , henholdsvis. Analogt med kraftlovsfordelingen av grad som finnes i skalafrie nettverk, følger styrken til en gitt node også en kraftlovsfordeling. ${\ displaystyle a_ {ij}}$${\ displaystyle w_ {ij}}$${\ displaystyle i}$${\ displaystyle j}$

${\ displaystyle s (k) \ approx k^{\ beta}}$

En studie av gjennomsnittsverdien av styrken for hjørner med mellomrom viser at den funksjonelle oppførselen kan tilnærmes med en skaleringsform: ${\ displaystyle s (b)}$${\ displaystyle b}$

Perkoleringssentralitet

Perkoleringssentralitet er en versjon av vektet sentralitet mellom, men den tar hensyn til 'tilstanden' til kilden og målnodene for hver korteste vei ved beregning av denne vekten. Perkolasjon av en 'smitte' forekommer i komplekse nettverk i en rekke scenarier. For eksempel kan virus- eller bakteriell infeksjon spre seg over sosiale nettverk av mennesker, kjent som kontaktnettverk. Spredning av sykdom kan også vurderes på et høyere abstraksjonsnivå, ved å vurdere et nettverk av byer eller befolkningssentre, forbundet med vei, jernbane eller flyforbindelser. Datavirus kan spre seg over datanettverk. Rykter eller nyheter om forretningstilbud og avtaler kan også spre seg via sosiale nettverk av mennesker. I alle disse scenariene sprer en 'smitte' seg over koblingene til et komplekst nettverk, og endrer 'tilstandene' til nodene etter hvert som de sprer seg, enten gjenopprettelig eller på annen måte. For eksempel, i et epidemiologisk scenario, går individer fra "mottagelig" til "infisert" tilstand når infeksjonen sprer seg. Statene de enkelte nodene kan ta i eksemplene ovenfor kan være binære (for eksempel mottatt/ikke mottatt nyhet), diskrete (mottagelige/infiserte/gjenopprettede) eller til og med kontinuerlige (for eksempel andelen infiserte mennesker i en by ), mens smitten sprer seg. Felles trekk i alle disse scenariene er at smittespredning resulterer i endring av nodetilstander i nettverk. Perkoleringssentralitet (PC) ble foreslått med dette i bakhodet, som spesifikt måler viktigheten av noder når det gjelder å hjelpe perkolasjonen gjennom nettverket. Dette tiltaket ble foreslått av Piraveenan, Prokopenko & Hossain (2013) .

Perkoleringssentralitet er definert for en gitt node, på et gitt tidspunkt, som andelen "perkulerte stier" som går gjennom denne noden. En 'perkolert bane' er en korteste bane mellom et par noder, der kildenoden er perkolert (f.eks. Infisert). Målnoden kan være perkolert eller ikke-perkolert, eller i en delvis perkolert tilstand.

${\ displaystyle PC^{t} (v) = {\ frac {1} {N-2}} \ sum _ {s \ neq v \ neq r} {\ frac {\ sigma _ {sr} (v)} {\ sigma _ {sr}}} {\ frac {{x^{t}} _ {s}} {{\ sum {[{x^{t}} _ {i}}]}-{x^{ TV}}}}$

hvor er totalt antall korteste stier fra node til node og er antallet av de banene som passerer gjennom . Perkolasjonstilstanden til noden til enhver tid er angitt med og to spesielle tilfeller er når som indikerer en ikke-perkolert tilstand på et tidspunkt, mens når som indikerer en fullstendig perkolert tilstand til enhver tid . Verdiene i mellom indikerer delvis perkolerte stater (f.eks. I et nettverk av townships vil dette være prosentandelen av mennesker smittet i byen). ${\ displaystyle \ sigma _ {sr}}$${\ displaystyle s}$${\ displaystyle r}$${\ displaystyle \ sigma _ {sr} (v)}$${\ displaystyle v}$${\ displaystyle i}$${\ displaystyle t}$${\ displaystyle {x^{t}} _ {i}}$${\ displaystyle {x^{t}} _ {i} = 0}$${\ displaystyle t}$${\ displaystyle {x^{t}} _ {i} = 1}$${\ displaystyle t}$

De vedlagte vekter til perkoleringsbanene avhenger av perkoleringsnivåene som er tilordnet kildenodene, basert på forutsetningen at jo høyere perkolasjonsnivået til en kildeknute er, desto viktigere er banene som stammer fra den noden. Noder som ligger på korteste veier som stammer fra sterkt perkolerte noder, er derfor potensielt viktigere for perkolasjonen. Definisjonen av PC kan også utvides til også å omfatte målnodevekter. Beregninger av perkoleringssentralitet løper i tide med en effektiv implementering som er tatt i bruk fra Brandes raske algoritme, og hvis beregningen må ta i betraktning målnoder, er tiden i verste fall . ${\ displaystyle O (NM)}$${\ displaystyle O (N^{3})}$

Algoritmer

Beregning av sentraliteten mellom alle toppunktene i en graf innebærer å beregne de korteste banene mellom alle parene på en graf, noe som tar tid med Floyd - Warshall -algoritmen , modifisert for ikke bare å finne en, men telle alle korteste veier mellom to noder. På en sparsom graf kan Johnsons algoritme eller Brandes algoritme være mer effektiv, begge tar tid. På uvekte grafer tar det tid å beregne sentralitet mellom dem ved å bruke Brandes 'algoritme. ${\ displaystyle \ Theta (| V |^{3})}$${\ displaystyle O (| V |^{2} \ log | V |+| V || E |)}$${\ displaystyle O (| V || E |)}$

Ved beregning av sentralitet og nærhet mellom alle hjørner i en graf, antas det at grafer er uorienterte og forbundet med tillatelse til løkker og flere kanter. Når du spesifikt håndterer nettverksgrafer, er grafer ofte uten sløyfer eller flere kanter for å opprettholde enkle relasjoner (hvor kanter representerer forbindelser mellom to personer eller hjørner). I dette tilfellet vil bruk av Brandes 'algoritme dele de endelige sentralitetspoengene med 2 for å ta hensyn til at hver korteste bane telles to ganger.

En annen algoritme generaliserer Freemans mellomrom beregnet på geodesikk og Newmans mellomrom beregnet på alle veier, ved å introdusere en hyperparameter som styrer avveiningen mellom leting og utnyttelse. Tidskompleksiteten er antall kanter ganger antall noder i grafen.

En omtrentlig, sannsynlig estimering av sentraliteter mellom mellomrom kan oppnås mye raskere ved å prøve stier ved hjelp av et toveis bredde-første søk .

applikasjoner

Sosiale nettverk

I sosiale nettverksanalyser kan sentralitet mellom seksjoner ha forskjellige implikasjoner. Fra et makroskopisk perspektiv reflekterer brostillinger eller "strukturelle hull" (indikert med høy sentralitet mellom sentralitet) makt, fordi de lar personen i broposisjonen utøve kontroll (f.eks. Bestemme om den skal dele informasjon eller ikke) over personene den forbinder. mellom. Fra det mikroskopiske perspektivet til egonettverk (dvs. kun med tanke på førstegradsforbindelser), sammenfaller en sentral sentralitet på nettet med nominasjoner av nærmeste venner (dvs. sterke mellommenneskelige bånd ), fordi det gjenspeiler sosiale kapitalinvesteringer i forholdet når fjerne sosiale kretser (f.eks. familie og universitet) er bygd sammen (ofte som følge av en introduksjon av ego).

Elvenettverk

Mellomliggende sentralitet har blitt brukt til å analysere den topologiske kompleksiteten til elvenettverk .

Relaterte konsepter

Mellomliggende sentralitet er relatert til et nettverks tilkobling , i så høye som høye mellompunkter har potensial til å koble fra grafer hvis de fjernes (se kutt sett ).

Se også

• Sentralitet

Referanser

Bibliografi