Centralitet mellan varandra

En oriktad graf färgad baserat på centraliteten för varje vertex från minst (röd) till störst (blå).

Inom grafteorin är betweenness centrality ett mått på centralitet i en graf baserad på kortaste vägar . För varje par av hörn i en sammankopplad graf finns det minst en kortaste väg mellan hörnen så att antingen antalet kanter som banan passerar genom (för oviktade grafer) eller summan av kanternas vikter (för viktade grafer) ) minimeras. Mellanliggande centralitet för varje vertex är antalet av dessa kortaste vägar som passerar genom vertexet.

Betweenness centrality utformades som ett allmänt mått på centralitet: det gäller ett brett spektrum av problem inom nätverksteorin, inklusive problem relaterade till sociala nätverk , biologi, transport och vetenskapligt samarbete. Även om tidigare författare intuitivt har beskrivit centralitet som baserad på mellanhet, Freeman (1977) den första formella definitionen av centralitet mellan varandra.

Centralitet mellan varandra finner bred tillämpning i nätverksteori ; det representerar i vilken grad noder står mellan varandra. Till exempel, i ett telekommunikationsnätverk skulle en nod med högre centralitet mellan varandra ha mer kontroll över nätverket, eftersom mer information kommer att passera genom den noden.

Definition

Mellanhetscentraliteten för en nod $v$ ges av uttrycket:

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

där $\sigma _{st}$ är det totala antalet kortaste vägar från nod $s$ till nod $t$ och $\sigma _ {st}(v)$ är antalet av de vägar som passerar genom $v$ (inte där $v$ är en slutpunkt).

Notera att en nods centralitet mellan varandra skalas med antalet par av noder som föreslås av summeringsindexen. Därför kan beräkningen skalas om genom att dividera med antalet par av noder som inte inkluderar $v$ , så att $g\in [0,1]$ . Divisionen görs av $(N-1)(N-2)$ för riktade grafer och $(N) -1)(N-2)/2$ för oriktade grafer, där $N$ är antalet noder i den jättelika komponenten. Observera att detta skalas för högsta möjliga värde, där en nod korsas av varenda kortaste väg. Detta är ofta inte fallet, och en normalisering kan utföras utan förlust av precision

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

vilket resulterar i:

\max(normal)=1

\min(normal)=0

Observera att detta alltid kommer att vara en skalning från ett mindre område till ett större område, så ingen precision går förlorad.

Viktade nätverk

I ett viktat nätverk behandlas länkarna som förbinder noderna inte längre som binära interaktioner, utan viktas i proportion till deras kapacitet, inflytande, frekvens, etc., vilket lägger till ytterligare en dimension av heterogenitet inom nätverket utöver de topologiska effekterna. En nods styrka i ett viktat nätverk ges av summan av vikterna av dess intilliggande kanter.

s_{i}=\summa _{j=1}^{N}a_{ij}w_{ij}

Med $a_{ij}$ och $w_{ij}$ är närliggande och viktmatriser mellan noderna $i$ respektive $j$ . Analogt med effektlagsfördelningen av grad som finns i skalfria nätverk, följer styrkan hos en given nod också en kraftlagsfördelning.

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

En studie av medelvärdet $s(b)$ av styrkan för hörn med mellanliggande $b$ visar att det funktionella beteendet kan approximeras med en skalningsform:

$s(b)\approx b^{\alpha }$

Perkolationscentralitet

Perkolationscentralitet är en version av viktad mellanliggande centralitet, men den tar hänsyn till "tillståndet" för käll- och målnoderna för varje kortaste väg vid beräkning av denna vikt. Perkolering av en "smitta" sker i komplexa nätverk i ett antal scenarier. Till exempel kan virus- eller bakterieinfektioner spridas över sociala nätverk av människor, så kallade kontaktnätverk. Spridningen av sjukdomar kan också betraktas på en högre abstraktionsnivå, genom att överväga ett nätverk av städer eller befolkningscentra, sammankopplade med väg-, järnvägs- eller flygförbindelser. Datavirus kan spridas över datornätverk. Rykten eller nyheter om affärserbjudanden och erbjudanden kan också spridas via sociala nätverk av människor. I alla dessa scenarier sprids en "smitta" över länkarna i ett komplext nätverk och ändrar nodernas "tillstånd" när den sprids, antingen återställbart eller på annat sätt. Till exempel, i ett epidemiologiskt scenario går individer från "mottagliga" till "infekterade" tillstånd när infektionen sprider sig. Tillstånden som de enskilda noderna kan ta i exemplen ovan kan vara binära (som fått/inte tagit emot en nyhet), diskreta (mottagliga/infekterade/återhämtade) eller till och med kontinuerliga (som andelen infekterade människor i en stad ), när smittan sprider sig. Gemensamt för alla dessa scenarier är att spridningen av smittspridning resulterar i förändringar av nodtillstånd i nätverk. Percolation centrality (PC) föreslogs med detta i åtanke, som specifikt mäter nodernas betydelse när det gäller att underlätta perkoleringen genom nätverket. Denna åtgärd föreslogs av Piraveenan, Prokopenko & Hossain (2013) .

Perkolationscentralitet definieras för en given nod, vid en given tidpunkt, som andelen "perkolerade vägar" som går genom den noden. En 'perkolerad väg' är den kortaste vägen mellan ett par noder, där källnoden är perkolerad (t.ex. infekterad). Målnoden kan vara perkolerad eller icke-perkolerad, eller i ett delvis perkolerat tillstånd.

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

där $\sigma _{sr}$ är det totala antalet kortaste vägar från nod $s$ till nod $r$ och $\sigma _{ sr}(v)$ är antalet av de vägar som passerar genom $v$ . Perkolationstillståndet för noden $i$ vid tidpunkten $t$ betecknas med ${x^{t}}_{i}$ och två specialfall är när ${x^{t}}_{i}=0$ vilket indikerar ett icke-perkolerat tillstånd vid tidpunkten $t$ medan när ${x^{t}} _{i}=1$ vilket indikerar ett helt perkolerat tillstånd vid tidpunkten $t$ . Värdena däremellan indikerar delvis perkolerade tillstånd (t.ex. i ett nätverk av townships skulle detta vara procentandelen människor som är smittade i den staden).

De bifogade vikterna till perkolationsvägarna beror på perkolationsnivåerna som tilldelats källnoderna, baserat på antagandet att ju högre perkolationsnivån för en källnod är, desto viktigare är vägarna som kommer från den noden. Noder som ligger på kortaste vägar som härrör från mycket perkolerade noder är därför potentiellt viktigare för perkoleringen. Definitionen av PC kan också utvidgas till att även omfatta målnodsvikter. Beräkningar av perkolationscentralitet körs i ${\displaystyle O(NM)}-$ tid med en effektiv implementering antagen från Brandes snabba algoritm och om beräkningen behöver ta hänsyn till målnodernas vikter, är värsta fallet $O(N^{3})$ .

Algoritmer

Att beräkna mellan- och närhetscentraliteten för alla hörn i en graf innebär att man beräknar de kortaste vägarna mellan alla par av hörn på en graf, vilket tar $\Theta (|V|^{3})$ tid med Floyd–Warshall-algoritmen , modifierad för att inte bara hitta en utan räkna alla kortaste vägarna mellan två noder. På en gles graf Johnsons algoritm eller Brandes algoritm vara mer effektiva, båda tar $O(|V|^{2}\ log |V|+|V||E|)$ tid. På oviktade grafer tar det ${\displaystyle O(|V||E|)} tid$ att beräkna mellanvärdescentralitet med Brandes algoritm.

Vid beräkning av mellanliggande och närhet centraliteter för alla hörn i en graf, antas det att grafer är oriktade och sammankopplade med hänsyn till slingor och flera kanter. När det specifikt handlar om nätverksgrafer är grafer ofta utan loopar eller flera kanter för att bibehålla enkla relationer (där kanter representerar kopplingar mellan två personer eller hörn). I det här fallet kommer Brandes algoritm att dividera slutliga centralitetspoäng med 2 för att ta hänsyn till varje kortaste väg som räknas två gånger.

En annan algoritm generaliserar Freemans mellanhet beräknad på geodetik och Newmans mellanhet beräknad på alla vägar, genom att introducera en hyperparameter som styr avvägningen mellan utforskning och exploatering. Tidskomplexiteten är antalet kanter gånger antalet noder i grafen.

En ungefärlig, probabilistisk uppskattning av centraliteter mellan varandra kan erhållas mycket snabbare genom att ta provvägar med en dubbelriktad bredd-först-sökning .

Ansökningar

Sociala nätverk

I sociala nätverksanalyser kan centraliteten mellan varandra ha olika implikationer. Ur ett makroskopiskt perspektiv reflekterar överbryggande positioner eller "strukturella hål" (indikerat med hög centralitet mellan varandra) makt, eftersom de tillåter personen på den överbryggande positionen att utöva kontroll (t.ex. bestämma om den ska dela information eller inte) över personerna som den kopplar samman. mellan. Ur det mikroskopiska perspektivet av ego-nätverk (dvs endast med tanke på första gradens kopplingar), i sociala nätverk online sammanfaller en hög centralitet mellan varandra med nomineringar av närmaste vänner (dvs starka mellanmänskliga band ), eftersom det återspeglar sociala kapitalinvesteringar i relationen när avlägsna sociala kretsar (t.ex. familj och universitet) överbryggas (ofta som ett resultat av en introduktion av ego).

Flodnätverk

Betweenness centrality har använts för att analysera den topologiska komplexiteten hos flodnätverk samt deras användning i sjöfartshandeln.

Relaterade begrepp

Mellanlägescentralitet är relaterad till ett nätverks anslutningsmöjlighet , eftersom högt mellanliggande hörn har potentialen att koppla bort grafer om de tas bort (se cut set ).

Se även

Centralitet

Bibliografi

Barrat, A.; et al. (2004). "Arkitekturen för komplexa viktade nätverk" . Proceedings of the National Academy of Sciences of the United States of America . 101 (11): 3747–3752. arXiv : cond-mat/0311416 . Bibcode : 2004PNAS..101.3747B . doi : 10.1073/pnas.0400087101 . ISSN 0027-8424 . PMC 374315 . PMID 15007165 .
Borassi, Michele; Natale, Emanuele (2019). "KADABRA är en adaptiv algoritm för mellanliggande via slumpmässig approximation" . ACM Journal of Experimental Algorithmics . 24 : 1,2:1–1,2:35. doi : 10.1145/3284359 . ISSN 1084-6654 . S2CID 67871875 .
Brandes, Ulrik (2001). "En snabbare algoritm för centralitet mellan varandra" (PDF) . Journal of Mathematical Sociology . 25 (2): 163–177. CiteSeerX 10.1.1.11.2024 . doi : 10.1080/0022250x.2001.9990249 . hdl : 10983/23603 . S2CID 13971996 . Arkiverad (PDF) från originalet den 29 mars 2021 . Hämtad 29 mars 2021 .
Burt, Ronald (2009). Strukturella hål: Konkurrensens sociala struktur . Cambridge: Harvard University Press . ISBN 978-0-674-02909-5 . OCLC 1041149426 . Hämtad 29 mars 2021 .
Freeman, Linton (1977). "En uppsättning mått på centralitet baserade på ömsesidighet". Sociometri . 40 (1): 35–41. doi : 10.2307/3033543 . JSTOR 3033543 .
Goh, K.-I.; Kahng, B.; Kim, D. (2001). "Universellt beteende för lastfördelning i skalfria nätverk". Fysiska granskningsbrev . 87 (27): 278701. arXiv : cond-mat/0106565 . Bibcode : 2001PhRvL..87A8701G . doi : 10.1103/PhysRevLett.87.278701 . ISSN 0031-9007 . PMID 11800921 . S2CID 15746304 .
Mantrach, Amin; et al. (2010). "The Sum-over-Paths Covariance Kernel: A Novel Covariance Measure between Nodes of a Directed Graph". IEEE-transaktioner på mönsteranalys och maskinintelligens . 32 (6): 1112–1126. doi : 10.1109/tpami.2009.78 . PMID 20431135 . S2CID 4807216 .
Moxley, Robert L.; Moxley, Nancy F. (1974). "Att bestämma punkt-Centralitet i outvecklade sociala nätverk". Sociometri . 37 (1): 122–130. doi : 10.2307/2786472 . JSTOR 2786472 .
Newman, Mark EJ (2010). Nätverk: en introduktion . Oxford: Oxford University Press . ISBN 978-0-19-920665-0 . OCLC 964511577 .
Piraveenan, Mahendra; Prokopenko, Mikhail; Hossain, Liaquat (2013). Holme, Petter (red.). "Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks" . PLOS ETT . 8 (1): e53095. Bibcode : 2013PLoSO...853095P . doi : 10.1371/journal.pone.0053095 . ISSN 1932-6203 . PMC 3551907 . PMID 23349699 .
Sarker, Shiblu; et al. (2019). "Kritiska noder i flodnätverk" . Vetenskapliga rapporter . 9 (1): 11178. Bibcode : 2019NatSR...911178S . doi : 10.1038/s41598-019-47292-4 . ISSN 2045-2322 . PMC 6672004 . PMID 31371735 .
Stolz, Simon; Schlereth, Christian (2021). "Förutsäga slipstyrka med ego-nätverksstrukturer". Journal of Interactive Marketing . 54 (maj): 40–52. doi : 10.1016/j.intmar.2020.10.001 . S2CID 229403802 .