Centralitet

Indikatorn på centralitet eller närhet till centrum i grafteori och nätverksanalys bestämmer de viktigaste hörnen i grafen. Tillämpningar av indikatorn används för att identifiera den eller de mest inflytelserika personerna i ett socialt nätverk , viktiga infrastrukturnoder på Internet eller storstadsnätverk och bärare av sjukdomen. Centralitetsbegrepp som ursprungligen utvecklades i analysen av sociala nätverk och många termer av centralitet används för att mäta sociologiska primärkällor [2] . Dessa mätvärden ska inte förväxlas med nodpåverkansmått , som letar efter kvantitativa egenskaper för påverkan från varje nod i nätverket.

Definition och beskrivning av centralitetsindex

Centralitetsindex är svar på frågan "Vad kännetecknar vikten av en vertex?" Svaret ges i termer av en verkligt värderad funktion på grafens hörn, vars värden (förväntat) ger en rangordning som bestämmer de viktigaste noderna [3] [4] [5] .

Ordet "viktighet" har ett brett spektrum av betydelser, vilket leder till många olika definitioner av centralitet. Två kategoriseringssystem har föreslagits. "Viktighet" kan förstås i relation till typen av flöde genom nätet. Detta gör att centralitet kan klassificeras efter vilken typ av flöde som anses viktigt [4] . "Viktighet" kan alternativt förstås som deltagande i nätverkets integritet. Detta gör att centraliteter kan klassificeras utifrån hur de mäter deltagande [6] . Båda dessa synsätt delar in centraliteter i olika kategorier. En centralitet som är lämplig för en kategori kommer ofta att vara olämplig när den tillämpas på en annan kategori [4] .

Om centraliteter kategoriseras efter deras deltagande, blir det tydligt att de flesta centraliteter tillhör samma kategori. Antalet rutter som kommer från en given nod skiljer sig endast i hur rutter bestäms och räknas. Begränsning av avtal för denna grupp tillåter beskrivning av centraliteter på spektrumet av rutter från längd ett ( grad av anslutning ) till obegränsade rutter ( grad av inflytande ) [3] [7] . Observationen att många centraliteter delar dessa länkar förklarar den höga nivån av korrelation mellan dessa index.

Beskrivning av flöden i nätverket

Ett nätverk kan ses som en beskrivning av de vägar som något flyter på. Detta tillåter beskrivning baserad på flödestyper och vägtyper kodade av centralitet. Flödet kan baseras på överföringar, där varje odelbart element går från en nod till en annan, liknande leverans av paket från posten till kundens hem. I det andra fallet finns det en reproduktion av elementet som går till nästa nod, så att både källan och målet har detta element. Ett exempel på ett sådant fall är ryktesspridning, där information delas privat, med både källa och mål informerade i slutet av processen. Det sista fallet är parallell spridning, där ett element sprids genom flera länkar samtidigt, liknande en radiosändning, som ger samma information till många lyssnare samtidigt [4] .

På liknande sätt kan typen av väg begränsas till: Geodesics (kortaste vägarna), stigar (ingen vertex besöks mer än en gång, stigar (hörn kan besökas flera gånger, men ingen kant korsas två gånger) eller rutter (både hörn och kanter kan förekomma flera gånger) [4] .

Beskrivning av gångstruktur

En alternativ klassificering kan härledas från hur centralitet är konstruerad. Detta leder återigen till en uppdelning i två klasser - Radial eller Median. Radiella centraliteter räknar antalet banor som börjar/slutar vid en given vertex. Grader av anslutning och grader av påverkan är exempel på radiella mått på centralitet, som räknar antalet banor med längd en eller obegränsad längd. Mediancentraliteter räknar vägarna som passerar genom en given vertex. Det kanoniska exemplet är graden av Freeman-medling, antalet kortaste vägar som passerar genom en given vertex [6] .

På samma sätt kan räkningen fånga antingen volymen eller längden på rutten. Volym är det totala antalet rutter av en given typ. Tre exempel från föregående stycke faller inom denna kategori. Längden är avståndet från en given vertex till de andra hörnen i grafen. Graden av närhet till andra Freeman-noder, det totala geodetiska avståndet från en given vertex till alla andra hörn, är det mest kända exemplet [6] . Observera att denna klassificering beror på vilken typ av rutter som beräknas (dvs. rutter, kretsar, stigar, geodetik).

Borgatti och Everett menade att denna typologi ger en uppfattning om hur man jämför mått på centralitet. Centraliteter som faller i samma cell i denna 2x2-klassificering är tillräckligt lika för att vara acceptabla alternativ, och man kan rimligen jämföra vilken poäng som är bäst för ett givet problem. Mått från olika celler är dock helt olika. Varje bestämning av relativ lämplighet kan endast ske i ett förutbestämt sammanhang, vilken kategori är lämpligast [6] .

Radiella volymetriska centraliteter som finns på spektrumet

Beskrivningen av sträckningsstrukturen visar att nästan alla centraliteter som används är radiell-volymetriska mått. Detta ger förtroende för att vertexcentraliteten är en funktion av centraliteten hos de hörn som den är associerad med. Centraliteter skiljer sig åt i hur de är förknippade.

Bonacic visade att om en förening definieras i termer av vägar, så kan en familj av centraliteter definieras i termer av väglängder under övervägande [3] . Anslutningsgraden räknar antalet rutter av längd ett, graden av påverkan räknar rutter med obegränsad längd. Alternativa definitioner av föreningar är också möjliga. Alpha-centrality låter dig ha externa källor för inflytande för hörn. Estradas subgrafcentralitet räknar endast slutna banor (trianglar, fyrhörningar, ...).

Kärnan i sådana mått är observationen att graderna i en grafs närliggande matris ger antalet banor med längden lika med graden. På liknande sätt är matrisexponenten nära relaterad till antalet banor av en given längd. En initial transformation av närliggande matris tillåter definitionen av ett antal olika typer av rutter. I båda tillvägagångssätten kan vertexcentralitet uttryckas som en oändlig summa, eller

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

för matrispotenser, eller

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

för matrisexponenten, där

$k$ lika med ruttens längd,
$A_{R}$ är den transformerade närliggande matrisen, och
$\beta$ är en kompenserande parameter som säkerställer konvergensen av summan.

Familjen av Bonacic-mått omvandlar inte närliggande matris. Alpha centrality ersätter närliggande matris med dess upplösning . Subgrafens centralitet ersätter närliggande matris med dess spår. Oavsett den initiala transformationen av närliggande matris, har alla dessa tillvägagångssätt ett gemensamt begränsande beteende. Eftersom det tenderar till noll konvergerar indexet till graden av anslutning . När man strävar efter maximalt värde konvergerar indexet till graden av påverkan [7] . $\beta$ $\beta$

Spelteoretisk centralitet

Gemensamt för de flesta av ovanstående standardmått är att de utvärderar vikten av en nod, och fokuserar endast på den roll som noden spelar på egen hand. Men i många applikationer kommer detta tillvägagångssätt inte att vara adekvat, eftersom nodinteraktion kan detekteras om åtgärder tillämpas på gruppnoder.

Tänk till exempel på problemet med att stoppa en epidemi. Om du tittar på nätverksbilden ovan, vilka noder ska vaccineras? Utifrån de åtgärder som beskrivits ovan vill vi känna igen de noder som är viktigast för spridningen av sjukdomen. Att använda enbart centralitetsmetoder som fokuserar på nodernas individuella egenskaper kanske inte är en bra idé. Noderna i den röda rutan kan inte enbart stoppa spridningen av sjukdomen, men sett som en grupp ser vi tydligt att de kan stoppa sjukdomen om den börjar i noderna , , . Spelteoretiska centraliteter försöker ta hänsyn till de beskrivna problemen och möjligheterna med hjälp av spelteorin. Tillvägagångssättet som föreslagits av Michalak (et al.) [8] använder Shapley-vektorn . På grund av komplexiteten (i tiden) med att beräkna Shapley-vektorn, investeras det mesta av ansträngningen inom detta område i utvecklingen av nya algoritmer och metoder som förlitar sig på den specifika nätverkstopologin och problemets speciella karaktär. Detta tillvägagångssätt kan reducera tidskomplexiteten för algoritmen från exponentiell till polynom. $v_{1}$ ${\displaystyle v_{4))$ $v_{5}$

Viktiga begränsningar

Centralitetsindex har två viktiga begränsningar, den ena är uppenbar, den andra är subtil. En uppenbar begränsning är att centralitet som är optimal för en tillämpning ofta inte är optimal för en annan. Om så inte var fallet skulle det dessutom inte behövas så många olika centraliteter. En illustration av detta fenomen ges av Crackhards drake , för vilken tre olika begrepp om centralitet ger tre olika mest centrala hörn [9] .

En subtil begränsning är att det finns en genomgripande missuppfattning att vertex centralitet återspeglar den relativa betydelsen av hörn. Centralitetsindex utvecklades explicit för rangordning, vilket gör det möjligt att välja de viktigaste hörnen [3] [4] . De gör det bra under de nämnda begränsningarna. De var inte utformade för att mäta knutar på ett allmänt sätt. Nyligen har nätverksfysiker börjat utveckla nodpåverkansmått för att lösa detta problem.

Felet är dubbelt. För det första, rangordning endast efter hörn, eftersom deras betydelse inte speglar skillnaden i betydelse mellan olika rangordningsnivåer. Detta faktum kan mildras genom att tillämpa Freemans centralitet på centralitetsmåttet i fråga, vilket ger en viss inblick i nodernas betydelse genom deras olika centralitetspoäng. Dessutom låter Freeman centralitet dig jämföra vissa nätverk när det gäller indikatorer från noderna med det högsta värdet [10] .

För det andra, egenskaper som (korrekt) återspeglar de viktigaste hörnen i ett givet nätverk/applikation generaliserar inte nödvändigtvis till resten av hörnen. För de flesta andra noder i nätverket kan rangordning vara meningslös [11] [12] [13] [14] . Detta förklarar till exempel varför bara de första få resultaten av en bildsökning på Google visas i lämplig ordning. PageRank är ett mycket instabilt mått som ofta visar motsatt rankning efter en liten ändring i sökparametern [15] .

Även om omöjligheten att generalisera centralitetsindexet till resten av nätverket kanske inte verkar uppenbart vid första anblicken, följer det direkt av ovanstående definitioner. Komplexa nätverk har en heterogen topologi. I vilken utsträckning det optimala måttet beror på nätverksstrukturen för de viktigaste hörnen, i den mån det mått som är optimalt för sådana hörn inte är optimalt för resten av nätet [11] .

Anslutningar

Historiskt sett är det första och begreppsmässigt enklaste konceptet graden av anslutning , vilket definieras som antalet länkar som inträffar till en nod (det vill säga antalet länkar som en nod har). Graden kan tolkas i termer av nodens direkta risk att fånga något som passerar genom nätverket (som ett virus eller någon information). När det gäller ett riktat nätverk (där länkarna är riktade) definierar vi vanligtvis två olika mått på graden av uppkoppling, nämligen i -grad och ut -grad . Följaktligen är in-graden antalet anslutningar med noden, och ut-graden är antalet anslutningar av noden med andra noder. När anknytning förknippas med någon positiv aspekt, såsom vänskap eller samarbete, tolkas in-graden ofta som en sorts popularitet, och out-graden som sällskaplighet.

Graden av anslutning av en vertex för en given graf med hörn och kanter definieras som $v$ $G:=(V,E)$ $|V|$ $|E|$

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

Att beräkna graden av anslutning för alla noder i en graf tar tid i den täta närliggande matrisrepresentationen av grafen och tid i den glesa matrisrepresentationen för kanter . $\Theta (V^{2})$ $\Theta (E)$

Definitionen av centralitet på nodnivå kan utökas till hela grafen, och i det här fallet talar vi om grafcentralitet [10] . Låt vara den nod med den högsta graden av anslutning i . Låt vara en sammankopplad graf med noder som maximerar följande värde (med som noden med den högsta graden av anslutning i ): $v*$ $G$ $X:=(Y,Z)$ $|Y|$ $y*$ $X$

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

Följaktligen är graden av grafens centralitet lika med: $G$

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

Värdet är maximalt när grafen innehåller en central nod som alla andra noder är anslutna till ( stjärndiagram ), i vilket fall $H$ $X$

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

Alltså för vilken graf som helst $G:=(V,E),$

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

Närhet till andra noder

I en ansluten graf är den normaliserade graden av närhet för en nod lika med medellängden på den kortaste vägen mellan noden och alla andra noder i grafen. Ju mer central noden är, desto närmare är den alla andra noder.

Graden av närhet definierades av Alex Bavelas (1950) som avståndets reciproka [16] [17] , dvs.

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

där är lika med avståndet mellan hörnen och . Men när man talar om graden av närhet till andra noder menar folk vanligtvis dess normaliserade form, vanligtvis erhållen från den föregående formeln genom att multiplicera med , där är lika med antalet noder i grafen. Storleksstorlek möjliggör jämförelse mellan noder av grafer av olika storlekar. $d(y,x)$ $x$ $y$ $N-1$ $N$

Att ta hänsyn till avståndet från eller till alla andra noder är inte tillämpligt på oriktade grafer, medan de i riktade grafer ger helt olika resultat. Till exempel kan en webbplats ha en hög utgående närhet men en låg inkommande närhet).

Harmonisk centralitet

I en (inte nödvändigtvis sammankopplad) graf omvänder harmonisk centralitet operationerna för summering och inversion vid bestämning av graden av närhet:

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

var , om det inte finns någon väg från till . Harmonisk centralitet kan normaliseras genom att dividera med , där är lika med antalet noder i grafen. $1/d(y,x)=0$ $y$ $x$ $N-1$ $N$

Harmonisk centralitet föreslogs av Marchiori och Lathora (2000) [18] , sedan oberoende av Dekker (2005) under namnet värderad centralitet [19] och Rochat (2009) [ 20] .

Medlingsgrad

Förmedlingsgraden är ett mått på centraliteten hos en vertex i en graf (det finns också en kantförmedlingsgrad , som inte diskuteras här). Graden av förmedling kvantifierar antalet gånger en nod överbryggar den kortaste vägen mellan två andra noder. Graden av medling introducerades av Linton Freeman som ett mått på det kvantitativa uttrycket av en persons interaktion med andra människor i ett socialt nätverk [21] . I detta koncept har de hörn som har högst sannolikhet att vara på en slumpmässigt vald kortaste väg mellan två slumpmässigt valda hörn en hög grad av mediation.

Förmedlingsgraden för en vertex i en graf med hörn beräknas enligt följande: $v$ $G:=(V,E)$ $V$

För varje par av hörn ( s , t ) beräknas de kortaste vägarna mellan dem .
Bestäm för varje par av hörn ( s , t ) andelen kortaste vägar som passerar genom det aktuella hörnet (här, vertex v ).
Vi sammanfattar dessa andelar över alla par av hörn ( s , t ).

Mer kompakt kan graden av medling representeras som [22] :

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

där är lika med det totala antalet kortaste vägar från nod till nod , och är lika med antalet sådana vägar som passerar genom . Graden av mediering kan normaliseras genom att dividera med antalet par av hörn som inte inkluderar v , vilket är lika med för riktade grafer och lika med för oriktade grafer . Till exempel, i en oriktad stjärna har den centrala vertexen (som finns i varje möjlig kortaste väg) förmedlingsgrad (1 om normaliserad), medan bladen (som inte finns i någon kortaste väg) har förmedlingsgrad 0. ${\displaystyle \sigma _{st))$ $s$ $t$ $\sigma _{st}(v)$ $v$ $(n-1)(n-2)$ $(n-1)(n-2)/2$ $(n-1)(n-2)/2$

Ur beräkningssynpunkt innebär både graden av mediation och graden av närhet för alla hörn i en graf att man beräknar de kortaste vägarna mellan alla par av hörn i grafen, vilket tar tid när man använder Floyd-Warshall-algoritmen . Men på glesa grafer kan Johnsons algoritm vara mer effektiv och köra i tid . När det gäller ovägda grafer kan beräkningar utföras med Brandes-algoritmen [22] , vilket tar tid . Vanligtvis antar dessa algoritmer att graferna är oriktade och kopplade till upplösningen av loopar och flera kanter. När man arbetar med nätverksgrafer som representerar enkla kopplingar som ofta inte har loopar eller flera kanter (där kanterna representerar kopplingar mellan människor). I det här fallet delas det slutliga centralitetsindexet med hjälp av Brandes algoritm med 2 för att ta hänsyn till varje kortaste väg som räknas två gånger [22] . $O(V^{3})$ $O(V^{2}\log V+VE)$ $O(VE)$

Grad av inflytande

Graden av påverkan är ett mått på påverkan av en nod i nätverket . Den tilldelar relativa poäng till alla noder i nätverket baserat på konceptet att länkar till noder med hög poäng bidrar mer till poängen för noden i fråga än samma länk till en nod med låg poäng [23] [5] [5] . Googles PageRank och Katz nodcentralitet är varianter av graden av påverkan [24] .

Använda närliggande matris för att hitta graden av påverkan

För en given graf med hörn, låt vara närliggande matris , det vill säga om vertex är anslutet till vertex , och annars. Det relativa vertexcentralitetsindexet kan definieras 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 }}\summa _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\summa _ {t\in G}a_{v,t}x_{t}

där är uppsättningen av grannar till vertex , och är en konstant. Efter mindre transformationer kan detta uttryck skrivas om i vektornotation som en ekvation för en egenvektor $M(v)$ $v$ $\lambda$

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

I allmänhet finns det många olika egenvärden för vilka det finns en egenvektor som inte är noll. Eftersom elementen i närliggande matris är icke-negativa, finns det ett enskilt största egenvärde som är reellt och positivt, enligt Frobenius-Perron-satsen . Detta största egenvärde ger det önskade måttet på centralitet [23] . Den associerade egenvektorkomponenten ger den relativa centraliteten för en vertex i nätverket. Egenvektorn definieras upp till en faktor, så att endast relationen mellan vertexcentraliteter är fullständigt definierad. För att bestämma exponentens absoluta värde är det nödvändigt att till exempel normalisera egenvektorn så att summan över alla hörn är lika med 1 eller normalisera med det totala antalet hörn n . Potensmetoden är en av många egenvärdesderivationsalgoritmer som kan användas för att hitta denna dominanta egenvektor [24] . Dessutom kan detta generaliseras så att elementen i matrisen A kan vara reella tal som representerar bindningens styrka, som i en stokastisk matris . $\lambda$ $v^{th}$ $v$

Centralitet enligt Katz

Centralitet enligt Kac [25] är en generalisering av graden av anknytning. Anslutningsmöjligheter mäter antalet direkta grannar, och Kac-centraliteten mäter antalet alla noder som kan anslutas med vägar samtidigt som avlägsna noder straffas. Matematiskt definieras denna centralitet som

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

var är en dämpningsmultiplikator från intervallet . $\alfa$ $(0,1)$

Enligt Katz kan centralitet ses som en variant av graden av påverkan. En annan form av centralitet enligt Kac är

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

Jämfört med graden av inflytande ersätts den med $x_{j}$ $x_{j}+1.$

Det visades [26] att huvudegenvektorn (motsvarande det största egenvärdet för närliggande matris ) är Kac-centralitetsgränsen när k närmar sig underifrån. $A$ $\alfa$ ${\tfrac {1}{\lambda ))$

PageRank

PageRank uppfyller följande likhet

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

var

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

är lika med antalet grannar till noden (eller antalet utgående anslutningar för den riktade grafen). Jämfört med Katz grad av inflytande och centralitet är skalningsfaktorn en viktig skillnad . Skillnaden mellan PageRank och grad av påverkan ligger i det faktum att PageRank-vektorn är en vänster egenvektor (det vill säga en egenvektor för den transponerade matrisen, observera att multiplikatorn har omvänd ordning på index) [27] . $j$ $L(j)$ ${\displaystyle a_{ji))$

Perkolationscentralitet

Det finns ett gäng centralitetsmått för att bestämma "viktigheten" av en enda nod i ett komplext nätverk. Men de återspeglar betydelsen av en nod rent topologiskt, och värdet av en nod beror inte på något sätt på nodens "tillstånd". Värdet förblir konstant oavsett nätverksdynamik. Detta gäller även för uppmätta medlingsåtgärder. En nod kan dock också vara centralt belägen vad gäller grad av förmedling eller annat mått på centralitet, men inte vara "centralt placerad" i ett nätverk där det finns läckage. Läckage av "infektion" sker i komplexa nätverk i ett stort antal scenarier. En virus- eller bakterieinfektion kan spridas via människors sociala nätverk, så kallade kontaktnätverk. Spridningen av sjukdomar kan också ses på en hög abstraktionsnivå genom att överväga ett nätverk av städer eller befolkningscentra som är sammankopplade med vägar, järnvägar eller flygbolag. Datavirus kan spridas över datornätverk. Rykten eller nyheter om företagserbjudanden och erbjudanden kan också spridas via människors sociala medier. I alla dessa scenarier sprids "infektionen" genom länkarna i ett komplext nätverk, och ändrar nodernas "tillstånd" reversibelt eller irreversibelt. Till exempel, i ett epidemiologiskt scenario, flyttar individer från det "mottagliga" tillståndet till det "infekterade" tillståndet. Tillstånden för specifika noder som spridningar av "smitta" kan anta binära värden (som "en nyhet mottagen/ej mottagen"), diskreta värden (mottagliga/infekterade/botade) eller till och med kontinuerliga värden (såsom andelen smittade människor i staden). Det gemensamma i alla dessa scenarier är att spridningen av "infektionen" leder till en förändring av nätverksnodernas tillstånd. Med detta i åtanke har percolation centrality (PC) föreslagits , som mäter vikten av en nod när det gäller att bidra till perkolering genom nätverket. Denna åtgärd föreslogs av Pairavinan et al [28] .

Släckningscentralitet definieras för en given nod och vid en given tidpunkt som andelen "läckningsvägar" som passerar genom noden. En "läckväg" är den kortaste vägen mellan ett par noder där källnoden är i ett läcktillstånd (t.ex. infekterad). Målnoden kan vara i ett perkolationstillstånd, ett icke-perkolationstillstånd eller ett partiellt perkolationstillstånd.

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

där är det totala antalet kortaste vägar från nod till nod , och är antalet sådana vägar som passerar genom . Läckagetillståndet för en nod vid tidpunkten betecknas som och det finns två specialfall, när som indikerar ett tätt tillstånd vid tidpunkten och när , vilket indikerar full läcka vid tidpunkten . Värden mellan dessa värden betyder partiella läckagetillstånd (till exempel i ett nätverk av städer kan detta vara andelen infekterade personer i staden). ${\displaystyle \sigma _{sr))$ $s$ $r$ $\sigma _{sr}(v)$ $v$ $i$ $t$ ${x^{t}}_{i}$ ${x^{t}}_{i}=0$ $t$ ${x^{t}}_{i}=1$ $t$

Läckvägsvikterna beror på de läcknivåer som tilldelats källnoderna, baserat på postulatet att ju högre läcknivån för källnoden är, desto viktigare är vägarna som går ut från den noden. Noder som ligger på de kortaste vägarna med början vid noder med hög perkolation är därför potentiellt viktigare för perkolering. Definitionen av PC kan också utökas till att även omfatta målnodsvikter. Beräkningen av läckagecentraliteten utförs i tid med en effektiv implementering lånad från den snabba Brandes-algoritmen, och om beräkningarna kräver att man tar hänsyn till ändnodernas vikter är värsta tänkbara tid . $O(NM)$ $O(N^{3})$

Korsklick centralitet

Centraliteten för en enskild nod i en komplex graf avgör nodens kopplingar till olika klick . En nod med hög korsklick centralitet främjar spridningen av information eller sjukdom i grafen. Klickor är subgrafer där varje nod är kopplad till alla andra klicknoder. Korsklickscentraliteten för en nod för en given graf med hörn och kanter betecknas som och lika med antalet klick som hörn tillhör. Detta mått användes i Faganis tidning [29] , men föreslogs först av Everett och Borgatti 1998 under namnet "klicköverlappande centralitet". $v$ $G:=(V,E)$ $|V|$ $|E|$ $X(v)$ $v$

Freeman centralitet

Centraliteten för ett nätverk är ett mått på hur central dess mest centrala nod är jämfört med andra noder [10] . Måttet på centralitet beräknas sedan (a) som summan av centralitetsskillnaderna mellan den mest centrala noden i nätverket och alla andra noder, och (b) dividerar detta värde med den teoretiskt största summan av skillnader i något nätverk av samma storlek [10] . Då kan vilket centralitetsmått som helst ha sitt eget centralitetsmått. Formellt sett, om är centralitetsmåttet för punkten , om är det största sådana måttet i nätverket, och om $C_{x}(p_{i})$ $i$ $C_{x}(p_{*})$

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

är den största summan av skillnader i punktcentralitet för varje graf med samma antal noder, då är nätverkets centralitet [10] $C_{x}$

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

Skillnadsbaserade mått på centralitet

För att få bättre resultat i att rangordna noderna i ett givet nätverk använder Alvarez-Socorro (et al.) [30] ett mått på olikhet (karakteristiskt för klassificeringsteori och dataanalys) för att förbättra måttet på centralitet i komplexa nätverk. Detta illustreras av graden av påverkan genom att beräkna centraliteten för varje nod genom att lösa egenvärdesproblemet

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

where (koordinatmässig produkt), och är en godtycklig olikhetsmatris , definierad i termer av olikhetsmåttet. Till exempel genom Jaccards olikhet som ges av formeln $W_{ij}=A_{ij}D_{ij}$ $D_{ij}$

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

Detta mått gör det möjligt för oss att kvantifiera det topologiska bidraget (därav det kallas bidragscentraliteten) för varje nod till centraliteten för en given nod, och erhåller ett större vikt/viktighetsförhållande för de noder med större olikhet, eftersom detta tillåter en given nod att nå noder som kan inte nås direkt.

Observera att det är icke-negativt, eftersom och är icke-negativa matriser, så vi kan använda Frobenius-Perron-satsen för att säkerställa att lösningen på problemet ovan är unik för med icke-negativ c , vilket gör att vi kan få centraliteten av varje nod i nätverket. Sålunda är centraliteten för den i:te noden lika med $W$ $A$ $D$ ${\displaystyle \lambda =\lambda _{max))$

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

där är lika med antalet nätverksnoder. Vissa nätverk och olikhetsmått testades av Alvarez-Socorro (et al.) [31] och förbättrade resultat erhölls i de studerade fallen. $n$

Generaliseringar

Empiriska och teoretiska studier generaliserar begreppet centralitet i samband med statiska nätverk till dynamiska centraliteter [32] i samband med tidsberoende och kortlivade nätverk [33] [34] [35] .

För en generalisering till viktade nätverk, se Opsal et al [36] .

Begreppet centralitet har också generaliserats till gruppnivå. Till exempel visar graden av gruppförmedling andelen geodetiska länkar av par (det vill säga banor med minsta längd) av noder som inte tillhör gruppen som passerar genom gruppen [37] [38] .

Se även

Anteckningar

↑ En del av terminologin är hämtad från artikeln av A. S. Semenov och M. V. Bartosh "UPPSATTNING AV STABILITETEN I INTERNET OF THINGS NÄTVERK ANVÄNDER INDIKATORER FÖR CENTRALITET AV RELATIONER" . Termerna i litteraturen på ryska har inte satt sig. Så, i artikeln av Evin I. A. Komplexa nätverk: En introduktion till teorin , istället för termen "medlingsgrad", används termerna "nodbelastning", "anslutningar med maximal betydelse". På sidan Nätverksstatistik används istället för termen "grad av anslutning", den bokstavliga översättningen "centralitet efter grad", istället för termerna "grad av ..." - "centralitet av ...". Ibland används termen "centralitet" istället för termen "centralitet".
↑ Newman, 2010 .
↑ 1 2 3 4 Bonacich, 1987 , sid. 1170–1182.
↑ 1 2 3 4 5 6 Borgatti, 2005 , sid. 55–71.
↑ 1 2 3 Negre, Morzan, Hendrickson et al., 2018 , sid. E12201-E12208.
↑ 1 2 3 4 Borgatti, Everett, 2006 , sid. 466–484.
↑ 1 2 Benzi, Klymko, 2013 , sid. 686–706.
↑ Michalak, Aadithya, Szczepański, Ravindran, Jennings, 2013 , sid. 607-650.
↑ Krackhardt, 1990 , sid. 342–369.
↑ 1 2 3 4 5 Freeman, 1979 , sid. 215–239.
↑ 12 Advokat , 2015 , sid. 8665.
↑ da Silva, Viana, da F. Costa, 2012 , sid. P07005.
↑ Bauer och Lizier, 2012 , sid. 68007.
↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , sid. 1–13.
↑ Ghoshal, Barabsi, 2011 , sid. 394.
↑ Bavelas, 1950 , sid. 725–730.
↑ Sabidussi, 1966 , sid. 581–603.
↑ Marchiori, Latora, 2000 , sid. 539–546.
↑ Dekker, 2005 .
↑ Rochat, 2009 .
↑ Freeman, 1977 , sid. 35–41.
↑ 1 2 3 Brandes, 2001 , sid. 163–177.
↑ 12 Newman , 2007 , sid. 1-12.
^ 12 American Mathematical Society . (obestämd)
↑ Katz, 1953 , sid. 39–43.
↑ Bonacich, 1991 , sid. 155–168.
↑ Hur rangordnar Google webbsidor? Arkiverad från originalet den 31 januari 2012. 20Q: Om nätverksliv
↑ Piraveenan, Prokopenko, Hossain, 2013 , sid. e53095.
↑ Faghani, 2013 , sid. 1815–1826
↑ Alvarez-Socorro, Herrera-Almarza, González-Díaz, 2015 , sid. 17095.
↑ Alvarez-Socorro AJ, Herrera-Almarza LA, González-Díaz. Tilläggsinformation för egencentralitet baserad på olikhetsmått avslöjar centrala noder i komplexa nätverk . Nature Publishing Group. (obestämd)
↑ Braha, Bar-Yam, 2006 , sid. 59–63.
↑ Hill, Braha, 2010 , sid. 046105.
↑ Gross, Sayama, 2009 .
↑ Holme, Saramaki, 2013 .
↑ Opsahl, Agneessens, Skvoretz, 2010 , sid. 245–251.
↑ Everett, Borgatti, 2005 , sid. 57–76.
↑ Puzis, Yagil, Elovici, Braha, 2009 .

Litteratur

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

Philip Bonacich. Makt och centralitet: En familj av åtgärder // American Journal of Sociology. - 1987. - T. 92 , nr. 5 . - doi : 10.1086/228631 .
Bonacich P. Samtidig grupp och individuell centralitet // Sociala nätverk. - 1991. - T. 13 , nr. 2 . - doi : 10.1016/0378-8733(91)90018-o .
Stephen P. Borgatti. Centralitet och nätverksflöde // Sociala nätverk. - 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 för karakterisering av proteinallosteriska vägar // Proceedings of the National Academy of Sciences. - 2018. - T. 115 . - doi : 10.1073/pnas.1810452115 .
Stephen P. Borgatti, Martin G. Everett. Ett grafteoretiskt perspektiv på centralitet // Sociala nätverk. - 2006. - T. 28 , nr. 4 . - doi : 10.1016/j.socnet.2005.11.005 .
Michele Benzi, Christine Klymko. En matrisanalys av olika centralitetsmått // SIAM Journal on Matrix Analysis and Applications. - 2013. - T. 36 , nr. 2 . - doi : 10.1137/130950550 . - arXiv : 1312.6722 .
Tomasz P. Michalak, Karthik V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Nicholas R. Jennings. Effektiv beräkning av Shapley-värdet för spelteoretisk nätverkscentralitet // Journal of Artificial Intelligence Research. - 2013. - T. 46 .
David Krackhardt. Att bedöma det politiska landskapet: struktur, kognition och makt i organisationer // Administrativ vetenskap kvartalsvis. - 1990. - Juni ( vol. 35 , nummer 2 ). - doi : 10.2307/2393394 . — .
Renato da Silva, Matheus Viana, Luciano da F. Costa. Förutsäga epidemi från individuella egenskaper hos spridarna // J. Stat. Mek.: Theory Exp.. - 2012. - T. 2012 . - doi : 10.1088/1742-5468/2012/07/p07005 . - . - arXiv : 1202.0024 .
Frank Bauer, Joseph Lizier. Identifiera påverkande spridare och effektivt uppskatta antalet infektioner i epidemimodeller: A walk counting approach // 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 -- finns det en underskattad epidemisk effekt av nätverks perifera noder? // The European Physical Journal B. - 2013. - T. 86 , nr 10 . - doi : 10.1140/epjb/e2013-31025-5 . - arXiv : 1110.2558 .
Ghoshal G., Barabsi AL Rankingstabilitet och superstabila noder i komplexa nätverk. // NatCommun. - 2011. - T. 2 . - doi : 10.1038/ncomms1396 . — .
Glenn advokat. Förstå spridningskraften hos alla noder i ett nätverk: ett kontinuerligt tidsperspektiv //Sci Rep. - 2015. - T. 5 . - doi : 10.1038/srep08665 . - . - arXiv : 1405.6707 . — PMID 25727453 .
Linton C. Freeman. Centralitet i sociala nätverk: Begreppsförtydligande // Sociala nätverk. - 1979. - Vol. 1 , nummer. 3 . — S. 215–239 . - doi : 10.1016/0378-8733(78)90021-7 . Arkiverad från originalet den 22 februari 2016.
Linton Freeman. En uppsättning mått på centralitet baserat på mellanskillnad // Sociometri. - 1977. - T. 40 , nr. 1 . — s. 35–41 . - doi : 10.2307/3033543 . — .
Alex Bavelas. Kommunikationsmönster i uppgiftsorienterade grupper // J. Acoust. soc. Am. - 1950. - T. 22 , nr. 6 .
Sabidussi G. Sabidussi. Centralitetsindex för en graf // Psykometri. - 1966. - T. 31 , nr. 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 , nr. 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 , nr. 3 .
Yannick Rochat. Närhetscentralitet utökad till osammanhängande grafer: The harmonic centrality index // Applications of Social Network Analysis, ASNA 2009 . — 2009.
Ulrik Brandes. En snabbare algoritm för centralitet mellan varandra // Journal of Mathematical Sociology. - 2001. - T. 25 , nr. 2 . - doi : 10.1080/0022250x.2001.9990249 .
Newman MEJ Nätverkens matematik .
Katz L. Ett nytt statusindex härlett från Sociometric Index // Psychometrics. - 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 , nr. 1 . - doi : 10.1371/journal.pone.0053095 . - . — PMID 23349699 .
Mohamamd Reza Faghani. En studie av XSS Worm Propagation and Detection Mechanisms in Online Social Networks // IEEE Transactions on Information Forensics and Security. - 2013. - T. 8 , nr. 11 . - doi : 10.1109/TIFS.2013.2280884 .
Alvarez-Socorro AJ, Herrera-Almarza GC, González-Díaz LA Egencentralitet baserad på olikhetsmått avslöjar centrala noder i komplexa nätverk // Vetenskapliga rapporter. - 2015. - November ( vol. 5 ). - doi : 10.1038/srep17095 . - . — PMID 26603652 .
Braha D., Bar-Yam Y. Från centralitet till tillfällig berömmelse: Dynamisk centralitet i komplexa nätverk // komplexitet. - 2006. - T. 12 , nr. 2 . - doi : 10.1002/cplx.20156 . - . - arXiv : fysik/0611295 .
Hill SA, Braha D. Dynamisk modell av tidsberoende komplexa nätverk // Physical Review E. - 2010. - Vol. 82 , nr. 4 . - doi : 10.1103/physreve.82.046105 . - . - arXiv : 0901.4407 . — PMID 21230343 .
Adaptiva nätverk: teori, modeller och tillämpningar / Gross T., Sayama H.. - Springer, 2009.
Holme P., Saramaki J. Temporal Networks. — Springer, 2013.
Tore Opsahl, Filip Agneessens, John Skvoretz. Nodcentralitet i viktade nätverk: Generaliserande grad och kortaste vägar // Sociala nätverk. - 2010. - T. 32 , nr. 3 . - doi : 10.1016/j.socnet.2010.03.006 . Arkiverad från originalet den 26 februari 2018.
Everett MG, Borgatti SP Utökad centralitet. I PJ Carrington, J. Scott och S. Wasserman (Red.) // Modeller och metoder i analys av sociala nätverk. - New York: Cambridge University Press, 2005. - S. 57-76.
Puzis R., Yagil D., Elovici Y., Braha D. Samarbete mot internetanvändares anonymitet // Internet Research. - 2009. - T. 19 , nr. 1 . Arkiverad från originalet den 7 december 2013.

Läsning för vidare läsning

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