Centralitet

Indikatoren for centralitet eller nærhed til centrum i grafteori og netværksanalyse bestemmer de vigtigste hjørner af grafen. Anvendelser af indikatoren bruges til at identificere den eller de mest indflydelsesrige personer i et socialt netværk , nøgleinfrastrukturknudepunkter på internettet eller storbynetværk og bærere af sygdommen. Begreber om centralitet oprindeligt udviklet i analysen af sociale netværk og mange termer for centralitet bruges til at måle sociologiske primære kilder [2] . Disse målinger må ikke forveksles med nodepåvirkningsmetrikker , som leder efter kvantitative karakteristika for påvirkningen af hver node i netværket.

Definition og beskrivelse af centralitetsindekser

Centralitetsindekser er svar på spørgsmålet "Hvad karakteriserer vigtigheden af et toppunkt?" Svaret gives i form af en funktion med reel værdi på grafens toppunkter, hvis værdier (forventet) giver en rangordning, der bestemmer de vigtigste noder [3] [4] [5] .

Ordet "betydning" har en bred vifte af betydninger, hvilket fører til mange forskellige definitioner af centralitet. Der er foreslået to kategoriseringsordninger. "Betydning" kan forstås i forhold til typen af flow gennem netværket. Dette gør det muligt at klassificere centralitet efter den type flow, der anses for vigtig [4] . "Betydning" kan alternativt forstås som deltagelse i netværkets integritet. Dette gør det muligt at klassificere centraliteter baseret på, hvordan de måler deltagelse [6] . Begge disse tilgange opdeler centraliteter i forskellige kategorier. En centralitet, der er egnet til én kategori, vil ofte være uegnet, når den anvendes til en anden kategori [4] .

Hvis centraliteter kategoriseres efter deres deltagelse, bliver det klart, at de fleste centraliteter tilhører samme kategori. Antallet af ruter, der stammer fra en given knude, er kun forskellig i, hvordan ruter bestemmes og tælles. Begrænsning af aftaler for denne gruppe gør det muligt at beskrive centraliteter på spektret af ruter fra længde et ( grad af forbindelse ) til ubegrænsede ruter ( grad af indflydelse ) [3] [7] . Den observation, at mange centraliteter deler disse forbindelser, forklarer det høje niveau af korrelation mellem disse indekser.

Beskrivelse af strømme i netværket

Et netværk kan opfattes som en beskrivelse af de veje, som noget flyder ad. Dette tillader beskrivelse baseret på flowtyper og stityper kodet af centralitet. Flowet kan være baseret på overførsler, hvor hvert udeleligt element går fra en node til en anden, svarende til levering af pakker fra posthuset til kundens hjem. I det andet tilfælde er der en gengivelse af elementet, der går videre til den næste knude, således at både kilden og målet har dette element. Et eksempel på en sådan sag er rygtespredning, hvor information deles privat, med både kilde og mål informeret i slutningen af processen. Det sidste tilfælde er parallel udbredelse, hvor et element udbredes gennem flere links på samme tid, svarende til en radioudsendelse, som giver den samme information til mange lyttere på samme tid [4] .

På samme måde kan stiens art begrænses til: Geodesics (korteste stier), stier (ingen toppunkt besøges mere end én gang, stier (hjørnepunkter kan besøges flere gange, men ingen kant krydses to gange) eller ruter (både toppunkter og kanter) kan forekomme flere gange) [4] .

Beskrivelse efter gangstruktur

En alternativ klassifikation kan udledes af den måde, centralitet er konstrueret på. Dette fører igen til en opdeling i to klasser - Radial eller Median. Radiale centraliteter tæller antallet af stier, der starter/slutter ved et givet toppunkt. Grader af forbindelse og grader af indflydelse er eksempler på radiale mål for centralitet, der tæller antallet af stier med en længde eller ubegrænset længde. Median centraliteter tæller de stier, der passerer gennem et givet vertex. Det kanoniske eksempel er graden af Freeman-formidling, antallet af korteste veje, der passerer gennem et givet vertex [6] .

På samme måde kan optællingen fange enten volumen eller længden af ruten. Volumen er det samlede antal ruter af en given type. Tre eksempler fra det foregående afsnit falder ind under denne kategori. Længden er afstanden fra et givet toppunkt til de andre toppunkter i grafen. Graden af nærhed til andre Freeman-knuder, den totale geodætiske afstand fra et givet toppunkt til alle andre toppunkter, er det bedst kendte eksempel [6] . Bemærk, at denne klassificering afhænger af typen af ruter, der beregnes (dvs. ruter, kredsløb, stier, geodætik).

Borgatti og Everett mente, at denne typologi giver en idé om, hvordan man sammenligner mål for centralitet. Centraliteter, der falder i samme celle i denne 2x2-klassifikation, er ens nok til at være acceptable alternativer, og man kan med rimelighed sammenligne, hvilken score der er bedst for et givet problem. Mål fra forskellige celler er dog helt forskellige. Enhver bestemmelse af relativ egnethed kan kun ske i en forudbestemt kontekst, hvilken kategori er mere egnet [6] .

Radiale volumetriske centraliteter, der findes på spektret

Beskrivelsen af rutestrukturen viser, at næsten alle de anvendte centraliteter er radial-volumetriske mål. Dette giver tillid til, at toppunktets centralitet er en funktion af centraliteten af de toppunkter, som den er forbundet med. Centraliteter er forskellige i den måde, de er forbundet på.

Bonacic viste, at hvis en association er defineret i form af stier, så kan en familie af centraliteter defineres i form af vejlængder under overvejelse [3] . Graden af forbindelse tæller antallet af ruter af længde 1, graden af indflydelse tæller ruter af ubegrænset længde. Alternative definitioner af foreninger er også mulige. Alfa-centralitet giver dig mulighed for at have eksterne kilder til indflydelse for hjørner. Estradas undergrafcentralitet tæller kun lukkede stier (trekanter, firkanter, ...).

Hjertet i sådanne mål er den observation, at graderne af den tilstødende matrix af en graf giver antallet af stier med længde lig med graden. På samme måde er matrixeksponenten tæt forbundet med antallet af stier af en given længde. En indledende transformation af tilstødende matrix tillader definitionen af en optælling af forskellige typer ruter. I begge tilgange kan toppunktets centralitet udtrykkes som en uendelig sum, eller

{\displaystyle \sum _{k=0}^{\infty}A_{R}^{k}\beta ^{k))

for matrixpotenser, eller

\sum _{k=0}^{\infty }{\frac {(A_{R}\beta )^{k}}{k!)}}

for matrixeksponenten, hvor

$k$ lig med rutens længde,
$A_{R}$ er den transformerede adjacency matrix, og
$\beta$ er en kompenserende parameter, der sikrer konvergensen af summen.

Familien af Bonacic-mål transformerer ikke tilstødende matrix. Alfa-centralitet erstatter tilstødende matrix med dens opløsning . Undergrafens centralitet erstatter tilstødende matrix med dens spor. Uanset den indledende transformation af tilstødende matrix, har alle disse tilgange en fælles begrænsende adfærd. Da det har en tendens til nul, konvergerer indekset til graden af forbindelse . Når man stræber efter den maksimale værdi, konvergerer indekset til graden af indflydelse [7] . $\beta$ $\beta$

Spilteoretisk centralitet

Et fælles træk ved de fleste af de ovennævnte standardmål er, at de evaluerer vigtigheden af en node, idet de kun fokuserer på den rolle, som noden spiller på egen hånd. I mange applikationer vil denne tilgang imidlertid ikke være tilstrækkelig, da nodeinteraktion kan detekteres, hvis der anvendes målinger på gruppeknudepunkter.

Overvej for eksempel problemet med at stoppe en epidemi. Ser man på netværksbilledet ovenfor, hvilke noder skal vaccineres? På baggrund af de ovenfor beskrevne tiltag ønsker vi at anerkende de knuder, der er vigtigst for spredningen af sygdommen. Det er måske ikke en god idé at bruge centralitetstilgange, der fokuserer på de individuelle egenskaber af noder. Noderne i det røde felt kan ikke alene stoppe sygdommens spredning, men set som en gruppe, ser vi tydeligt, at de kan stoppe sygdommen, hvis den starter i knuderne , , . Spilteoretiske centraliteter forsøger at tage højde for de beskrevne problemer og muligheder ved hjælp af spilteoriens redskaber. Fremgangsmåden foreslået af Michalak (et al.) [8] bruger Shapley-vektoren . På grund af kompleksiteten (i tid) ved at beregne Shapley-vektoren, investeres størstedelen af indsatsen på dette område i udviklingen af nye algoritmer og metoder, der er afhængige af den specifikke netværkstopologi og problemets særlige karakter. Denne tilgang kan reducere tidskompleksiteten af algoritmen fra eksponentiel til polynomium. $v_{1}$ ${\displaystyle v_{4))$ $v_{5}$

Vigtige begrænsninger

Centralitetsindekser har to vigtige begrænsninger, den ene er indlysende, den anden er subtil. En åbenlys begrænsning er, at centralitet, der er optimal for én anvendelse, ofte ikke er optimal for en anden. Desuden, hvis dette ikke var tilfældet, ville der ikke være behov for så mange forskellige centraliteter. En illustration af dette fænomen er givet af Crackhards drage , for hvilken tre forskellige forestillinger om centralitet giver tre forskellige mest centrale hjørner [9] .

En subtil begrænsning er, at der er en gennemgående misforståelse om, at toppunkts centralitet afspejler den relative betydning af toppunkter. Centralitetsindekser blev udviklet eksplicit til rangordning, hvilket gør det muligt at vælge de vigtigste hjørner [3] [4] . De gør det godt under de nævnte begrænsninger. De var ikke designet til at måle knob på en generel måde. For nylig er netværksfysikere begyndt at udvikle nodepåvirkningsmetrikker for at løse dette problem.

Fejlen er dobbelt. For det første, rangering kun i rækkefølge af hjørner, da deres betydning ikke afspejler forskellen i vigtighed mellem forskellige rangeringsniveauer. Denne kendsgerning kan afbødes ved at anvende Freemans centralitet på det pågældende mål for centralitet, hvilket giver en vis indsigt i nodernes betydning ud fra deres forskellige centralitetsscore. Desuden giver Freeman centralitet dig mulighed for at sammenligne nogle netværk med hensyn til indikatorer fra noderne med den højeste værdi [10] .

For det andet generaliserer egenskaber, der (korrekt) afspejler de vigtigste hjørner i et givent netværk/applikation, ikke nødvendigvis til resten af hjørnerne. For de fleste andre noder i netværket kan rangering være meningsløs [11] [12] [13] [14] . Dette forklarer for eksempel, hvorfor kun de første par resultater af en Google-billedsøgning vises i en passende rækkefølge. PageRank er et meget ustabilt mål, der ofte viser den modsatte rang efter en lille ændring i søgeparameteren [15] .

Selvom umuligheden af at generalisere centralitetsindekset til resten af netværket måske ikke virker indlysende ved første øjekast, følger det direkte af ovenstående definitioner. Komplekse netværk har en heterogen topologi. I hvor høj grad det optimale mål afhænger af netværksstrukturen af de vigtigste toppunkter, i det omfang det mål der er optimalt for sådanne toppunkter ikke er optimalt for resten af netværket [11] .

Forbindelse

Historisk set er det første og begrebsmæssigt enkleste koncept graden af forbindelse , som er defineret som antallet af links, der falder ind til en node (det vil sige antallet af links en node har). Graden kan fortolkes i forhold til nodens direkte risiko for at fange noget, der passerer gennem netværket (såsom en virus eller nogle oplysninger). I tilfælde af et rettet netværk (hvor forbindelserne er rettet), definerer vi normalt to forskellige mål for graden af tilslutning, nemlig in -degree og out -degree . Følgelig er in-graden antallet af forbindelser med noden, og out-graden er antallet af forbindelser af noden med andre noder. Når forbindelse er forbundet med et eller andet positivt aspekt, såsom venskab eller samarbejde, tolkes in-graden ofte som en slags popularitet, og out-graden som selskabelighed.

Graden af tilslutning af et toppunkt for en given graf med toppunkter og kanter er defineret som $v$ $G:=(V,E)$ $|V|$ $|E|$

C_{D}(v)=\deg(v)

Beregning af forbindelsesgraden for alle noder i en graf tager tid i den tætte tilstødende matrixrepræsentation af grafen og tid i den sparsomme matrixrepræsentation for kanter . $\Theta (V^{2})$ $\Theta (E)$

Definitionen af centralitet på knudeniveau kan udvides til hele grafen, og i dette tilfælde taler vi om grafcentralitet [10] . Lad være den node med den højeste grad af forbindelse i . Lad være en forbundet graf med noder, der maksimerer følgende værdi (med som den node med den højeste grad af forbindelse i ): $v*$ $G$ $X:=(Y,Z)$ $|Y|$ $y*$ $x$

H=\sum _{j=1}^{|Y|}[C_{D}(y*)-C_{D}(y_{j})]

Følgelig er graden af grafens centralitet lig med: $G$

C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})] }{H}}

Værdien er maksimal, når grafen indeholder en central knude, som alle andre knudepunkter er forbundet med ( stjernegraf ), i hvilket tilfælde $H$ $x$

H=(n-1)\cdot ((n-1)-1)=n^{2}-3n+2.

Således for enhver graf $G:=(V,E),$

C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})] }{|V|^{2}-3|V|+2}}

Nærhed til andre noder

I en forbundet graf er den normaliserede grad af nærhed af en knude lig med den gennemsnitlige længde af den korteste vej mellem knudepunktet og alle andre knudepunkter i grafen. Så jo mere central noden er, jo tættere er den på alle andre noder.

Graden af nærhed blev defineret af Alex Bavelas (1950) som afstandens gensidige [16] [17] , dvs.

C(x)={\frac {1}{\sum _{y}d(y,x)))

hvor er lig med afstanden mellem hjørnerne og . Men når man taler om graden af nærhed til andre noder, mener folk normalt dens normaliserede form, normalt opnået fra den foregående formel ved at gange med , hvor er lig med antallet af noder i grafen. Størrelse tillader sammenligning mellem noder af grafer af forskellige størrelser. $d(y,x)$ $x$ $y$ $N-1$ $N$

At tage afstanden fra eller til alle andre knudepunkter i betragtning er ikke anvendelig for urettede grafer, mens de i rettede grafer giver helt andre resultater. For eksempel kan et websted have en høj udgående nærhed, men en lav indgående nærhed).

Harmonisk centralitet

I en (ikke nødvendigvis forbundet) graf vender harmonisk centralitet operationerne for summering og inversion om ved bestemmelse af graden af nærhed:

H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)))

hvor , hvis der ikke er nogen vej fra til . Harmonisk centralitet kan normaliseres ved at dividere med , hvor er lig med antallet af noder i grafen. $1/d(y,x)=0$ $y$ $x$ $N-1$ $N$

Harmonisk centralitet blev foreslået af Marchiori og Lathora (2000) [18] , derefter uafhængigt af Dekker (2005) under navnet værdsat centralitet [19] og Rochat (2009) [ 20] .

Mæglingsgrad

Mediationsgraden er et mål for centraliteten af et toppunkt i en graf (der er også en kantmedieringsgrad , som ikke diskuteres her). Graden af mediering kvantificerer antallet af gange, en knude slår bro over den korteste vej mellem to andre knudepunkter. Graden af mediering blev introduceret af Linton Freeman som et mål for det kvantitative udtryk for en persons interaktion med andre mennesker i et socialt netværk [21] . I dette koncept har de toppunkter, der har størst sandsynlighed for at være på en tilfældigt valgt korteste vej mellem to tilfældigt valgte toppunkter, en høj grad af mediering.

Mediationsgraden af et toppunkt i en graf med toppunkter beregnes som følger: $v$ $G:=(V,E)$ $V$

For hvert par af hjørner ( s , t ) beregnes de korteste veje mellem dem .
Bestem for hvert par af hjørner ( s , t ) den brøkdel af korteste veje, der passerer gennem det pågældende toppunkt (her vertex v ).
Vi opsummerer disse andele over alle par af knudepunkter ( s , t ).

Mere kompakt kan graden af mediation repræsenteres som [22] :

{\displaystyle C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st))))

hvor er lig med det samlede antal korteste stier fra knude til knude , og er lig med antallet af sådanne stier, der passerer igennem . Graden af mediering kan normaliseres ved at dividere med antallet af par af knudepunkter uden v , hvilket er lig med for rettede grafer og lig med for urettede grafer . For eksempel i en ikke-rettet stjerne har det centrale toppunkt (som er indeholdt i enhver mulig korteste vej) formidlingsgrad (1 hvis normaliseret), mens bladene (som ikke er indeholdt i nogen korteste vej) har formidlingsgrad 0. ${\displaystyle \sigma _{st))$ $s$ $t$ $\sigma _{st}(v)$ $v$ $(n-1)(n-2)$ $(n-1)(n-2)/2$ $(n-1)(n-2)/2$

Fra et beregningsmæssigt synspunkt involverer både graden af mediering og graden af nærhed af alle hjørner i en graf at beregne de korteste veje mellem alle par af hjørner i grafen, hvilket tager tid, når man bruger Floyd-Warshall-algoritmen . Men på sparsomme grafer kan Johnsons algoritme være mere effektiv og køre i tide . Ved uvægtede grafer kan der udføres beregninger ved hjælp af Brandes-algoritmen [22] , hvilket tager tid . Typisk antager disse algoritmer, at graferne er urettede og forbundet med opløsningen af sløjfer og flere kanter. Når man arbejder med netværksgrafer, der repræsenterer simple forbindelser, der ofte ikke har sløjfer eller flere kanter (hvor kanterne repræsenterer forbindelser mellem mennesker). I dette tilfælde, ved brug af Brandes' algoritme, divideres det endelige centralitetsindeks med 2 for at tage højde for hver korteste vej, der tælles to gange [22] . $O(V^{3})$ $O(V^{2}\log V+VE)$ $O(VE)$

Grad af indflydelse

Graden af indflydelse er et mål for indflydelsen af en knude i netværket . Den tildeler relative scores til alle noder i netværket ud fra konceptet om, at links til high score noder bidrager mere til scoren for den pågældende node end det samme link til en low score node [23] [5] [5] . Googles PageRank og Katz 's nodecentralitet er varianter af graden af indflydelse [24] .

Brug af tilstødende matrix til at finde graden af indflydelse

For en given graf med toppunkter, lad være tilstødende matrix , det vil sige hvis toppunktet er forbundet med toppunktet , og ellers. Det relative toppunkt centralitetsindeks kan defineres som $G:=(V,E)$ $|V|$ $A=(a_{v,t})$ $a_{v,t}=1$ $v$ $t$ $a_{v,t}=0$ $v$

x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _ {t\in G}a_{v,t}x_{t}

hvor er mængden af naboer til toppunktet , og er en konstant. Efter mindre transformationer kan dette udtryk omskrives i vektornotation som en ligning for en egenvektor $M(v)$ $v$ $\lambda$

\mathbf {Ax} ={\lambda }\mathbf {x}

Generelt er der mange forskellige egenværdier , for hvilke der er en egenvektor, der ikke er nul. Fordi elementerne i tilstødende matrix er ikke-negative, er der en enkelt største egenværdi, der er reel og positiv, ifølge Frobenius-Perron-sætningen . Denne største egenværdi giver det ønskede mål for centralitet [23] . Den tilhørende egenvektorkomponent giver den relative centralitet af et toppunkt i netværket. Egenvektoren er defineret op til en faktor, således at kun forholdet mellem toppunktscentraliteter er fuldstændigt defineret. For at bestemme den absolutte værdi af eksponenten, er det nødvendigt at normalisere egenvektoren, for eksempel, så summen over alle hjørner er lig med 1 eller normalisere med det samlede antal hjørner n . Potensmetoden er en af mange egenværdiafledningsalgoritmer, som kan bruges til at finde denne dominerende egenvektor [24] . Desuden kan dette generaliseres, således at elementerne i matrix A kan være reelle tal, der repræsenterer styrken af bindingen, som i en stokastisk matrix . $\lambda$ $v^{th}$ $v$

Centralitet ifølge Katz

Centralitet ifølge Kac [25] er en generalisering af graden af sammenhæng. Forbindelse måler antallet af direkte naboer, og Kac-centraliteten måler antallet af alle noder, der kan forbindes med stier, mens fjerne noder straffes. Matematisk defineres denne centralitet som

x_{i}=\sum _{k=1}^{\infty}\sum _{j=1}^{N}\alpha ^{k}(A^{k})_{ji}

hvor er en dæmpningsmultiplikator fra intervallet . $\alfa$ $(0,1)$

Ifølge Katz kan centralitet ses som en variant af graden af indflydelse. En anden form for centralitet ifølge Kac er

x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).

Sammenlignet med graden af indflydelse erstattes den af $x_{j}$ $x_{j}+1.$

Det blev vist [26] , at hovedegenvektoren (svarende til den største egenværdi af tilstødende matrix ) er Kac centralitetsgrænsen, når k nærmer sig nedefra. $EN$ $\alfa$ ${\tfrac {1}{\lambda ))$

PageRank

PageRank opfylder følgende lighed

x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)))+{\frac {1-\alpha }{N}} ,

hvor

{\displaystyle L(j)=\sum _{i}a_{ji))

er lig med antallet af naboer til noden (eller antallet af udgående forbindelser i den rettede graf). Sammenlignet med Katz' grad af indflydelse og centralitet er skaleringsfaktoren en vigtig forskel . Forskellen mellem PageRank og grad af indflydelse ligger i, at PageRank-vektoren er en venstre egenvektor (det vil sige en egenvektor af den transponerede matrix, bemærk at multiplikatoren har den omvendte rækkefølge af indekser) [27] . $j$ $L(j)$ ${\displaystyle a_{ji))$

Perkolationscentralitet

Der er en række mål for centralitet til at bestemme "betydningen" af en enkelt node i et komplekst netværk. Men de afspejler vigtigheden af en node rent topologisk, og værdien af en node afhænger ikke på nogen måde af nodens "tilstand". Værdien forbliver konstant uanset netværkets dynamik. Dette gælder selv for afmålte mæglingsforanstaltninger. En node kan dog også være centralt placeret med hensyn til grad af formidling eller anden centralitetsmål, men ikke være "centralt placeret" i sammenhæng med et netværk, hvor der er lækage. Lækage af "infektion" forekommer i komplekse netværk i et stort antal scenarier. En viral eller bakteriel infektion kan spredes gennem folks sociale netværk, kendt som kontaktnetværk. Spredning af sygdom kan også ses på et højt abstraktionsniveau ved at overveje et netværk af byer eller befolkningscentre forbundet med veje, jernbaner eller flyselskaber. Computervirus kan spredes over computernetværk. Rygter eller nyheder om erhvervstilbud og -aftaler kan også spredes gennem folks sociale medier. I alle disse scenarier spredes "infektionen" gennem forbindelserne i et komplekst netværk, og ændrer "tilstandene" af noderne reversibelt eller irreversibelt. For eksempel, i et epidemiologisk scenarie, bevæger individer sig fra den "modtagelige" tilstand til den "inficerede" tilstand. Tilstandene for specifikke noder som "smitte"-spredninger kan antage binære værdier (såsom "en nyhed modtaget/ikke modtaget"), diskrete værdier (modtagelige/inficerede/helbredte) eller endda kontinuerlige værdier (såsom andelen af smittede i byen). Det fælles i alle disse scenarier er, at spredningen af "infektionen" fører til en ændring i netværksknudernes tilstand. Med dette in mente er der foreslået percolation centrality (PC) , som måler vigtigheden af en node i forhold til at bidrage til perkolation gennem netværket. Denne foranstaltning blev foreslået af Pairavinan et al . [28] .

Nedsivningscentralitet defineres for en given knude og på et givet tidspunkt som andelen af "sivningsstier", der passerer gennem knudepunktet. En "lækagevej" er den korteste vej mellem et par knudepunkter, hvor kildenoden er i en lækagetilstand (f.eks. inficeret). Målknuden kan være i en perkolationstilstand, en ikke-perkolationstilstand eller en delvis perkolationstilstand.

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^{ t}}_{v}}}

hvor er det samlede antal korteste stier fra knude til knude , og er antallet af sådanne stier, der går igennem . En nodes lækagetilstand på et tidspunkt betegnes som, og der er to specielle tilfælde, når som indikerer en stram tilstand på et tidspunkt , og når , som indikerer fuld lækage på et tidspunkt . Værdier mellem disse værdier betyder delvise nedsivningstilstande (for eksempel i et netværk af byer kan dette være procentdelen af inficerede mennesker i byen). ${\displaystyle \sigma _{sr))$ $s$ $r$ $\sigma _{sr}(v)$ $v$ $jeg$ $t$ ${x^{t}}_{i}$ ${x^{t}}_{i}=0$ $t$ ${x^{t}}_{i}=1$ $t$

Vægtene af lækagevejene afhænger af lækageniveauerne, der er tildelt kildeknudepunkterne, baseret på postulatet om, at jo højere lækniveauet for kildeknuden er, desto vigtigere er stierne, der udgår fra den knude. Noder, der ligger på de korteste veje, der starter ved noder med høj perkolation, er derfor potentielt vigtigere for perkolation. Definitionen af PC kan også udvides til også at omfatte målknudevægte. Beregningen af lækagecentralitet udføres i tide med en effektiv implementering lånt fra den hurtige Brandes-algoritme, og hvis beregningerne kræver, at der tages hensyn til vægten af endeknuderne, er den værste tid . $O(NM)$ $O(N^{3})$

Krydsklik centralitet

Krydsklikens centralitet af en individuel knude i en kompleks graf bestemmer knudepunktets forbindelser til forskellige kliker . En node med høj krydsklik-centralitet fremmer spredningen af information eller sygdom i grafen. Kliker er undergrafer, hvor hver node er forbundet med alle andre kliknoder. Krydsklik-centraliteten af en knude for en given graf med toppunkter og kanter er angivet som og lig med antallet af kliker, som toppunktet tilhører. Denne foranstaltning blev brugt i Faganis papir [29] , men blev først foreslået af Everett og Borgatti i 1998 under navnet "klik overlap centralitet". $v$ $G:=(V,E)$ $|V|$ $|E|$ $X(v)$ $v$

Freeman centralitet

Centraliteten af ethvert netværk er et mål for, hvor centralt dets mest centrale knudepunkt er sammenlignet med andre knudepunkter [10] . Målingen af centralitet bliver derefter (a) beregnet som summen af centralitetsforskellene mellem den mest centrale knude i netværket og alle andre knudepunkter, og (b) dividere denne værdi med den teoretisk største sum af forskelle i ethvert netværk af samme størrelse [10] . Så kan ethvert centralitetsmål have sit eget centralitetsmål. Formelt set, hvis er centralitetsmålet for punktet , hvis er det største sådan mål i netværket, og hvis $C_{x}(p_{i})$ $jeg$ $C_{x}(p_{*})$

\max \sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})

er den største sum af forskelle i punktcentralitet for enhver graf med det samme antal noder, så er netværkets centralitet [10] $C_{x}$

C_{x}={\frac {\sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}{\max \ sum _{i=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})}}.

Forskelsbaserede mål for centralitet

For at få bedre resultater i at rangere noderne i et givet netværk, bruger Alvarez-Socorro (et al.) [30] et mål for ulighed (karakteristisk for klassifikationsteori og dataanalyse) til at forbedre målingen af centralitet i komplekse netværk. Dette er illustreret ved graden af indflydelse ved at beregne centraliteten af hver knude ved at løse egenværdiproblemet

W\mathbf {c} =\lambda \mathbf {c}

where (koordinatmæssigt produkt), og er en vilkårlig ulighedsmatrix , defineret i forhold til ulighedsmålet. For eksempel gennem Jaccards ulighed givet af formlen $W_{ij}=A_{ij}D_{ij}$ ${\displaystyle D_{ij))$

D_{ij}=1-{\dfrac {|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\kop V^{ +}(j)|}}

Dette mål giver os mulighed for at kvantificere det topologiske bidrag (derfor kaldet bidragscentralitet) af hver knude til centraliteten af en given knude, hvilket opnår et større vægt/betydningsforhold for de knudepunkter med større ulighed, da dette tillader en given knude at nå knudepunkter, som ikke kan nås direkte.

Bemærk, at det er ikke-negativt, da og er ikke-negative matricer, så vi kan bruge Frobenius-Perron-sætningen til at sikre, at løsningen på problemet ovenfor er unik for med ikke-negativ c , hvilket giver os mulighed for at opnå centraliteten af hver node i netværket. Således er centraliteten af den i-te node lig med $W$ $EN$ $D$ ${\displaystyle \lambda =\lambda _{max))$

c_{i}={\dfrac {1}{n}}\sum _{j=1}^{n}W_{ij}c_{j},\,\,\,\,\,\ ,j=1,\cdots ,n

hvor er lig med antallet af netværksknuder. Nogle netværk og ulighedsmål blev testet af Alvarez-Socorro (et al.) [31] og forbedrede resultater blev opnået i de undersøgte tilfælde. $n$

Generaliseringer

Empiriske og teoretiske undersøgelser generaliserer begrebet centralitet i sammenhæng med statiske netværk til dynamiske centraliteter [32] i sammenhæng med tidsafhængige og kortlivede netværk [33] [34] [35] .

For en generalisering til vægtede netværk, se Opsal et al . [36] .

Begrebet centralitet er også blevet generaliseret til gruppeniveau. For eksempel viser graden af gruppeformidling andelen af geodætiske links af par (det vil sige stier med minimum længde) af noder, der ikke tilhører gruppen, der passerer gennem gruppen [37] [38] .

Se også

Noter

↑ En del af terminologien er hentet fra artiklen af A. S. Semenov og M. V. Bartosh "ESTIMATION OF THE STABILITY OF THE INTERNET OF THINGS NETWORK USING INDICATORS OF CENTRALITY OF RELATIONS" . Vilkårene i litteraturen på russisk er ikke faldet til ro. Så i artiklen af Evin I. A. Complex networks: En introduktion til teorien , i stedet for udtrykket "grad af mediation", bruges udtrykkene "node load", "forbindelser med maksimal betydning". På siden Network Metrics bruges i stedet for udtrykket "grad af forbindelse", den bogstavelige oversættelse "centralitet efter grad" i stedet for udtrykkene "grad af ..." - "centralitet ved ...". Nogle gange bruges udtrykket "centralitet" i stedet for udtrykket "centralitet".
↑ Newman, 2010 .
↑ 1 2 3 4 Bonacich, 1987 , s. 1170-1182.
↑ 1 2 3 4 5 6 Borgatti, 2005 , s. 55-71.
↑ 1 2 3 Negre, Morzan, Hendrickson et al., 2018 , s. E12201-E12208.
↑ 1 2 3 4 Borgatti, Everett, 2006 , s. 466-484.
↑ 1 2 Benzi, Klymko, 2013 , s. 686-706.
↑ Michalak, Aadithya, Szczepański, Ravindran, Jennings, 2013 , s. 607-650.
↑ Krackhardt, 1990 , s. 342-369.
↑ 1 2 3 4 5 Freeman, 1979 , s. 215-239.
↑ 12 Advokat , 2015 , s. 8665.
↑ da Silva, Viana, da F. Costa, 2012 , s. P07005.
↑ Bauer og Lizier, 2012 , s. 68007.
↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , s. 1-13.
↑ Ghoshal, Barabsi, 2011 , s. 394.
↑ Bavelas, 1950 , s. 725-730.
↑ Sabidussi, 1966 , s. 581-603.
↑ Marchiori, Latora, 2000 , s. 539-546.
↑ Dekker, 2005 .
↑ Rochat, 2009 .
↑ Freeman, 1977 , s. 35-41.
↑ 1 2 3 Brandes, 2001 , s. 163-177.
↑ 12 Newman , 2007 , s. 1-12.
↑ 12 American Mathematical Society . (ubestemt)
↑ Katz, 1953 , s. 39-43.
↑ Bonacich, 1991 , s. 155-168.
↑ Hvordan rangerer Google websider? Arkiveret fra originalen den 31. januar 2012. 20Q: Om Networked Life
↑ Piraveenan, Prokopenko, Hossain, 2013 , s. e53095.
↑ Faghani, 2013 , s. 1815-1826
↑ Alvarez-Socorro, Herrera-Almarza, González-Díaz, 2015 , s. 17095.
↑ Alvarez-Socorro AJ, Herrera-Almarza LA, González-Díaz. Supplerende information om egencentralitet baseret på ulighedsmål afslører centrale knudepunkter i komplekse netværk . Nature Publishing Group. (ubestemt)
↑ Braha, Bar-Yam, 2006 , s. 59-63.
↑ Hill, Braha, 2010 , s. 046105.
↑ Gross, Sayama, 2009 .
↑ Holme, Saramaki, 2013 .
↑ Opsahl, Agneessens, Skvoretz, 2010 , s. 245-251.
↑ Everett, Borgatti, 2005 , s. 57-76.
↑ Puzis, Yagil, Elovici, Braha, 2009 .

Litteratur

Newman MEJ Networks: En introduktion. — Oxford, Storbritannien: Oxford University Press, 2010.
Newman MEJ The mathematics of networks, // The New Palgrave Encyclopedia of Economics . — Basingstoke, Palgrave Macmillan, 2007.

Philip Bonacich. Magt og centralitet: En familie af foranstaltninger // American Journal of Sociology. - 1987. - T. 92 , no. 5 . - doi : 10.1086/228631 .
Bonacich P. Samtidig gruppe- og individuelle centraliteter // Sociale netværk. - 1991. - T. 13 , no. 2 . - doi : 10.1016/0378-8733(91)90018-o .
Stephen P. Borgatti. Centralitet og netværksflow // Sociale netværk. - 2005. - T. 27 . - doi : 10.1016/j.socnet.2004.11.008 .
Christian F. A. Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista. Egenvektorcentralitet til karakterisering af proteinallosteriske veje // Proceedings of the National Academy of Sciences. - 2018. - T. 115 . - doi : 10.1073/pnas.1810452115 .
Stephen P. Borgatti, Martin G. Everett. Et grafteoretisk perspektiv på centralitet // Sociale netværk. - 2006. - T. 28 , no. 4 . - doi : 10.1016/j.socnet.2005.11.005 .
Michele Benzi, Christine Klymko. En matrixanalyse af forskellige centralitetsmål // SIAM Journal on Matrix Analysis and Applications. - 2013. - T. 36 , no. 2 . - doi : 10.1137/130950550 . - arXiv : 1312.6722 .
Tomasz P. Michalak, Karthik V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Nicholas R. Jennings. Effektiv beregning af Shapley-værdien for spilteoretisk netværkscentralitet // Journal of Artificial Intelligence Research. - 2013. - T. 46 .
David Krackhardt. Vurdering af det politiske landskab: struktur, erkendelse og magt i organisationer // Administrative Science Quarterly. - 1990. - Juni ( bind 35 , hæfte 2 ). - doi : 10.2307/2393394 . — .
Renato da Silva, Matheus Viana, Luciano da F. Costa. Forudsigelse af epidemi ud fra individuelle træk ved sprederene // J. Stat. Mek.: Teorieksp.. - 2012. - T. 2012 . - doi : 10.1088/1742-5468/2012/07/p07005 . - . - arXiv : 1202.0024 .
Frank Bauer, Joseph Lizier. Identifikation af påvirkende spredere og effektiv estimering af infektionstal i epidemiske modeller: En gåtællertilgang // Europhys Lett. - 2012. - T. 99 . - S. 68007 . - doi : 10.1209/0295-5075/99/68007 . - . - arXiv : 1203.0502 .
Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefanic. Epidemisk centralitet -- er der en undervurderet epidemisk effekt af netværks perifere knuder? // The European Physical Journal B. - 2013. - T. 86 , nr. 10 . - doi : 10.1140/epjb/e2013-31025-5 . - arXiv : 1110.2558 .
Ghoshal G., Barabsi AL Rangeringsstabilitet og superstabile noder i komplekse netværk. // NatCommun. - 2011. - T. 2 . - doi : 10.1038/ncomms1396 . — .
Glenn advokat. Forstå spredningskraften af alle noder i et netværk: et kontinuerligt tidsperspektiv //Sci Rep. - 2015. - T. 5 . - doi : 10.1038/srep08665 . - . - arXiv : 1405.6707 . — PMID 25727453 .
Linton C. Freeman. Centralitet i sociale netværk: Begrebsafklaring // Sociale netværk. - 1979. - Bind 1 , udgave. 3 . — S. 215–239 . - doi : 10.1016/0378-8733(78)90021-7 . Arkiveret fra originalen den 22. februar 2016.
Linton Freeman. Et sæt af mål for centralitet baseret på mellemhed // Sociometri. - 1977. - T. 40 , no. 1 . — s. 35–41 . - doi : 10.2307/3033543 . — .
Alex Bavelas. Kommunikationsmønstre i opgaveorienterede grupper // J. Acoust. soc. Er. - 1950. - T. 22 , no. 6 .
Sabidussi G. Sabidussi. Centralitetsindekset for en graf // Psykometri. - 1966. - T. 31 , no. 4 . - doi : 10.1007/bf02289527 . — PMID 5232444 .
Massimo Marchiori, Vito Latora. Harmony in the small-world // Physica A: Statistical Mechanics and its Applications. - 2000. - T. 285 , no. 3–4 . - doi : 10.1016/s0378-4371(00)00311-3 . - . - arXiv : cond-mat/0008357 .
Anthony Decker. Conceptual Distance in Social Network Analysis // Journal of Social Structure. - 2005. - T. 6 , no. 3 .
Yannick Rochat. Nærhedscentralitet udvidet til uforbundne grafer: Det harmoniske centralitetsindeks // Applications of Social Network Analysis, ASNA 2009 . – 2009.
Ulrik Brandes. En hurtigere algoritme for centralitet mellemhed // Journal of Mathematical Sociology. - 2001. - T. 25 , no. 2 . - doi : 10.1080/0022250x.2001.9990249 .
Newman MEJ Netværks matematik .
Katz L. Et nyt statusindeks afledt af Sociometrisk Indeks // Psykometri. - 1953. - S. 39-43 .
Piraveenan M., Prokopenko M., Hossain L. Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks // PLOS ONE. - 2013. - T. 8 , no. 1 . - doi : 10.1371/journal.pone.0053095 . - . — PMID 23349699 .
Mohamamd Reza Faghani. En undersøgelse af XSS-ormudbredelse og -detektionsmekanismer i online sociale netværk // IEEE-transaktioner om informationsforensik og sikkerhed. - 2013. - T. 8 , no. 11 . - doi : 10.1109/TIFS.2013.2280884 .
Alvarez-Socorro AJ, Herrera-Almarza GC, González-Díaz LA Egencentralitet baseret på ulighedsmål afslører centrale knudepunkter i komplekse netværk // Videnskabelige rapporter. - 2015. - November ( bind 5 ). - doi : 10.1038/srep17095 . - . — PMID 26603652 .
Braha D., Bar-Yam Y. Fra centralitet til midlertidig berømmelse: Dynamisk centralitet i komplekse netværk // kompleksitet. - 2006. - T. 12 , no. 2 . - doi : 10.1002/cplx.20156 . - . - arXiv : fysik/0611295 .
Hill SA, Braha D. Dynamic Model of Time-Dependent Complex Networks // Physical Review E. - 2010. - Vol. 82 , no. 4 . - doi : 10.1103/physreve.82.046105 . - . - arXiv : 0901.4407 . — PMID 21230343 .
Adaptive Networks: Theory, Models and Applications / Gross T., Sayama H.. - Springer, 2009.
Holme P., Saramaki J. Temporal Networks. — Springer, 2013.
Tore Opsahl, Filip Agneessens, John Skvoretz. Node centralitet i vægtede netværk: Generalisering af grad og korteste veje // Sociale netværk. - 2010. - T. 32 , no. 3 . - doi : 10.1016/j.socnet.2010.03.006 . Arkiveret fra originalen den 26. februar 2018.
Everett MG, Borgatti SP Udvider centralitet. I PJ Carrington, J. Scott og S. Wasserman (red.) // Modeller og metoder i analyse af sociale netværk. - New York: Cambridge University Press, 2005. - S. 57-76.
Puzis R., Yagil D., Elovici Y., Braha D. Samarbejdet angreb på internetbrugeres anonymitet // Internet Research. - 2009. - T. 19 , no. 1 . Arkiveret fra originalen den 7. december 2013.

Læsning for yderligere læsning

Koschützki, D.; Lehmann, K.A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. og Zlotowski, O. (2005) Centralitetsindekser. I Brandes, U. og Erlebach, T. (red.) Network Analysis: Methodological Foundations , pp. 16-61, LNCS 3418, Springer-Verlag.