Graden av medling

Graden av förmedling är ett mått på centralitet i en graf baserad på kortaste vägar . För alla hörnpar i en sammankopplad graf finns det minst en (kortast) väg mellan hörn där antingen antalet kanter längs vilka banan går (för oviktade grafer) eller summan av vikterna av dessa kanter (för viktade grafer) är minimal. Graden av mediering för varje vertex är lika med antalet av dessa kortaste vägar genom vertexet.

Mediationsgraden används flitigt i nätverksteori - den återspeglar i vilken grad hörn är mellan andra hörn. Till exempel, i ett telekommunikationsnätverk skulle noden med den högsta graden av förmedling ha mer kontroll över nätverket när mer information passerar genom den noden. Graden av förmedling utvecklades som ett allmänt mått på centralitet - det kan tillämpas på ett brett spektrum av problem inom nätverksteorin, inklusive problem relaterade till sociala nätverk , biologiskt, transport och vetenskapligt samarbete [1] .

Även om tidigare författare intuitivt beskrev centralitet i termer av grad av förmedling, gav Freeman [2] den första formella definitionen av förmedlingsgrad.

Definition

Graden av nodförmedling ges av: $v$

{\displaystyle g(v)=\summa _{s\neq v\neq t}{\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 av dessa vägar som går igenom . ${\displaystyle \sigma _{st))$ $s$ $t$ $\sigma _{st}(v)$ $v$

Observera att graden av mediering är lika med andelen av par av noder med villkoret definierat av summeringsvillkoret. Därför finns det par av noder vars kortaste vägar inte inkluderar , så att . Uppdelningen är med för riktade grafer och med för oriktade grafer, där är lika med antalet noder i den största komponenten. Observera att detta värde är störst när en vertex finns i en enskild kortaste väg. Ofta görs inte detta och normalisering kan göras utan förlust av noggrannhet. $v$ $g\in [0,1]$ $(N-1)(N-2)$ $(N-1)(N-2)/2$ $N$

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

som leder till

\max(normal)=1

\min(normal)=0

Viktade nätverk

I ett viktat nätverk behandlas länkar som förbinder noder inte längre som separata interaktioner, utan viktas i proportion till deras kapacitet, inflytande, frekvens etc., vilket adderar ytterligare en dimension till heterogeniteten i nätverket förutom topologiska effekter. Graden av förmedling av en nod i ett viktat nätverk ges av summan av vikterna av dess intilliggande kanter.

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

När och är närliggande och viktmatriser mellan noder och resp. I likhet med effektlagen för gradfördelning som finns i skalinvarianta nätverk, lyder graden av en given nod också en kraftlag. $a_{{ij}}$ $w_{ij}$ $i$ $j$

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

Studien av medelvärdet av styrkan på hörnen med graden av mediation visar att det funktionella beteendet kan approximeras med uttrycket [3] $s(b)$ $b$

{\displaystyle s(b)\approx b^{\alpha ))

Perkolationscentralitet

Perkolationscentralitet är en version av den viktade graden av förmedling, men tar hänsyn till "tillståndet" för käll- och målnoderna för varje kortaste väg vid beräkning av vikten. Läckage uppstår i komplexa nätverk i en mängd olika scenarier. Till exempel kan en virus- eller bakterieinfektion spridas via människors sociala nätverk, så kallade kontaktnätverk. Sjukdomsspridning kan också betraktas på en hög abstraktionsnivå genom att överväga ett nätverk av städer eller befolkningscentra som är förbundna med vägar, järnvägar eller flygbolag. Datavirus kan spridas över datornätverk. Rykten och nyheter om affärserbjudanden och erbjudanden kan också spridas via människors sociala nätverk. I alla dessa scenarier sprids "smittan" genom länkarna i ett komplext nätverk, vilket ä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 Payravinan et al [4] .

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 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 . Läckagetillståndet för en nod vid tidpunkten betecknas som och det finns två specialfall när , vilket indikerar täthetstillståndet vid tidpunkten , och när , vilket indikerar fullt läckage vid tidpunkten . Värden mellan dessa värden indikerar 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 lika med . $O(NM)$ $O(N^{3})$

Algoritmer

Att beräkna graderna av förmedling och grader av närhet för alla hörn i en graf kräver att man beräknar de kortaste vägarna mellan alla par av hörn i grafen, vilket tar tid när Floyd-Warshall-algoritmen används modifierad för att hitta alla vägar snarare än en väg för två valda noder. På glesa grafer kan Johnsons algoritm eller Brandeis algoritm vara effektivare, båda algoritmerna körs i tid . På oviktade grafer tar det tid att beräkna graden av förmedling med Brandes-algoritmen [5] . $\Theta (|V|^{3})$ $O(|V|^{2}\log |V|+|V||E|)$ $O(|V||E|)$

Vid beräkning av graderna av mediering och närhetsgrader för alla hörn i grafen, antas det att graferna är oriktade, sammankopplade och att flera kanter är tillåtna. När man arbetar med nätverksgrafer har graferna ofta inga cykler eller flera kanter, vilket återspeglar enkla kopplingar (här representerar kanterna kopplingen mellan människor). I det här fallet, när du använder Brandes-algoritmen, delas det slutliga centralitetsvärdet med 2 för att ta hänsyn till att varje kortaste väg räknas två gånger [6] .

En annan algoritm generaliserar graden av Freemans förmedling till geodesik och graden av Newmans förmedling till alla vägar genom att introducera en parameter som styr utbytet mellan utforskning och användning. Tidskomplexiteten är lika med antalet flanker per antal noder i grafen [7] .

Begreppet centralitet har också utvidgats till gruppnivå [8] . Gruppförmedlingsgraden indikerar andelen geodetik som förbinder par av icke-gruppmedlemmar som passerar genom en grupp av noder. Brandes algoritm för att beräkna mediationsgraden för alla hörn har modifierats för att beräkna gruppmedieringsgraden för en grupp av noder med samma asymptotiska körtid [8] .

Relaterade begrepp

Graden av förmedling är relaterad till nätverkets uppkoppling genom att hörn med hög grad av förmedling potentiellt bryter grafen om de tas bort (se skäruppsättning ).

Ruttens förmedlingsgrad generaliserar graden av förmedling när den tillämpas på vilket schema som helst för att bestämma enkla vägar utan cykler endast baserat på kriteriet om den kortaste vägen [9] .

Se även

Centralitet

Anteckningar

↑ Freeman, 1977 , sid. 39.
↑ Freeman, 1977 .
↑ Barrat, Barthelemy, Pastor-Satorras, Vespignani, 2004 .
↑ Piraveenan, 2013 , sid. e53095.
↑ Brandes, 2001 , sid. ett.
↑ Brandes, 2001 , sid. 9.
↑ Mantrach, 2010 .
↑ 1 2 Puzis, Yagil, Elovici, Braha, 2009 .
↑ Dolev, Elovici, Puzis, 2010 , sid. 25:1-25:27.

Litteratur

Ulrik Brandes. En snabbare algoritm för centralitet mellan varandra // Journal of Mathematical Sociology. - 2001. - T. 25 , nr. 2 . — S. 163–177 . - doi : 10.1080/0022250x.2001.9990249 . Arkiverad från originalet den 13 oktober 2017.
Linton Freeman. En uppsättning mått på centralitet baserat på mellanhet // Sociometri. - 1977. - T. 40 , nr. 1 . — s. 35–41 . - doi : 10.2307/3033543 . — .
Goh KI, Kahng B., Kim D. Universal Behaviour of Load Distribution in Scale-Free Networks // Physical Review Letters. - 2001. - T. 87 , nr. 27 . - S. 278701 . - doi : 10.1103/physrevlett.87.278701 . - . - arXiv : cond-mat/0106565 .
Amin Mantrach. The summa-over-paths covariance kernel: Ett nytt kovariansmått mellan noder i en riktad graf // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2010. - T. 32 , nr. 6 . - S. 1112-1126 . - doi : 10.1109/tpami.2009.78 .
Robert L. Moxley, Nancy F. Moxley. Fastställande av punktcentralitet i oförutsedda sociala nätverk // Sociometri. - 1974. - T. 37 , nr. 1 . — S. 122–130 . - doi : 10.2307/2786472 . — .
Newman MEJ Networks: En introduktion. - Oxford, Storbritannien: Oxford University Press, 2010. - ISBN 978-0199206650 .
Shlomi Dolev, Yuval Elovici, Rami Puzis. Routing betweenness centrality // J. ACM. - 2010. - T. 57 , nr. 4 . — S. 25:1–25:27 . - doi : 10.1145/1734213.1734219 .
Mahendra Piraveenan. Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes under Percolation in Networks // PLOS ONE. - 2013. - T. 8 , nr. 1 . — S. e53095 . - doi : 10.1371/journal.pone.0053095 . - . — PMID 23349699 .
Barrat A., Barthelemy M., Pastor-Satorras R., Vespignani A. Arkitekturen för komplexa viktade nätverk // PNAS. - 2004. - T. 101 , nr 11 .
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.
Shlomi Dolev, Yuval Elovici, Rami Puzis. Routing betweenness centrality // J. ACM. - T. 57 , nej. 4 . - doi : 10.1145/1734213.1734219 .