Grad af mægling

Graden af mediering er et mål for centralitet i en graf baseret på korteste veje . For ethvert par af knudepunkter i en forbundet graf er der mindst én (korteste) vej mellem knudepunkter, hvor enten antallet af kanter, som stien går langs (for uvægtede grafer) eller summen af vægtene af disse kanter (for vægtede) grafer) er minimal. Graden af mediering for hvert toppunkt er lig med antallet af disse korteste veje gennem toppunktet.

Mediationsgraden er meget udbredt i netværksteori - den afspejler i hvilken grad toppunkter er mellem andre toppunkter. For eksempel, i et telekommunikationsnetværk , vil noden med den højeste grad af formidling have mere kontrol over netværket, efterhånden som mere information passerer gennem den node. Graden af mediering blev udviklet som et generelt mål for centralitet - det kan anvendes på en lang række problemer i netværksteori, herunder problemer relateret til sociale netværk , biologisk, transport og videnskabeligt samarbejde [1] .

Selvom tidligere forfattere intuitivt beskrev centralitet i form af grad af formidling, gav Freeman [2] den første formelle definition af formidlingsgrad.

Definition

Graden af nodemediering er givet af: $v$

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

hvor er lig med det samlede antal korteste veje fra knude til knude , og er lig med antallet af disse veje, der går igennem . ${\displaystyle \sigma _{st))$ $s$ $t$ $\sigma _{st}(v)$ $v$

Bemærk, at graden af mediering er lig med brøkdelen af par af noder med betingelsen defineret af summeringsbetingelsen. Derfor er der par af noder, hvis korteste veje ikke inkluderer , så . Opdelingen er med for rettede grafer og med for urettede grafer, hvor er lig med antallet af noder i den største komponent. Bemærk, at denne værdi er størst, når et toppunkt er indeholdt i en enkelt korteste vej. Ofte gøres dette ikke, og normalisering kan udføres uden tab af nøjagtighed. $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)))

der fører til

\max(normal)=1

\min(normal)=0

Vægtede netværk

I et vægtet netværk behandles links, der forbinder noder, ikke længere som separate interaktioner, men vægtes i forhold til deres kapacitet, indflydelse, frekvens osv., hvilket tilføjer endnu en dimension til heterogeniteten i netværket udover topologiske effekter. Graden af formidling af en node i et vægtet netværk er givet ved summen af vægtene af dens tilstødende kanter.

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

Hvornår og er adjacency- og vægtmatricerne mellem noder og hhv. I lighed med magtloven for gradfordeling, der findes i skala-invariante netværk, adlyder graden af en given node også en magtlov. $a_{{ij}}$ $w_{ij}$ $jeg$ $j$

{\displaystyle s(k)\ca. k^{\beta ))

Undersøgelsen af gennemsnitsværdien af hjørnernes styrke med graden af mediering viser, at den funktionelle adfærd kan tilnærmes ved udtrykket [3] $s(b)$ $b$

{\displaystyle s(b)\ca. b^{\alpha ))

Perkolationscentralitet

Perkolationscentralitet er en version af den vægtede formidlingsgrad, men tager højde for "tilstanden" af kilde- og målknuderne for hver korteste vej, når vægten beregnes. Lækage forekommer i komplekse netværk i en lang række scenarier. For eksempel kan en viral eller bakteriel infektion spredes gennem folks sociale netværk, kendt som kontaktnetværk. Spredning af sygdom kan også betragtes 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 og nyheder om forretningstilbud og -aftaler kan også spredes gennem folks sociale netværk. I alle disse scenarier spredes "smitten" 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 Payravinan et al . [4] .

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 lig med det samlede antal korteste stier fra knude til knude , og er lig med 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 angiver tæthedstilstanden på et tidspunkt , og hvornår , som angiver fuld lækage på et tidspunkt . Værdier mellem disse værdier angiver 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 højde for endeknudernes vægte, er worst case-tiden lig med . $O(NM)$ $O(N^{3})$

Algoritmer

Beregning af grader af mediering og grader af nærhed af alle hjørner i en graf kræver beregning af de korteste veje mellem alle par af hjørner i grafen, hvilket tager tid, når man bruger Floyd-Warshall-algoritmen modificeret til at finde alle stier i stedet for én vej for to udvalgte noder. På sparsomme grafer kan Johnsons algoritme eller Brandeis' algoritme være mere effektive, begge algoritmer kører i tid . På uvægtede grafer tager det tid at beregne formidlingsgraden ved hjælp af Brandes-algoritmen [5] . $\Theta (|V|^{3})$ $O(|V|^{2}\log |V|+|V||E|)$ $O(|V||E|)$

Når man beregner graderne af mediering og grader af nærhed af alle hjørner af grafen, antages det, at graferne er urettede, forbundet, og flere kanter er tilladt. Når man arbejder med netværksgrafer, har graferne ofte ikke cyklusser eller flere kanter, hvilket afspejler simple forbindelser (her repræsenterer kanterne forbindelsen mellem mennesker). I dette tilfælde, når du bruger Brandes-algoritmen, divideres den endelige centralitetsværdi med 2 for at tage højde for, at hver korteste vej tælles to gange [6] .

En anden algoritme generaliserer graden af Freemans formidling til geodætik og graden af Newmans formidling til alle veje ved at indføre en parameter, der styrer udvekslingen mellem udforskning og brug. Tidskompleksiteten er lig med antallet af kanter pr. antal knudepunkter i grafen [7] .

Begrebet centralitet er også blevet udvidet til gruppeniveau [8] . Gruppeformidlingsgraden angiver andelen af geodetiske forbindelser, der forbinder par af ikke-gruppemedlemmer, der passerer gennem en gruppe af noder. Brandes' algoritme til beregning af mediationsgraden af alle toppunkter er blevet modificeret til at beregne gruppemedieringsgraden for en gruppe af noder med samme asymptotiske køretid [8] .

Relaterede begreber

Mediationsgraden er relateret til netværkets tilslutningsmuligheder ved , at toppunkter med høj grad af formidling potentielt bryder grafen, hvis de fjernes (se skæresæt ).

Rutegraden af formidling generaliserer graden af formidling , når den anvendes på en hvilken som helst ordning til bestemmelse af simple stier uden cykler, kun baseret på kriteriet om den korteste vej [9] .

Se også

Centralitet

Noter

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

Litteratur

Ulrik Brandes. En hurtigere algoritme for centralitet mellemhed // Journal of Mathematical Sociology. - 2001. - T. 25 , no. 2 . — S. 163–177 . - doi : 10.1080/0022250x.2001.9990249 . Arkiveret fra originalen den 13. oktober 2017.
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 . — .
Goh KI, Kahng B., Kim D. Universal Behavior of Load Distribution in Scale-Free Networks // Physical Review Letters. - 2001. - T. 87 , no. 27 . - S. 278701 . - doi : 10.1103/physrevlett.87.278701 . - . - arXiv : cond-mat/0106565 .
Amin Mantrach. Sum-over-paths kovarianskernen: Et nyt kovariansmål mellem noder i en rettet graf // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2010. - T. 32 , no. 6 . - S. 1112-1126 . - doi : 10.1109/tpami.2009.78 .
Robert L. Moxley, Nancy F. Moxley. Bestemmelse af punktcentralitet i ukonstruerede sociale netværk // Sociometri. - 1974. - T. 37 , no. 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 mellemhed centralitet // J. ACM. - 2010. - T. 57 , no. 4 . — S. 25:1–25:27 . - doi : 10.1145/1734213.1734219 .
Mahendra Piraveenan. Perkolationscentralitet: Kvantificering af grafteoretisk indvirkning af noder under perkolation i netværk // PLOS ONE. - 2013. - T. 8 , no. 1 . — S. e53095 . - doi : 10.1371/journal.pone.0053095 . - . — PMID 23349699 .
Barrat A., Barthelemy M., Pastor-Satorras R., Vespignani A. Arkitekturen af komplekse vægtede netværk // PNAS. - 2004. - T. 101 , nr. 11 .
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.
Shlomi Dolev, Yuval Elovici, Rami Puzis. Routing mellemhed centralitet // J. ACM. - T. 57 , no. 4 . - doi : 10.1145/1734213.1734219 .