Närhet centralitet

I en sammankopplad graf är närhetscentralitet (eller närhet ) av en nod ett mått på centralitet i ett nätverk , beräknat som den reciproka summan av längden av de kortaste vägarna mellan noden och alla andra noder i grafen. Således, ju mer central en nod är, desto närmare är den alla andra noder.

Distance and shortest path in a simple graph.

Siffran bredvid varje nod är avståndet från den noden till den kvadratiska röda noden mätt med längden på den kortaste vägen. De gröna kanterna illustrerar en av de två kortaste vägarna mellan den röda kvadratnoden och den röda cirkelnoden. Närheten till den röda kvadratnoden är därför 5/(1+1+1+2+2) = 5/7.

Närhet definierades av Bavelas (1950) som det ömsesidiga av farness , det vill säga:

C_{B}(x)={\frac {1}{\sum _{y}d(y,x)}}.

där $d(y,x)$ är avståndet (längden på den kortaste vägen) mellan hörn $x$ och $y$ . Denna onormaliserade version av närhet är ibland känd som status När man talar om närhetscentralitet hänvisar folk vanligtvis till dess normaliserade form som representerar medellängden på de kortaste vägarna istället för deras summa. Det ges i allmänhet av föregående formel multiplicerat med $N-1$ , där $N$ är antalet noder i grafen som resulterar i:

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

Normaliseringen av närhet förenklar jämförelsen av noder i grafer av olika storlekar. För stora grafer blir minus etta i normaliseringen oväsentligt och det tas ofta bort.

Som ett av de äldsta centralitetsmåtten ges närhet ofta i allmänna diskussioner om nätverkscentralitetsmått i inledande texter eller i artiklar som jämför olika centralitetsmått. De värden som produceras av många centralitetsmått kan vara starkt korrelerade. I synnerhet närhet och grad har visat sig vara relaterade i många nätverk genom ett ungefärligt förhållande

{\frac {1}{C(x)}}\approx {\frac {-1}{\ ln(z-1)}}\ln(k_{x})+\beta

där ${\textstyle k_{x}}$ är graden av vertex $x$ medan $z$ och β är parametrar som hittas genom att anpassa närhet och grad till denna formel. Z- parametern representerar förgreningsfaktorn, den genomsnittliga graden av noder (exklusive rotnoden och löv) för de kortaste vägträden som används för att approximera nätverk när detta samband demonstreras. Detta är aldrig ett exakt förhållande men det fångar en trend som ses i många verkliga nätverk.

Närhet är relaterat till andra längdskalor som används inom nätverksvetenskap. Till exempel är den genomsnittliga kortaste väglängden ${\textstyle \langle \ell \rangle } ,$ det genomsnittliga avståndet mellan hörn i ett nätverk, helt enkelt medelvärdet av de omvända närhetsvärdena

\langle \ell \rangle ={\frac {1}{N} }\summa _{x}{\frac {1}{C(x)}}={\frac {1}{N(N-1)}}\summa _{x}\summa _{y}d( y,x)

.

Att ta avstånd från eller till alla andra noder är irrelevant i oriktade grafer, medan det kan ge helt olika resultat i riktade grafer (t.ex. en webbplats kan ha en hög närhetscentralitet från utgående länkar, men låg närhetscentralitet från inkommande länkar).

Ansökningar

Närhet används i många olika sammanhang. Inom bibliometri har närhet använts för att titta på hur akademiker väljer sina tidskrifter och bibliografier inom olika områden eller för att mäta en författares inverkan på ett område och deras sociala kapital. När den används för att välja potentiella leads i kunddata har närhet setts leda till en betydande vinst i framgångsfrekvensen. Närheten till en stad i ett lufttransportnätverk har visat sig vara starkt korrelerad med socioekonomiska indikatorer som bruttonationalprodukten. Närhet har också tillämpats på biologiska nätverk där detta till exempel användes för att identifiera mer än 50 % av de globala regulatorerna inom de översta 2 % av de rankade generna eller essentiella gener visade sig ha högre närhet än icke-essentiella gener i protein- interaktionsnätverk. I ett metaboliskt nätverk kan nodernas närhet identifiera de viktigaste metaboliterna.

I frånkopplade grafer

När en graf inte är starkt kopplad introducerade Beauchamp 1965 idén att använda summan av reciproka av avstånd, istället för reciproka av summan av avstånd, med konventionen $1/\infty =0$ :

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

Beauchamps modifiering följer den (mycket senare i tiden) allmänna principen som föreslagits av Marchiori och Latora (2000) att i grafer med oändliga avstånd beter sig det harmoniska medelvärdet bättre än det aritmetiska medelvärdet. I själva verket kan Bavelas närhet beskrivas som den denormaliserade ömsesidiga av det aritmetiska medelvärdet av avstånd, medan Beauchamps centralitet är det ömsesidiga av det harmoniska medelvärdet av avstånd.

Denna idé har återuppstått flera gånger i litteraturen, ofta utan normaliseringsfaktorn $n-1$ : för oriktade grafer under namnet värderad centralitet av Dekker (2005) och under namnet harmonisk centralitet av Rochat (2009) ; if axiomatiserades av Garg (2009) och föreslogs igen senare av Opsahl (2010). Det studerades på generella riktade grafer av Boldi och Vigna (2014). Denna idé är också ganska lik den marknadspotential som föreslås i Harris (1954) som nu ofta går under termen marknadstillträde.

Varianter

Dangalchev (2006) föreslår i ett arbete om nätverkssårbarhet för oriktade grafer en annan definition:

D(x)=\summa _{y\neq x}{\frac {1}{2^{d(y,x)}}}.

Denna definition används effektivt för frånkopplade grafer och gör det möjligt att skapa bekväma formler för grafoperationer. Till exempel:

Om en graf $G_{1}+G_{2}$ skapas genom att länka nod $p$ i graf $G_{1}$ till nod $q$ i graf $G_{2}$ då är den kombinerade närheten:

D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q));

om en graf $G_{1}+G_{2}$ skapas genom att komprimera nod $p$ i graf $G_{1}$ och nod $q$ av graf $G_{2}$ till en nod då är närheten:

D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+2D(p)D(q).

Om grafen $T(G)$ är törngrafen för grafen $G$ , som har $n$ noder, då $T(G)$ närhet är:

D(T(G))={\frac {9}{4}}D(G)+n.

Den naturliga generaliseringen av denna definition är:

D(x)=\summa _{y\neq x}\ {\alpha ^{d(y,x)}},

där $\alpha$ tillhör (0,1). När $\alpha$ ökar från 0 till 1 ändras den generaliserade närheten från lokal karaktäristik (grad) till global (antal anslutna noder).

Informationscentraliteten hos Stephenson och Zelen (1989) är ett annat närhetsmått , som beräknar det harmoniska medelvärdet av motståndsavstånden mot en vertex x , som är mindre om x har många banor med litet motstånd som förbinder det med andra hörn.

I den klassiska definitionen av närhetscentraliteten modelleras informationsspridningen genom användning av kortaste vägar. Denna modell kanske inte är den mest realistiska för alla typer av kommunikationsscenarier. Således har relaterade definitioner diskuterats för att mäta närhet, som den random walk closeness centrality introducerad av Noh och Rieger (2004). Den mäter hastigheten med vilken slumpmässigt gående meddelanden når ett hörn från någon annanstans i grafen. Hierarkisk närhet av Tran och Kwon (2014) är en utökad närhetscentralitet för att på ett annat sätt hantera begränsningen av närhet i grafer som inte är starkt kopplade. Den hierarkiska närheten inkluderar explicit information om intervallet av andra noder som kan påverkas av den givna noden.

Se även