Központiság

A gráfelméletben és a hálózatelemzésben a központosság vagy a központhoz való közelség mutatója határozza meg a gráf legfontosabb csúcsait . A mutató alkalmazásai arra szolgálnak, hogy azonosítsák a legbefolyásosabb személy(ek)et a közösségi hálózatokban , az internet vagy a nagyvárosi hálózatok kulcsfontosságú infrastrukturális csomópontjait , valamint a betegség hordozóit. A szociológiai primer források mérésére a centralitás fogalmát, amelyet eredetileg a közösségi hálózatok elemzése során fejlesztettek ki, és a centralitás számos kifejezését használják [2] . Ezeket a mérőszámokat nem szabad összetéveszteni a csomópont-hatás mérőszámaival., amelyek a hálózat egyes csomópontjainak hatásának mennyiségi jellemzőit keresik .

A centralitási indexek meghatározása és leírása

A centralitási indexek választ adnak arra a kérdésre, hogy "Mi jellemzi egy csúcs fontosságát?" A választ egy valós értékű függvényben adjuk meg a gráf csúcsain, amelynek értékei (várhatóan) adnak egy rangsort, amely meghatározza a legfontosabb csomópontokat [3] [4] [5] .

A "fontosság" szó jelentése széles skálával rendelkezik, ami a központiság sokféle meghatározásához vezet. Két kategorizációs rendszert javasoltak. A "jelentősség" a hálózaton keresztüli áramlás típusával összefüggésben érthető. Ez lehetővé teszi a centralitás osztályozását a fontosnak tartott áramlás típusa szerint [4] . A „fontosság” alternatívaként a hálózat integritásában való részvételként is értelmezhető. Ez lehetővé teszi a központok osztályozását aszerint, hogy miként mérik a részvételt [6] . Mindkét megközelítés különböző kategóriákra osztja a központokat. Az egyik kategóriának megfelelő központiság gyakran alkalmatlan lesz, ha egy másik kategóriába alkalmazzák [4] .

Ha a centralitásokat részvételük alapján kategorizáljuk, világossá válik, hogy a legtöbb centralitás ugyanabba a kategóriába tartozik. Az adott csomópontból kiinduló útvonalak száma csak az útvonalak meghatározásában és számlálásában különbözik. Az erre a csoportra vonatkozó megállapodások korlátozása lehetővé teszi az útvonalak spektrumának központi pontjainak leírását az első hossztól ( összekapcsolhatósági fok ) a korlátlan útvonalakig ( befolyási fok ) [3] [7] . Az a megfigyelés, hogy sok központ osztozik ezeken a kapcsolatokon, megmagyarázza az indexek közötti magas szintű korrelációt.

Az áramlások leírása a hálózatban

A hálózat felfogható az utak leírásaként, amelyek mentén valami áramlik. Ez lehetővé teszi az áramlástípusok és a központiság által kódolt útvonaltípusok alapján történő leírást. Az áramlás alapja lehet az átutalás, ahol minden oszthatatlan elem átjut egyik csomópontból a másikba, hasonlóan a csomagok postáról az ügyfél otthonába történő kézbesítéséhez. A második esetben az elem reprodukálása történik meg, amely átmegy a következő csomóponthoz, így a forrás és a cél is rendelkezik ezzel az elemmel. Ilyen eset például a pletykák terjedése, amikor az információkat privát módon osztják meg, a folyamat végén a forrást és a célt is tájékoztatják. Az utolsó eset a párhuzamos terjedés, amikor egy elemet egyidejűleg több linken is terjesztenek, hasonlóan a rádióadáshoz, amely egyszerre sok hallgatónak szolgáltatja ugyanazt az információt [4] .

Hasonlóképpen, az útvonal típusa korlátozható a következőkre: Geodézia (legrövidebb utak), utak (egy csúcsot sem látogatnak meg többször, utak (a csúcsok többször is meglátogathatók, de egyetlen élt sem lehet kétszer bejárni) vagy útvonalak (csúcsok és élek egyaránt) többször előfordulhat) [4] .

Leírás sétaszerkezet szerint

Egy alternatív osztályozás származtatható a centralitás felépítésének módjából. Ez ismét két osztályra való felosztáshoz vezet – radiális vagy medián. A sugárirányú központok megszámolják azon utak számát, amelyek egy adott csúcsban kezdődnek/végeződnek. A kapcsolódási fokok és a befolyás fokai a központosság radiális mértékeinek példái, amelyek az egy vagy korlátlan hosszúságú utak számát számolják. A medián központok számolják az adott csúcson áthaladó utakat. A kanonikus példa a Freeman-közvetítés mértéke , az adott csúcson áthaladó legrövidebb utak száma [6] .

Hasonlóképpen, a számláló képes rögzíteni az útvonal mennyiségét vagy hosszát . A mennyiség egy adott típusú útvonalak teljes száma. Az előző bekezdésből három példa tartozik ebbe a kategóriába. A hossz a távolság egy adott csúcstól a gráf többi csúcsáig. A többi Freeman-csomóponthoz való közelség foka, egy adott csúcs és az összes többi csúcs közötti teljes geodéziai távolság a legismertebb példa [6] . Ne feledje, hogy ez a besorolás a kiszámított útvonalak típusától függ (pl. útvonalak, körpályák, utak, geodézia).

Borgatti és Everett úgy vélte, hogy ez a tipológia képet ad arról, hogyan lehet összehasonlítani a központiság mértékét. Ebben a 2x2 osztályozásban az ugyanabba a cellába eső központok elég hasonlóak ahhoz, hogy elfogadható alternatívák legyenek, és ésszerűen össze lehet hasonlítani, hogy egy adott problémára melyik pontszám a legjobb. A különböző sejtekből származó mérések azonban teljesen eltérőek. A relatív alkalmasság bármilyen meghatározása csak előre meghatározott kontextusban történhet, melyik kategória a megfelelőbb [6] .

A spektrumon létező radiális térfogati központok

Az útvonal-struktúra leírása azt mutatja, hogy szinte az összes használt központosítás radiális-térfogat-mérés. Ez bizonyosságot ad arról, hogy a csúcsközpontúság azon csúcsok központiságának függvénye, amelyekhez hozzá van rendelve. A központok a társításuk módjában különböznek egymástól.

Bonacic megmutatta, hogy ha egy asszociációt utak alapján határozunk meg, akkor a központok családja a vizsgált úthosszak alapján határozható meg [3] . A kapcsolódás mértéke az egy hosszúságú útvonalakat számolja, a befolyás mértéke a korlátlan hosszúságú útvonalakat. Az asszociációk alternatív definíciói is lehetségesek. Az alfa-centralitás lehetővé teszi, hogy külső befolyási források legyenek a csúcsokra. Estrada részgráf-centralitása csak a zárt utakat számolja (háromszögek, négyszögek, ...).

Az ilyen mérőszámok lényege az a megfigyelés, hogy egy gráf szomszédsági mátrixának fokai megadják a fokkal egyenlő hosszúságú utak számát. Hasonlóképpen, a mátrix kitevője szorosan összefügg az adott hosszúságú utak számával. A szomszédsági mátrix kezdeti átalakítása lehetővé teszi a különböző típusú útvonalak számának meghatározását. Mindkét megközelítésben a csúcsközpontúság kifejezhető végtelen összegként, ill

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

mátrix hatványokhoz, ill

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

a mátrix kitevőjére, ahol

$k$ megegyezik az útvonal hosszával,
$A_{R}$ a transzformált szomszédsági mátrix, és
$\beta$ egy kompenzáló paraméter, amely biztosítja az összeg konvergenciáját.

A Bonacic mértékek családja nem alakítja át a szomszédsági mátrixot. Az Alpha centrality a szomszédsági mátrixot a felbontásával helyettesíti . A részgráf-centralitás lecseréli a szomszédsági mátrixot annak nyomára. A szomszédsági mátrix kezdeti transzformációjától függetlenül mindegyik megközelítésnek van egy közös korlátozó viselkedése. Mivel nullára hajlik, az index konvergál a kapcsolódási fokhoz . A maximális értékre való törekvés során az index a befolyás mértékéhez konvergál [7] . $\beta$ $\beta$

Játékelméleti központiság

A legtöbb fenti szabványos intézkedés közös jellemzője, hogy értékelik egy csomópont fontosságát, és csak arra a szerepre összpontosítanak, amelyet a csomópont önmagában játszik. Azonban sok alkalmazásban ez a megközelítés nem megfelelő, mivel csomópontok kölcsönhatása észlelhető, ha intézkedéseket alkalmaznak a csoport csomópontokra.

Vegyük például a járvány megállításának problémáját. A fenti hálózati képet nézve mely csomópontokat kell beoltani? A fent leírt intézkedések alapján szeretnénk felismerni azokat a csomópontokat, amelyek a legfontosabbak a betegség terjedésében. Nem biztos, hogy a csomópontok egyedi tulajdonságaira összpontosító, csak centralitáson alapuló megközelítések alkalmazása nem jó ötlet. A piros mezőben lévő csomópontok önmagukban nem tudják megállítani a betegség terjedését, de csoportként tekintve jól látjuk, hogy megállíthatják a betegséget, ha az a , , csomópontokban kezdődik . A játékelméleti központok a játékelmélet eszközeivel próbálják figyelembe venni a leírt problémákat, lehetőségeket. A Michalak (et al.) [8] által javasolt megközelítés a Shapley-vektort használja . A Shapley-vektor kiszámításának (időbeli) bonyolultsága miatt a legtöbb erőfeszítést ezen a területen olyan új algoritmusok és módszerek kifejlesztésébe fektetik, amelyek a sajátos hálózati topológián és a probléma speciális természetén alapulnak. Ezzel a megközelítéssel az algoritmus időbeli összetettségét exponenciálisról polinomiálisra csökkentheti. $v_{1}$ ${\displaystyle v_{4))$ $v_{5}$

Fontos korlátozások

A központisági indexeknek két fontos korlátja van, az egyik nyilvánvaló, a másik finom. Nyilvánvaló korlát, hogy az egyik alkalmazáshoz optimális központiság gyakran nem optimális egy másik alkalmazáshoz. Sőt, ha ez nem így lenne, akkor nem is lenne szükség ennyi különböző központosításra. Ezt a jelenséget szemlélteti Crackhard sárkánya , amelyre a centralitás három különböző fogalma három különböző legcentrálisabb csúcsot eredményez [9] .

Egy finom korlát az, hogy van egy elterjedt tévhit, miszerint a csúcsközpontúság a csúcsok relatív fontosságát tükrözi. A centralitási indexeket kifejezetten a rangsoroláshoz fejlesztették ki, ami lehetővé teszi a legfontosabb csúcsok kiválasztását [3] [4] . Jól csinálják az említett korlátozások mellett. Nem úgy tervezték őket, hogy általánosan mérjék a csomókat. A közelmúltban a hálózati fizikusok elkezdték fejleszteni a csomópont-befolyásolási mérőszámokat a probléma megoldására.

A hiba kettős. Először is, csak a csúcsok szerinti rangsorolás, mivel ezek fontossága nem tükrözi a különböző rangsorolási szintek közötti fontossági különbséget. Ez a tény mérsékelhető, ha Freeman centralitását alkalmazzuk a kérdéses centralitás mérőszámára, ami némi betekintést ad a csomópontok fontosságába azok különböző centralitási pontszámai alapján. Sőt, a Freeman-központúság lehetővé teszi egyes hálózatok összehasonlítását a legmagasabb értékű csomópontok mutatói alapján [10] .

Másodszor, azok a tulajdonságok, amelyek (helyesen) tükrözik egy adott hálózatban/alkalmazásban a legfontosabb csúcsokat, nem feltétlenül általánosítanak a többi csúcsra. A hálózat legtöbb más csomópontja esetében a rangsorolás értelmetlen lehet [11] [12] [13] [14] . Ez megmagyarázza például, hogy a Google képkeresésének csak az első néhány eredménye jelenik meg megfelelő sorrendben. A PageRank egy nagyon instabil mérőszám, gyakran az ellenkező rangot mutatja a keresési paraméter kis változtatása után [15] .

Bár első pillantásra nem tűnik nyilvánvalónak a centralitási indexnek a hálózat többi részére történő általánosításának lehetetlensége, a fenti definíciókból ez közvetlenül következik. Az összetett hálózatok heterogén topológiájúak. Az optimális mérték mennyiben függ a legfontosabb csúcsok hálózati struktúrájától, mennyiben az ilyen csúcsokra optimális mérték nem optimális a hálózat többi részére [11] .

Kapcsolati lehetőségek

Történelmileg az első és fogalmilag legegyszerűbb fogalom a kapcsolódás mértéke , amelyet a csomóponthoz tartozó hivatkozások számaként határoznak meg (vagyis a csomóponthoz tartozó hivatkozások száma). A mérték a csomópont azon közvetlen kockázata alapján értelmezhető, hogy elkap valamit a hálózaton keresztül (például vírust vagy valamilyen információt). Irányított hálózat esetén (ahol a linkek irányítottak) általában két különböző mérőszámot határozunk meg a kapcsolódás mértékére, nevezetesen a -degree -t és a out- degree -t . Ennek megfelelően az in-degree a csomóponttal fennálló kapcsolatok száma, a kilépési fokozat pedig a csomópont más csomópontokkal való kapcsolatainak száma. Ha a kapcsolatot valamilyen pozitív aspektussal, például barátsággal vagy együttműködéssel társítják, a belépést gyakran egyfajta népszerűségként, a kilépést pedig társaságiságként értelmezik.

Egy adott gráf csúcsainak csúcsokkal és élekkel való összekapcsolhatóságának fokát a következőképpen határozzuk meg $v$ $G:=(V,E)$ $|V|$ $|E|$

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

A gráf összes csomópontjának kapcsolati fokának kiszámítása időt vesz igénybe a gráf sűrű szomszédsági mátrixábrázolásában , és időt vesz igénybe az élek ritka mátrixábrázolásában . $\Theta (V^{2})$ $\Theta (E)$

A csomóponti szintű centralitás definíciója kiterjeszthető a teljes gráfra , és ebben az esetben gráfcentralitásról beszélünk [10] . Legyen a legnagyobb kapcsolódási fokú csomópont a -ban . Legyen egy összekapcsolt gráf csomópontokkal, amely maximalizálja a következő értéket ( a legmagasabb fokú kapcsolódási fokú csomóponttal -ban ): $v*$ $G$ $X:=(Y,Z)$ $|Y|$ $y*$ $x$

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

Ennek megfelelően a gráf központiságának mértéke egyenlő: $G$

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

Az érték akkor maximális, ha a gráf egy központi csomópontot tartalmaz, amelyhez az összes többi csomópont kapcsolódik ( csillaggrafikon ), ebben az esetben $H$ $x$

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

Így bármely grafikonhoz $G:=(V,E),$

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

Más csomópontok közelsége

Egy összekapcsolt gráfban egy csomópont normalizált közelségének foka megegyezik a csomópont és a gráf összes többi csomópontja közötti legrövidebb út átlagos hosszával . Ezután minél központibb a csomópont, annál közelebb van az összes többi csomóponthoz.

A közelség mértékét Alex Bavelas (1950) a távolság reciprokjaként határozta meg [16] [17] , i.e.

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

ahol egyenlő a csúcsok és a távolsággal . Amikor azonban más csomópontokhoz való közelség mértékéről beszélünk, az emberek általában annak normalizált alakjára gondolnak, amelyet általában az előző képletből kapunk megszorozva -val , ahol egyenlő a gráf csomópontjainak számával. A méretezés lehetővé teszi a különböző méretű grafikonok csomópontjainak összehasonlítását. $d(y,x)$ $x$ $y$ $N-1$ $N$

Az összes többi csomóponttól való távolság figyelembevétele nem alkalmazható irányítatlan gráfokra, míg irányított gráfokban egészen más eredményeket adnak. Előfordulhat például, hogy egy webhelynek nagy a kimenő, de alacsony a bejövő közelsége).

Harmonikus központiság

Egy (nem feltétlenül összefüggő) gráfban a harmonikus centralitás megfordítja az összegzés és az inverzió műveleteit a közelség mértékének meghatározásában:

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

ahol , ha nincs elérési út innen . A harmonikus centralitás normalizálható, ha elosztjuk -val , ahol egyenlő a gráf csomópontjainak számával. $1/d(y,x)=0$ $y$ $x$ $N-1$ $N$

A harmonikus centralitást Marchiori és Lathora (2000) [18] , majd egymástól függetlenül Dekker (2005) valued centrality néven [19] és Rochat (2009) [ 20] javasolta .

A közvetítés mértéke

A közvetítési fok a gráfban lévő csúcsok központosságának mértéke (van egy élközvetítési fok is , amelyről itt nem lesz szó). A közvetítés mértéke számszerűsíti, hogy egy csomópont hányszor hidalja át a legrövidebb utat két másik csomópont között. A közvetítés mértékét Linton Freeman vezette be, mint a személy másokkal való interakciójának mennyiségi kifejeződését egy közösségi hálózatban [21] . Ebben a koncepcióban azok a csúcsok, amelyek a legnagyobb valószínűséggel egy véletlenszerűen kiválasztott legrövidebb úton vannak két véletlenszerűen kiválasztott csúcs között, nagyfokú közvetítéssel rendelkeznek.

A csúcsokkal rendelkező gráf csúcsainak közvetítési fokát a következőképpen számítjuk ki: $v$ $G:=(V,E)$ $V$

Minden egyes csúcspárhoz ( s , t ) a közöttük lévő legrövidebb utat számítjuk ki .
Minden egyes csúcspárhoz ( s , t ) határozzuk meg a kérdéses csúcson áthaladó legrövidebb utak hányadát (itt v csúcs ).
Összefoglaljuk ezeket a megosztásokat az összes csúcspáron ( s , t ).

Tömörebben a közvetítés mértéke a következőképpen ábrázolható [22] :

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

ahol egyenlő a csomóponttól a csomópontig tartó legrövidebb utak teljes számával , és egyenlő az ezen keresztül áthaladó utak számával . A közvetítés mértéke normalizálható , ha elosztjuk a v - t nem tartalmazó csúcspárok számával , ami egyenlő az irányított gráfoknál és egyenlő az irányítatlan gráfoknál . Például egy irányítatlan csillagban a központi csúcs (amely minden lehetséges legrövidebb úton benne van) közvetítési fokozattal rendelkezik (1, ha normalizálva van), míg a levelek (amelyek egyik legrövidebb útban sem szerepelnek) 0 közvetítési fokozatúak. ${\displaystyle \sigma _{st))$ $s$ $t$ $\sigma _{st}(v)$ $v$ ${\megjelenítési stílus (n-1) (n-2)}$ $(n-1) (n-2)/2$ $(n-1) (n-2)/2$

Számítási szempontból mind a közvetítés mértéke, mind a gráf összes csúcsának közelségének mértéke magában foglalja a gráf összes csúcspárja közötti legrövidebb utak kiszámítását, ami a Floyd-Warshall algoritmus használatakor időt vesz igénybe . Ritka gráfokon azonban a Johnson-algoritmus hatékonyabb lehet, ha időben fut . Súlyozatlan gráfok esetén a számításokat Brandes algoritmussal [22] lehet elvégezni , ami időbe telik . Általában ezek az algoritmusok azt feltételezik, hogy a gráfok irányítatlanok, és a hurkok és több él felbontásához kapcsolódnak. Amikor olyan hálózati gráfokkal dolgozik, amelyek egyszerű kapcsolatokat ábrázolnak, amelyek gyakran nem rendelkeznek hurokkal vagy több éllel (ahol az élek az emberek közötti kapcsolatokat jelölik). Ebben az esetben Brandes algoritmusát használva a végső centralitási indexet elosztjuk 2-vel, hogy minden legrövidebb utat kétszer megszámoljanak [22] . $O(V^{3})$ $O(V^{2}\log V+VE)$ $O(VE)$

Befolyási fok

A befolyás mértéke a hálózat egy csomópontjának befolyásának mértéke . Relatív pontszámokat rendel a hálózat összes csomópontjához azon az elven alapulva, hogy a magas pontszámú csomópontokhoz mutató hivatkozások nagyobb mértékben járulnak hozzá a kérdéses csomópont pontszámához, mint az alacsony pontszámú csomópontokhoz mutató hivatkozások [23] [5] [5] . A Google PageRank és Katz csomópontközpontúsága a befolyás mértékének változatai [24] .

A szomszédsági mátrix segítségével megkeressük a befolyás mértékét

Adott csúcsokkal rendelkező gráf esetén legyen a szomszédsági mátrix , azaz ha a csúcs a csúcshoz kapcsolódik , és egyébként. A relatív csúcscentralitási index a következőképpen definiálható $G:=(V,E)$ $|V|$ $A=(a_{v,t})$ $a_{v,t}=1$ $v$ $t$ $a_{v,t}=0$ $v$

x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _ {t\in G}a_{v,t}x_{t}

ahol a csúcs szomszédjainak halmaza , és konstans. Kisebb átalakítások után ez a kifejezés átírható vektoros jelöléssel egyenletként egy sajátvektorra $M(v)$ $v$ $\lambda$

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

Általában sok különböző sajátérték létezik, amelyekhez létezik egy nem nulla sajátvektor. Mivel a szomszédsági mátrix elemei nem negatívak, a Frobenius–Perron-tétel szerint egyetlen legnagyobb sajátérték létezik, amely valós és pozitív . Ez a legnagyobb sajátérték adja meg a centralitás kívánt mértékét [23] . A hozzá tartozó sajátvektor komponens megadja egy csúcs relatív központi helyét a hálózatban. A sajátvektor egy tényezőig van definiálva, így csak a csúcscentralitások kapcsolata van teljesen definiálva. A kitevő abszolút értékének meghatározásához szükséges például a sajátvektor normalizálása úgy, hogy az összes csúcs összege 1 legyen, vagy normalizálni kell az n csúcsok teljes számával . A hatványmódszer egyike a sok sajátérték-levezetési algoritmusnak , amelyek segítségével megtalálhatjuk ezt a domináns sajátvektort [24] . Sőt, ez általánosítható úgy, hogy az A mátrix elemei lehetnek valós számok, amelyek a kötés erősségét reprezentálják, mint egy sztochasztikus mátrixban . $\lambda$ $v^{th}$ $v$

Központiság Katz szerint

A Kac [25] szerinti centralitás a kapcsolódás mértékének általánosítása. A Connectivity a közvetlen szomszédok számát méri, a Kac centrality pedig az összes olyan csomópont számát méri, amelyek útvonalon keresztül összekapcsolhatók, miközben hátrányosan érinti a távoli csomópontokat. Matematikailag ezt a központiságot a következőképpen határozzuk meg

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

ahol egy csillapítási szorzó az intervallumból . $\alpha$ $(0,1)$

Katz szerint a centralitás a befolyás mértékének egy változataként fogható fel. A centralitás másik formája Kac szerint az

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

A befolyás mértékéhez képest helyébe a $x_{j}$ $x_{j}+1.$

Megmutattuk [26] , hogy a fő sajátvektor (amely a szomszédsági mátrix legnagyobb sajátértékének felel meg ) a Kac centrális határértéke, amikor k alulról közelít. $A$ $\alpha$ ${\tfrac {1}{\lambda ))$

PageRank

A PageRank teljesíti a következő egyenlőséget

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

ahol

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

megegyezik a csomópont szomszédjainak számával (vagy az irányított gráf kimenő kapcsolatainak számával). Katz befolyásának és központi szerepének mértékéhez képest a skálázási tényező fontos különbség . A PageRank és a befolyás mértéke közötti különbség abban rejlik, hogy a PageRank vektor egy bal oldali sajátvektor (vagyis a transzponált mátrix sajátvektora, vegye figyelembe, hogy a szorzó az indexek fordított sorrendjét tartalmazza) [27] . $j$ $L(j)$ ${\displaystyle a_{ji))$

Percolation centrality

Egy csomó központi mérőszám létezik egy csomópont „jelentőségének” meghatározására egy összetett hálózatban. Azonban pusztán topológiai értelemben tükrözik egy csomópont fontosságát, és egy csomópont értéke semmilyen módon nem függ a csomópont "állapotától". Az érték a hálózat dinamikájától függetlenül állandó marad. Ez még a mért mediációs intézkedésekre is igaz. Egy csomópont azonban központilag is elhelyezkedhet a közvetítés mértéke vagy a központiság egyéb mértéke szempontjából, de nem lehet „központi helyen” egy olyan hálózat kontextusában, amelyben szivárgás tapasztalható. A „fertőzés” kiszivárgása összetett hálózatokban számos forgatókönyv esetén fordul elő. A vírusos vagy bakteriális fertőzés az emberek közösségi hálózatain keresztül terjedhet, amelyeket kapcsolati hálózatoknak neveznek. A betegségek terjedése nagy absztrakciós szinten is szemlélhető, ha figyelembe vesszük a városok vagy lakossági központok hálózatát, amelyeket utak, vasutak vagy légitársaságok kötnek össze. A számítógépes vírusok terjedhetnek a számítógépes hálózatokon. Az üzleti ajánlatokról és üzletekről szóló pletykák vagy hírek az emberek közösségi médiáján is terjedhetnek. Mindezekben a forgatókönyvekben a "fertőzés" egy összetett hálózat linkjein keresztül terjed, reverzibilisen vagy visszafordíthatatlanul megváltoztatva a csomópontok "állapotait". Például egy járványügyi forgatókönyv szerint az egyének a "fogékony" állapotból a "fertőzött" állapotba kerülnek. Az egyes csomópontok állapotai a "fertőzés" terjedésekor bináris értékeket vehetnek fel (például "hír érkezett/nem érkezett"), diszkrét értékeket (fogékony/fertőzött/gyógyult), vagy akár folyamatos értékeket is. (mint például a fertőzöttek aránya a városban). Ezekben a forgatókönyvekben az a közös, hogy a "fertőzés" terjedése a hálózati csomópontok állapotának megváltozásához vezet. Ezt szem előtt tartva javasolták a perkolációs központosítást (PC) , amely méri egy csomópont fontosságát a hálózaton keresztüli perkolációhoz való hozzájárulás szempontjából. Ezt az intézkedést Pairavinan és munkatársai javasolták [28] .

A szivárgási központosság egy adott csomóponthoz és egy adott időpontban a csomóponton áthaladó "szivárgási utak" arányaként van definiálva. A "szivárgási út" a legrövidebb út egy csomópontpár között, ahol a forráscsomópont szivárgási állapotban van (például fertőzött). A célcsomópont lehet perkolációs, nem perkolációs vagy részleges perkolációs állapotban.

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é}}}

ahol a csomóponttól a csomópontig tartó legrövidebb utak teljes száma , és az ezen keresztül áthaladó utak száma . Egy csomópont pillanatnyi szivárgási állapotát a következőképpen jelöljük, és van két speciális eset, amikor az időpontban szűkös állapotot , és amikor az időpontban teljes szivárgást jelez . Az ezen értékek közötti értékek részleges szivárgási állapotokat jelentenek (például városok hálózatában ez lehet a fertőzöttek százalékos aránya a városban). ${\displaystyle \sigma _{sr))$ $s$ $r$ $\sigma _{sr}(v)$ $v$ $én$ $t$ ${x^{t}}_{i}$ ${x^{t}}_{i}=0$ $t$ ${x^{t}}_{i}=1$ $t$

A szivárgási útvonalak súlya a forráscsomópontokhoz rendelt szivárgási szintektől függ, azon a posztulátumon alapulva, hogy minél magasabb a forráscsomópont szivárgási szintje, annál fontosabbak az adott csomópontból kimenő utak. Azok a csomópontok, amelyek a legrövidebb utakon fekszenek, és a magas perkolációs csomópontoktól kezdődnek, ezért potenciálisan fontosabbak a perkoláció szempontjából. A PC definíciója kiterjeszthető a célcsomópont-súlyokra is. A szivárgáscentralitás számítása időben , a gyors Brandes algoritmusból kölcsönzött hatékony megvalósítással történik, és ha a számításokhoz a végcsomópontok súlyát kell figyelembe venni, akkor a legrosszabb eset az idő . $O(NM)$ $O(N^{3})$

Cross-click centrality

Az egyes csomópontok kereszt-klikk- centralitása egy összetett gráfban meghatározza a csomópont és a különböző klikkek közötti kapcsolatokat . A nagy keresztkattintásos központú csomópont elősegíti az információk vagy betegségek terjedését a grafikonon. A klikkek olyan részgráfok, amelyekben minden csomópont kapcsolódik az összes többi klikkcsomóponthoz. Egy adott csúcsokkal és élekkel rendelkező gráf csomópontjának keresztkattintási központja a csúcshoz tartozó klikkek számával egyenlő . Ezt a mértéket Fagani cikkében [29] használták , de először Everett és Borgatti javasolta 1998-ban „klikk átfedő központiság” néven. $v$ $G:=(V,E)$ $|V|$ $|E|$ $X(v)$ $v$

Freeman centralitás

Bármely hálózat központisága annak mértéke, hogy a legközpontibb csomópontja mennyire van központi helyen a többi csomóponthoz képest [10] . A központosság mértékét ezután (a) a hálózat legközpontibb csomópontja és az összes többi csomópont közötti centralitási különbségek összegeként számítják ki, és (b) ezt az értéket elosztják a hálózat bármely hálózata közötti különbségek elméletileg legnagyobb összegével. azonos méretű [10] . Ekkor bármely központi mérőszámnak megvan a maga centralitási mértéke. Formálisan ha a pont centralitási mértéke , ha a legnagyobb ilyen mérték a hálózatban, és ha $C_{x}(p_{i})$ $én$ $C_{x}(p_{*})$

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

az azonos számú csomóponttal rendelkező gráf pontcentralitásbeli különbségeinek legnagyobb összege , akkor a hálózat központisága [10] $C_{x}$

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

A központiság különbség alapú mérőszámai

Annak érdekében, hogy jobb eredményeket érjen el egy adott hálózat csomópontjainak rangsorolásában, Alvarez-Socorro (et al.) [30] egy (az osztályozási elméletre és az adatelemzésre jellemző) disszimilaritás mérőszámát alkalmazza, hogy javítsa a központiság mértékét összetett hálózatokban. Ezt szemlélteti a befolyás mértéke az egyes csomópontok központiságának kiszámításával a sajátérték probléma megoldásával

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

ahol (koordináta szerinti szorzat), és egy tetszőleges eltérési mátrix , amelyet a különbség mértékével határozunk meg. Például a képlet által adott Jaccard -féle eltérésen keresztül $W_{ij}=A_{ij}D_{ij}$ $D_{ij}$

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

Ez a mérték lehetővé teszi számunkra, hogy számszerűsítsük az egyes csomópontok topológiai hozzájárulását (ezért nevezzük hozzájárulás-centralitásnak) egy adott csomópont központiságához, így nagyobb súly/fontosság arányt kapunk a nagyobb eltérésekkel rendelkező csomópontok között, mivel ez lehetővé teszi, hogy egy adott csomópont elérje azokat a csomópontokat, amelyek közvetlenül nem érhető el.

Vegye figyelembe, hogy nem negatív, mivel és nem negatív mátrixok, így a Frobenius-Perron tétel segítségével biztosíthatjuk, hogy a fenti probléma megoldása egyedi legyen nem negatív c esetén, ami lehetővé teszi, hogy megkapjuk a minden csomópont a hálózatban. Így az i-edik csomópont központisága egyenlő $W$ $A$ $D$ ${\displaystyle \lambda =\lambda _{max))$

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

ahol egyenlő a hálózati csomópontok számával. Alvarez-Socorro (et al.) [31] tesztelt néhány hálózatot és eltérést, és a vizsgált esetekben jobb eredményeket értek el. $n$

Általánosítások

Az empirikus és elméleti tanulmányok a statikus hálózatok kontextusában a centralitás fogalmát dinamikus centralitásokra [32] általánosítják az időfüggő és rövid élettartamú hálózatok összefüggésében [33] [34] [35] .

A súlyozott hálózatokra vonatkozó általánosításhoz lásd Opsal és munkatársai [36] .

A centralitás fogalmát a csoportszintre is általánosították. Például a csoportközvetítés mértéke megmutatja a csoporton átmenő, nem a csoporthoz tartozó csomópontok párjainak (vagyis minimális hosszúságú útvonalainak) geodéziai kapcsolatainak arányát [37] [38] .

Lásd még

Jegyzetek

↑ A terminológia egy részét A. S. Semenov és M. V. Bartosh "A DOLGOK INTERNETE HÁLÓZAT STABILITÁSÁNAK BECSLÉSE A KAPCSOLATOK KÖZPONTI MUTATÓI HASZNÁLATA" című cikkéből vettük át . Az orosz nyelvű irodalom kifejezései nem ülnek le. Tehát Evin I. A. Complex networks: An Bevezetés az elméletbe cikkében a „mediációs fok” kifejezés helyett a „csomóponti terhelés”, „nagy jelentőségű kapcsolatok” kifejezéseket használjuk. A Hálózati mérőszámok oldalon a „kapcsolati fok” kifejezés helyett a „központosság fok szerint” szó szerinti fordítást használjuk, a „degree of …” - „centrality by …” kifejezések helyett. Néha a "centralitás" kifejezést használják a "centralitás" kifejezés helyett.
↑ Newman, 2010 .
↑ 1 2 3 4 Bonacich, 1987 , p. 1170–1182.
↑ 1 2 3 4 5 6 Borgatti, 2005 , p. 55–71.
↑ 1 2 3 Negre, Morzan, Hendrickson et al., 2018 , p. E12201-E12208.
↑ 1 2 3 4 Borgatti, Everett, 2006 , p. 466–484.
↑ 1 2 Benz, Klymko, 2013 , p. 686–706.
↑ Michalak, Aadithya, Szczepański, Ravindran, Jennings, 2013 , p. 607-650.
↑ Krackhardt, 1990 , p. 342–369.
↑ 1 2 3 4 5 Freeman, 1979 , p. 215–239.
↑ 12 Ügyvéd , 2015 , p. 8665.
↑ da Silva, Viana, da F. Costa, 2012 , p. P07005.
↑ Bauer és Lizier, 2012 , p. 68007.
↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , p. 1–13.
↑ Ghoshal, Barabsi, 2011 , p. 394.
↑ Bavelas, 1950 , p. 725–730.
↑ Sabidussi, 1966 , p. 581–603.
↑ Marchiori, Latora, 2000 , p. 539–546.
↑ Dekker, 2005 .
↑ Rochat, 2009 .
↑ Freeman, 1977 , p. 35–41.
↑ 1 2 3 Brandes, 2001 , p. 163–177.
↑ 12. Newman , 2007 , p. 1-12.
↑ 12 American Mathematical Society . (határozatlan)
↑ Katz, 1953 , p. 39–43.
↑ Bonacich, 1991 , p. 155–168.
↑ Hogyan rangsorolja a Google a weboldalakat? Az eredetiből archiválva : 2012. január 31. 20Q: A hálózatos életről
↑ Piraveenan, Prokopenko, Hossain, 2013 , p. e53095.
↑ Faghani, 2013 , p. 1815–1826
↑ Alvarez-Socorro, Herrera-Almarza, González-Díaz, 2015 , p. 17095.
↑ Alvarez-Socorro AJ, Herrera-Almarza LA, González-Díaz. A különbözőségi mérőszámokon alapuló kiegészítő információ a sajátcentralitáshoz komplex hálózatok központi csomópontjait tárja fel . Nature Publishing Group. (határozatlan)
↑ Braha, Bar-Yam, 2006 , p. 59–63.
↑ Hill, Braha, 2010 , p. 046105.
↑ Gross, Sayama, 2009 .
↑ Holme, Saramaki, 2013 .
↑ Opsahl, Agneessens, Skvoretz, 2010 , p. 245–251.
↑ Everett, Borgatti, 2005 , p. 57–76.
↑ Puzis, Yagil, Elovici, Braha, 2009 .

Irodalom

Newman MEJ Networks: Bevezetés. – Oxford, Egyesült Királyság: Oxford University Press, 2010.
Newman MEJ The mathematics of networks, // The New Palgrave Encyclopedia of Economics . – Basingstoke, Palgrave Macmillan, 2007.

Phillip Bonacich. Hatalom és központiság: mértékek családja // American Journal of Sociology. - 1987. - T. 92 , sz. 5 . - doi : 10.1086/228631 .
Bonacich P. Egyidejű csoport- és egyéni központok // Social Networks. - 1991. - T. 13 , sz. 2 . - doi : 10.1016/0378-8733(91)90018-o .
Stephen P. Borgatti. Központiság és hálózati áramlás // Közösségi hálózatok. - 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. Sajátvektor központi szerepe a fehérje alloszterikus útvonalak jellemzésében // Proceedings of the National Academy of Sciences. - 2018. - T. 115 . - doi : 10.1073/pnas.1810452115 .
Stephen P. Borgatti, Martin G. Everett. Graph-Theoretic Perspective on Centrality // Social Networks. - 2006. - T. 28 , sz. 4 . - doi : 10.1016/j.socnet.2005.11.005 .
Michele Benz, Christine Klymko. A különböző központi mérőszámok mátrixelemzése // SIAM Journal on Matrix Analysis and Applications. - 2013. - T. 36 , sz. 2 . - doi : 10.1137/130950550 . - arXiv : 1312.6722 .
Tomasz P. Michalak, Karthik V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Nicholas R. Jennings. A Shapley-érték hatékony számítása a játékelméleti hálózatközpontúsághoz // Journal of Artificial Intelligence Research. - 2013. - T. 46 .
David Krackhardt. Assessing the Political Landscape: Structure, Cognition and Power in Organisations // Administrative Science Quarterly. - 1990. - június ( 35. évf. , 2. szám ). - doi : 10.2307/2393394 . — .
Renato da Silva, Matheus Viana, Luciano da F. Costa. A járvány előrejelzése a terjesztők egyedi jellemzői alapján // J. Stat. Mech.: Elmélet Exp.. - 2012. - T. 2012 . - doi : 10.1088/1742-5468/2012/07/p07005 . - . - arXiv : 1202.0024 .
Frank Bauer, Joseph Lizier. Az érintett terjesztők azonosítása és a fertőzések számának hatékony becslése járványmodellekben: A sétaszámláló megközelítés // Europhys Lett. - 2012. - T. 99 . - S. 68007 . - doi : 10.1209/0295-5075/99/68007 . - Iránykód . - arXiv : 1203.0502 .
Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefanic. Járványközpontúság – van-e alábecsült járványhatás a hálózati perifériás csomópontoknak? // The European Physical Journal B. - 2013. - T. 86 , 10. sz . - doi : 10.1140/epjb/e2013-31025-5 . - arXiv : 1110.2558 .
Ghoshal G., Barabsi AL Stabilitás és szuperstabil csomópontok rangsorolása összetett hálózatokban. // NatCommun. - 2011. - T. 2 . - doi : 10.1038/ncomms1396 . — Iránykód .
Glenn ügyvéd. A hálózat összes csomópontjának terjesztési erejének megértése: folyamatos idejű perspektíva //Sci Rep. - 2015. - T. 5 . - doi : 10.1038/srep08665 . - Iránykód . - arXiv : 1405.6707 . — PMID 25727453 .
Linton C. Freeman. Központi szerep a közösségi hálózatokban: Fogalmi tisztázás // Közösségi hálózatok. - 1979. - 1. évf. , szám. 3 . – S. 215–239 . - doi : 10.1016/0378-8733(78)90021-7 . Az eredetiből archiválva : 2016. február 22.
Linton Freeman. A centralitás mértékeinek halmaza a kölcsönösségen alapulóan // Szociometria. - 1977. - T. 40 , sz. 1 . – 35–41 . - doi : 10.2307/3033543 . — .
Alex Bavelas. Kommunikációs minták feladatorientált csoportokban // J. Acoust. szoc. Am. - 1950. - T. 22 , sz. 6 .
Sabidussi G. Sabidussi. Egy gráf centralitási indexe // Pszichometria. - 1966. - T. 31 , sz. 4 . - doi : 10.1007/bf02289527 . — PMID 5232444 .
Massimo Marchiori, Vito Latora. Harmónia a kisvilágban // Physica A: Statisztikai mechanika és alkalmazásai. - 2000. - T. 285 , sz. 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 , sz. 3 .
Yannick Rochat. A zártság központossága kiterjesztve a nem kapcsolódó gráfokra: The harmonic centrality index // Applications of Social Network Analysis, ASNA 2009 . – 2009.
Ulrik Brandes. Gyorsabb algoritmus a köztiség központosításához // Journal of Mathematical Sociology. - 2001. - T. 25 , sz. 2 . - doi : 10.1080/0022250x.2001.9990249 .
Newman MEJ A hálózatok matematikája .
Katz L. A szociometriai indexből származó új állapotindex // Pszichometria. - 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 , sz. 1 . - doi : 10.1371/journal.pone.0053095 . - Iránykód . — PMID 23349699 .
Mohamamd Reza Faghani. Az XSS férgek terjedésének és észlelési mechanizmusainak tanulmányozása az online közösségi hálózatokban // IEEE Transactions on Information Forensics and Security. - 2013. - T. 8 , sz. 11 . - doi : 10.1109/TIFS.2013.2280884 .
Alvarez-Socorro AJ, Herrera-Almarza GC, González-Díaz LA A különbözőségi mérőszámokon alapuló sajátcentralitás feltárja a komplex hálózatok központi csomópontjait // Scientific Reports. - 2015. - november ( 5. köt. ). - doi : 10.1038/srep17095 . - . — PMID 26603652 .
Braha D., Bar-Yam Y. A központiságtól az ideiglenes hírnévig: Dinamikus központiság összetett hálózatokban // Komplexitás. - 2006. - T. 12 , sz. 2 . - doi : 10.1002/cplx.20156 . - . - arXiv : fizika/0611295 .
Hill SA, Braha D. Az időfüggő összetett hálózatok dinamikus modellje // Physical Review E. - 2010. - Vol. 82 , no. 4 . - doi : 10.1103/physreve.82.046105 . - . - arXiv : 0901.4407 . — PMID 21230343 .
Adaptív hálózatok: elmélet, modellek és alkalmazások / Gross T., Sayama H.. - Springer, 2009.
Holme P., Saramaki J. Temporal Networks. — Springer, 2013.
Tore Opsahl, Filip Agneessens, John Skvoretz. Csomópont-centralitás súlyozott hálózatokban: A fok és a legrövidebb utak általánosítása // Közösségi hálózatok. - 2010. - T. 32 , sz. 3 . - doi : 10.1016/j.socnet.2010.03.006 . Archiválva az eredetiből 2018. február 26-án.
Everett MG, Borgatti SP A központi szerep kiterjesztése. In PJ Carrington, J. Scott és S. Wasserman (szerk.) // Modellek és módszerek a közösségi hálózatok elemzésében. - New York: Cambridge University Press, 2005. - S. 57-76.
Puzis R., Yagil D., Elovici Y., Braha D. Együttműködő támadás az internethasználók névtelensége ellen // Internet Research. - 2009. - T. 19 , sz. 1 . Az eredetiből archiválva: 2013. december 7.

Olvasás további olvasáshoz

Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. és Zlotowski, O. (2005) Központisági indexek. In Brandes, U. and Erlebach, T. (szerk.) Network Analysis: Methodological Foundations , pp. 16-61, LNCS 3418, Springer-Verlag.