Keskeisyys

Keskeisyyden tai keskustan läheisyyden indikaattori graafiteoriassa ja verkkoanalyysissä määrittää graafin tärkeimmät kärjet . Indikaattorin sovelluksilla tunnistetaan sosiaalisen verkoston vaikutusvaltaisimmat henkilöt, Internetin tai suurkaupunkiverkoston keskeiset infrastruktuurin solmut ja taudin kantajat. Sosiologisten primäärilähteiden mittaamiseen käytetään alun perin sosiaalisten verkostojen analysoinnissa kehitettyjä keskeisyyden käsitteitä ja monia keskeisyyden käsitteitä [2] . Näitä mittareita ei pidä sekoittaa solmun vaikutusmittareihin , jotka etsivät kvantitatiivisia ominaisuuksia verkon kunkin solmun vaikutuksesta.

Keskeisyysindeksien määritelmä ja kuvaus

Keskeisyysindeksit ovat vastauksia kysymykseen "Mikä luonnehtii kärjen tärkeyttä?" Vastaus annetaan graafin kärkien reaaliarvoisena funktiona, jonka arvot (oletettavasti) antavat järjestyksen, joka määrittää tärkeimmät solmut [3] [4] [5] .

Sanalla "tärkeys" on laaja valikoima merkityksiä, mikä johtaa moniin erilaisiin keskeisyyden määritelmiin. On ehdotettu kahta luokittelujärjestelmää. "Tärkeyttä" voidaan ymmärtää suhteessa verkon läpi kulkevan virtauksen tyyppiin. Tämä mahdollistaa keskeisyyden luokittelun tärkeänä pidetyn virtaustyypin mukaan [4] . "Tärkeyttä" voidaan vaihtoehtoisesti ymmärtää osallistumisena verkon eheyteen. Tämä mahdollistaa keskeisyyksien luokittelun sen mukaan, miten ne mittaavat osallistumista [6] . Molemmat lähestymistavat jakavat keskeiset asiat eri luokkiin. Yhteen luokkaan sopiva keskus on usein sopimaton, kun sitä sovelletaan toiseen kategoriaan [4] .

Jos keskusyksiköt luokitellaan niiden osallistumisen perusteella, käy selväksi, että useimmat keskusyksiköt kuuluvat samaan kategoriaan. Tietystä solmusta lähtevien reittien lukumäärä eroaa vain siinä, kuinka reitit määritetään ja lasketaan. Tämän ryhmän sopimusrajoitukset mahdollistavat reittien spektrin keskeisyyksien kuvauksen pituudesta yksi ( yhteysaste ) rajoittamattomiin reitteihin ( vaikutusaste ) [3] [7] . Havainto, että monet keskusyksiköt jakavat nämä linkit, selittää näiden indeksien välisen korkean korrelaation.

Verkon virtojen kuvaus

Verkostoa voidaan pitää kuvauksena poluista, joita pitkin jokin virtaa. Tämä mahdollistaa kuvauksen, joka perustuu keskitetysti koodattuihin virtaustyyppeihin ja polkutyyppeihin. Kulku voi perustua siirtoihin, joissa jokainen jakamaton elementti siirtyy solmupisteestä toiseen, samalla tavalla kuin pakettien toimitus postista asiakkaan kotiin. Toisessa tapauksessa toistetaan elementti, joka siirtyy seuraavaan solmuun, joten sekä lähteellä että kohteella on tämä elementti. Esimerkki tällaisesta tapauksesta on huhujen leviäminen, jossa tietoa jaetaan yksityisesti, jolloin sekä lähde että kohde ilmoitetaan prosessin lopussa. Viimeinen tapaus on rinnakkaiseteneminen, jossa elementti etenee useiden linkkien kautta samanaikaisesti, kuten radiolähetys, joka antaa saman tiedon useille kuulijoille samanaikaisesti [4] .

Vastaavasti polun tyyppi voidaan rajoittaa: geodetiikka (lyhyimmät polut), polut (yhdessäkään kärjessä ei käy useammin kuin kerran), polut (kärkissä voidaan käydä useita kertoja, mutta mitään reunaa ei kuljeta kahdesti) tai reittejä (sekä kärjet että reunat voi esiintyä useita kertoja) [4] .

Kuvaus kävelyrakenteen mukaan

Vaihtoehtoinen luokittelu voidaan johtaa tavasta, jolla keskeisyys on rakennettu. Tämä taas johtaa jakaantumiseen kahteen luokkaan - radiaaliseen tai mediaaniin. Säteittäiset keskipisteet laskevat polkujen määrän, jotka alkavat/päättyvät tiettyyn kärkeen. Liitettävyysasteet ja vaikutusasteet ovat esimerkkejä keskeisyyden säteittäisistä mitoista, jotka laskevat yhden tai rajoittamattoman pituisten polkujen lukumäärän. Mediaanikeskipisteet laskevat polut, jotka kulkevat tietyn kärjen kautta. Kanoninen esimerkki on Freeman-välityksen aste , lyhimpien polkujen määrä, jotka kulkevat tietyn kärjen kautta [6] .

Samoin laskuri voi kaapata joko reitin määrän tai pituuden . Volyymi on tietyntyyppisten reittien kokonaismäärä. Kolme esimerkkiä edellisestä kappaleesta kuuluu tähän luokkaan. Pituus on etäisyys tietystä pisteestä graafin muihin kärkipisteisiin. Läheisyysaste muihin Freeman-solmuihin, geodeettinen kokonaisetäisyys tietystä kärjestä kaikkiin muihin kärkipisteisiin, on tunnetuin esimerkki [6] . Huomaa, että tämä luokittelu riippuu laskettavien reittien tyypistä (eli reitit, piirit, polut, geodetiikka).

Borgatti ja Everett katsoivat, että tämä typologia antaa käsityksen siitä, miten keskeisyyden mittareita voidaan verrata. Tässä 2x2-luokituksessa samaan soluun kuuluvat keskipisteet ovat riittävän samanlaisia ollakseen hyväksyttäviä vaihtoehtoja, ja voidaan kohtuudella verrata, mikä pistemäärä on paras tietylle ongelmalle. Eri solujen mittaukset ovat kuitenkin täysin erilaisia. Suhteellisen soveltuvuuden määrittäminen voi tapahtua vain ennalta määrätyssä kontekstissa, mikä kategoria on sopivampi [6] .

Spektrissä olevat säteittäiset volyymikeskipisteet

Reittirakenteen kuvaus osoittaa, että lähes kaikki käytetyt keskipisteet ovat säteittäis-tilavuusmittoja. Tämä antaa varmuutta siitä, että kärkikeskeisyys on funktio niiden kärkien keskeisyydestä, joihin se liittyy. Keskeisyydet eroavat tavasta, jolla ne yhdistetään.

Bonacic osoitti, että jos assosiaatio määritellään poluilla, niin keskusryhmien perhe voidaan määritellä tarkasteltavana olevien polkujen pituuksilla [3] . Yhteysaste laskee yhden pituisten reittien määrän , vaikutuksen aste laskee rajoittamattoman pituiset reitit. Vaihtoehtoiset yhdistysten määritelmät ovat myös mahdollisia. Alfa-keskeisyys mahdollistaa ulkoisten vaikutuslähteiden pisteille. Estradan osagraafin keskiarvo laskee vain suljetut polut (kolmiot, nelikulmiot, ...).

Tällaisten mittojen ydin on havainto, että graafin vierekkäisyysmatriisin asteet antavat polkujen määrän, joiden pituus on yhtä suuri kuin aste. Vastaavasti matriisieksponentti liittyy läheisesti tietynpituisten polkujen määrään. Viereisyysmatriisin ensimmäinen muunnos mahdollistaa erityyppisten reittien määrän määrittämisen. Kummassakin lähestymistavassa kärkikeskeisyys voidaan ilmaista äärettömänä summana tai

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

matriisitehoille tai

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

matriisieksponentille, missä

$k$ sama kuin reitin pituus,
$A_{R}$ on muunnettu viereisyysmatriisi, ja
$\beeta$ on kompensoiva parametri, joka varmistaa summan konvergenssin.

Bonacic-mittojen perhe ei muuta viereisyysmatriisia. Alpha centrality korvaa viereisyysmatriisin resoluutiollaan . Aligraafin keskitys korvaa viereisyysmatriisin sen jäljellä. Viereisyysmatriisin alkuperäisestä muunnoksesta huolimatta kaikilla näillä lähestymistavoilla on yhteinen rajoittava käyttäytyminen. Koska se pyrkii nollaan, indeksi konvergoi liitettävyysasteeseen . Maksimiarvoon pyrittäessä indeksi konvergoi vaikutuksen asteeseen [7] . $\beeta$ $\beeta$

Peliteoreettinen keskeisyys

Useimpien yllä olevien standardimittausten yhteinen piirre on, että ne arvioivat solmun tärkeyden keskittyen vain solmun omaan rooliin. Monissa sovelluksissa tämä lähestymistapa ei kuitenkaan ole riittävä, koska solmuvuorovaikutus voidaan havaita, jos toimenpiteitä sovelletaan ryhmäsolmuihin.

Harkitse esimerkiksi epidemian pysäyttämisen ongelmaa. Kun katsot yllä olevaa verkkokuvaa, mitkä solmut tulisi rokottaa? Yllä kuvattujen toimenpiteiden perusteella haluamme tunnistaa taudin leviämisen kannalta tärkeimmät solmut. Solmujen yksittäisiin ominaisuuksiin keskittyvien keskitettyjen lähestymistapojen käyttäminen ei ehkä ole hyvä idea. Punaisen laatikon solmut eivät yksin pysty pysäyttämään taudin leviämistä, mutta ryhmänä tarkasteltuna näemme selvästi, että ne voivat pysäyttää taudin, jos se alkaa solmuista , , . Peliteoreettiset keskeisyydet yrittävät ottaa kuvattuja ongelmia ja mahdollisuuksia huomioon peliteorian työkaluilla. Michalakin (et al.) [8] ehdottama lähestymistapa käyttää Shapley-vektoria . Shapley-vektorin laskennan monimutkaisuuden (ajallisesti) vuoksi suurin osa vaivannäöstä tällä alueella investoidaan uusien algoritmien ja menetelmien kehittämiseen, jotka perustuvat verkkoon tiettyyn topologiaan ja ongelman erityisluonteeseen. Tämä lähestymistapa voi vähentää algoritmin aikamonimutkaisuutta eksponentiaalisesta polynomiin. $v_{1}$ ${\displaystyle v_{4))$ $v_{5}$

Tärkeitä rajoituksia

Keskeisyysindekseillä on kaksi tärkeää rajoitusta, joista toinen on ilmeinen, toinen on hienovarainen. Ilmeinen rajoitus on, että yhdelle sovellukselle optimaalinen keskitys ei useinkaan ole optimaalinen toiselle. Lisäksi, jos näin ei olisi, niin monia erilaisia keskuksia ei tarvittaisi. Esimerkki tästä ilmiöstä on Crackhardin leija , jolle kolme erilaista keskeisyyden käsitettä tuottaa kolme erilaista keskeisintä kärkeä [9] .

Hienovarainen rajoitus on se, että vallitsee yleinen väärinkäsitys, jonka mukaan kärkien keskeisyys heijastaa kärkien suhteellista tärkeyttä. Keskeisyysindeksit kehitettiin eksplisiittisesti rankingista, mikä mahdollistaa tärkeimpien pisteiden valinnan [3] [4] . He tekevät sen hyvin mainittujen rajoitusten puitteissa. Niitä ei ole suunniteltu mittaamaan solmuja yleisesti. Viime aikoina verkkofyysikot ovat alkaneet kehittää solmuvaikutusmittareita tämän ongelman ratkaisemiseksi.

Virhe on kaksijakoinen. Ensinnäkin sijoitus vain kärkien järjestyksessä, koska niiden tärkeys ei heijasta tärkeyseroa eri sijoitustasojen välillä. Tätä tosiasiaa voidaan lieventää soveltamalla Freemanin keskeisyyttä kyseessä olevaan keskeisyyden mittaan, mikä antaa jonkinlaisen käsityksen solmujen tärkeydestä niiden erilaisten keskeisyyspisteiden perusteella. Lisäksi Freeman-keskeisyys mahdollistaa joidenkin verkkojen vertailun korkeimman arvon omaavien solmujen indikaattoreiden suhteen [10] .

Toiseksi ominaisuudet, jotka (oikein) heijastavat tietyn verkon/sovelluksen tärkeimpiä pisteitä, eivät välttämättä yleisty muihin kärkipisteisiin. Useimmille muille verkon solmuille ranking voi olla merkityksetöntä [11] [12] [13] [14] . Tämä selittää esimerkiksi sen, miksi Google-kuvahaun ensimmäiset tulokset näkyvät riittävässä järjestyksessä. PageRank on erittäin epävakaa mitta, joka näyttää usein päinvastaisen sijoituksen pienen hakuparametrin muutoksen jälkeen [15] .

Vaikka mahdottomuus yleistää keskeisyysindeksiä muuhun verkkoon ei ehkä vaikuta ensi silmäyksellä itsestään selvältä, se seuraa suoraan yllä olevista määritelmistä. Monimutkaisilla verkoilla on heterogeeninen topologia. Missä määrin optimaalinen mitta riippuu tärkeimpien pisteiden verkkorakenteesta, siinä määrin, että näille pisteille optimaalinen mitta ei ole optimaalinen muulle verkolle [11] .

Yhteydet

Historiallisesti ensimmäinen ja käsitteellisesti yksinkertaisin käsite on liitettävyyden aste , joka määritellään solmuun osuvien linkkien lukumääräksi (eli solmussa olevien linkkien lukumääräksi). Aste voidaan tulkita solmun suorana riskinä saada kiinni verkon kautta kulkevasta jostakin (kuten viruksesta tai jostain tiedosta). Kun kyseessä on suunnattu verkko (jossa linkit on suunnattu), määritämme yleensä kaksi erilaista liitettävyysastetta, nimittäin in -degree ja out -degree . Vastaavasti in-aste on solmun kanssa olevien yhteyksien lukumäärä ja ulkoaste on solmun yhteyksien lukumäärä muihin solmuihin. Kun yhteys liittyy johonkin positiiviseen näkökohtaan, kuten ystävyyteen tai yhteistyöhön, niin in-tutkinto tulkitaan usein eräänlaiseksi suosioksi ja ulko-aste sosiaalisuudeksi.

Tietyn graafin kärjen liitettävyyden aste kärkien ja reunojen kanssa määritellään seuraavasti $v$ $G:=(V,E)$ $|V|$ $|E|$

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

Graafin kaikkien solmujen liitettävyysasteen laskeminen vie aikaa graafin tiheässä vierekkäisyysmatriisiesityksessä ja aikaa reunojen harvassa matriisiesityksessä . $\Theta (V^{2})$ $\Theta (E)$

Solmutason keskeisyyden määritelmä voidaan laajentaa koko graafiin, ja tässä tapauksessa puhutaan graafisen keskeisyydestä [10] . Antaa olla solmu, jolla on korkein liitettävyys . Olkoon yhdistetty graafi solmuilla, joka maksimoi seuraavan arvon (jossa solmu, jolla on korkein liitettävyys : $v*$ $G$ $X:=(Y,Z)$ $|Y|$ $y*$ $X$

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

Vastaavasti graafin keskeisyysaste on yhtä suuri kuin: $G$

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

Arvo on maksimi, kun graafi sisältää yhden keskussolmun, johon kaikki muut solmut on kytketty ( tähtikuvaaja ), jolloin $H$ $X$

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

Siis mille tahansa kaaviolle $G:=(V,E),$

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

Läheisyys muihin solmuihin

Yhdistetyssä graafissa solmun normalisoitu läheisyysaste on yhtä suuri kuin solmun ja kaikkien muiden graafin solmujen välisen lyhimmän polun keskimääräinen pituus . Sitten mitä keskeisempi solmu on, sitä lähempänä kaikkia muita solmuja se on.

Alex Bavelas (1950) määritteli läheisyysasteen etäisyyden käänteisarvoksi [16] [17] , ts.

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

jossa on yhtä suuri kuin pisteiden välinen etäisyys ja . Kuitenkin, kun puhutaan läheisyysasteesta muihin solmuihin, ihmiset tarkoittavat yleensä sen normalisoitua muotoa, joka on yleensä saatu edellisestä kaavasta kertomalla , missä on yhtä suuri kuin kaavion solmujen lukumäärä. Mitoitus mahdollistaa erikokoisten kaavioiden solmujen vertailun. ${\näyttötyyli d(y,x)}$ $x$ $y$ $N-1$ $N$

Etäisyyden huomioon ottaminen kaikista muista solmuista tai muihin solmuihin ei sovellu suuntaamattomiin graafisiin, kun taas suunnatuissa graafisissa ne antavat aivan erilaisia tuloksia. Esimerkiksi verkkosivustolla voi olla korkea läheisyys lähteviin kohteisiin, mutta alhainen saapuvan liikenteen läheisyys).

Harmoninen keskeisyys

Graafissa (ei välttämättä yhdistetyssä) harmoninen keskeisyys kääntää summauksen ja inversion toiminnot läheisyysasteen määrittämisessä:

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

missä , jos ei ole polkua osoitteesta . Harmoninen keskeisyys voidaan normalisoida jakamalla , missä on yhtä suuri kuin graafin solmujen lukumäärä. ${\näyttötyyli 1/d(y,x)=0}$ $y$ $x$ $N-1$ $N$

Harmonista keskeisyyttä ehdottivat Marchiori ja Lathora (2000) [18] , sitten itsenäisesti Dekker (2005) nimellä arvottu keskeisyys [19] ja Rochat (2009) [ 20] .

Sovittelun tutkinto

Välitysaste on graafin kärjen keskeisyyden mitta (on myös reunavälitysaste , jota ei käsitellä tässä). Välityksen aste ilmaisee, kuinka monta kertaa solmu siltaa lyhimmän polun kahden muun solmun välillä. Linton Freeman esitteli sovittelun asteen mittaamaan kvantitatiivista ilmaisua ihmisen vuorovaikutuksesta muiden ihmisten kanssa sosiaalisessa verkostossa [21] . Tässä konseptissa pisteillä, joilla on suurin todennäköisyys olla satunnaisesti valitulla lyhimmällä polulla kahden satunnaisesti valitun kärjen välillä, on korkea välitysaste.

Huippupisteen välitysaste graafissa , jossa on pisteitä, lasketaan seuraavasti: $v$ $G:=(V,E)$ $V$

Kullekin pisteparille ( s , t ) lasketaan niiden väliset lyhyimmät polut .
Määritä kullekin pisteparille ( s , t ) lyhimpien polkujen murto-osa, joka kulkee kyseisen kärjen (tässä piste v ) läpi.
Teemme nämä osuudet yhteenvetona kaikista kärkipareista ( s , t ).

Tiivisemmin sovitteluaste voidaan esittää muodossa [22] :

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

jossa on yhtä suuri kuin lyhimpien polkujen kokonaismäärä solmusta solmuun ja on yhtä suuri kuin tällaisten läpi kulkevien polkujen lukumäärä . Välityksen aste voidaan normalisoida jakamalla pisteparien lukumäärällä v , joka on yhtä suuri suunnatuille graafiille ja yhtä suuri kuin suuntaamattomille graafeille . Esimerkiksi ohjaamattomassa tähdessä keskipisteellä (joka sisältyy mihin tahansa mahdolliseen lyhimpään polkuun) on välitysaste (1, jos se on normalisoitu), kun taas lehdillä (jotka eivät sisälly mihinkään lyhimpään polkuun) on välitysaste 0. ${\displaystyle \sigma _{st))$ $s$ $t$ $\sigma _{st}(v)$ $v$ ${\näyttötyyli (n-1) (n-2)}$ $(n-1) (n-2)/2$ $(n-1) (n-2)/2$

Laskennallisesti katsottuna sekä välitysaste että graafin kaikkien kärkien läheisyysasteet sisältävät lyhimpien polkujen laskemisen graafin kaikkien pisteparien välillä, mikä vie aikaa käytettäessä Floyd-Warshall-algoritmia . Harvoissa kaavioissa Johnsonin algoritmi voi kuitenkin olla tehokkaampi ajassa . Painottamattomien graafien tapauksessa laskelmat voidaan suorittaa Brandes-algoritmilla [22] , mikä vie aikaa . Tyypillisesti nämä algoritmit olettavat, että graafit ovat suuntaamattomia ja liittyvät silmukoiden ja useiden reunojen resoluutioon. Kun työskentelet verkkokaavioiden kanssa, jotka edustavat yksinkertaisia yhteyksiä, joissa ei usein ole silmukoita tai useita reunoja (jossa reunat edustavat ihmisten välisiä yhteyksiä). Tässä tapauksessa Brandesin algoritmia käyttäen lopullinen keskeisyysindeksi jaetaan kahdella, jotta jokainen lyhin polku lasketaan kahdesti [22] . $O(V^{3})$ $O(V^{2}\log V+VE)$ $O(VE)$

Vaikutusaste

Vaikutusaste on verkon solmun vaikutuksen mitta . Se antaa suhteelliset pisteet kaikille verkon solmuille sen käsitteen perusteella, että linkit korkean pistemäärän solmuihin vaikuttavat enemmän kyseisen solmun pistemäärään kuin sama linkki matalan pistemäärän solmuun [23] [5] [5] . Googlen PageRank ja Katzin solmukeskeisyys ovat muunnelmia vaikutusasteesta [24] .

Vaikutusasteen etsiminen viereisyysmatriisin avulla

Annetulle graafille , jossa on pisteet, olkoon viereisyysmatriisi , eli jos kärki on yhdistetty kärkeen ja muuten. Suhteellinen kärkikeskeisyysindeksi voidaan määritellä seuraavasti $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}

missä on kärjen naapureiden joukko ja on vakio. Pienten muunnosten jälkeen tämä lauseke voidaan kirjoittaa uudelleen vektorimerkinnällä yhtälöksi ominaisvektorille $M(v)$ $v$ $\lambda$

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

Yleensä on olemassa monia erilaisia ominaisarvoja , joille on olemassa nollasta poikkeava ominaisvektori. Koska vierekkäisyysmatriisin elementit ovat ei-negatiivisia, on olemassa yksi suurin ominaisarvo, joka on todellinen ja positiivinen Frobenius–Perron-lauseen mukaan . Tämä suurin ominaisarvo antaa halutun keskeisen arvon [23] . Siihen liittyvä ominaisvektorikomponentti antaa pisteen suhteellisen keskeisen aseman verkossa. Ominaisuusvektori määritellään kertoimeen asti, jolloin vain kärkikeskipisteiden suhde on täysin määritelty. Eksponentin itseisarvon määrittämiseksi on tarpeen normalisoida ominaisvektori esimerkiksi siten, että kaikkien pisteiden summa on yhtä suuri kuin 1 tai normalisoida pisteiden kokonaismäärällä n . Tehomenetelmä on yksi monista ominaisarvon johtamisalgoritmeista , joita voidaan käyttää tämän hallitsevan ominaisvektorin löytämiseen [24] . Lisäksi tämä voidaan yleistää niin, että matriisin A alkiot voivat olla reaalilukuja, jotka edustavat sidoksen vahvuutta, kuten stokastisessa matriisissa . $\lambda$ $v^{th}$ $v$

Keskustelu Katzin mukaan

Kacin [25] mukaan keskeisyys on yleistys yhteysasteesta. Yhteydet mittaavat suorien naapureiden määrää, ja Kac-keskeisyys mittaa kaikkien solmujen lukumäärää, jotka voidaan yhdistää poluilla, samalla kun se rankaisee etäisiä solmuja. Matemaattisesti tämä keskeisyys määritellään seuraavasti

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

missä on vaimennuskerroin väliltä . $\alpha$ $(0,1)$

Katzin mukaan keskeisyys voidaan nähdä vaikutuksen asteen muunnelmana. Toinen keskeisyyden muoto Kacin mukaan on

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

Vaikutusasteeseen verrattuna se korvataan $x_{j}$ $x_{j}+1.$

Osoitettiin [26] , että pääominaisvektori (vastaa viereisyysmatriisin suurinta ominaisarvoa ) on Kac-keskeisyysraja, kun k lähestyy alhaalta. $A$ $\alpha$ ${\tfrac {1}{\lambda ))$

PageRank

PageRank täyttää seuraavan yhtäläisyyden

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

missä

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

on yhtä suuri kuin solmun naapurien lukumäärä (tai suunnatun graafin lähtevien yhteyksien lukumäärä). Verrattuna Katzin vaikutuksen ja keskeisyyden asteeseen, skaalaustekijä on tärkeä ero . Ero PageRankin ja vaikutuksen asteen välillä on siinä, että PageRank-vektori on vasen ominaisvektori (eli transponoidun matriisin ominaisvektori, huomaa, että kertoimella on käänteinen indeksien järjestys) [27] . $j$ $L(j)$ ${\displaystyle a_{ji))$

Perkolaatiokeskeisyys

Yksittäisen solmun "tärkeyden" määrittämiseksi monimutkaisessa verkossa on joukko keskitetystiä. Ne heijastavat kuitenkin solmun tärkeyttä puhtaasti topologisesti, eikä solmun arvo riipu millään tavalla solmun "tilasta". Arvo pysyy vakiona verkon dynamiikasta riippumatta. Tämä pätee jopa mitattuihin sovittelutoimenpiteisiin. Solmu voi kuitenkin myös sijaita keskeisesti välitysasteen tai muun keskeisyyden mittaan nähden, mutta se ei voi olla "keskitettynä" sellaisen verkon kontekstissa, jossa on vuotoa. "Tartunnan" vuotamista tapahtuu monimutkaisissa verkoissa useissa skenaarioissa. Virus- tai bakteeri-infektio voi levitä ihmisten sosiaalisten verkostojen kautta, joita kutsutaan kontaktiverkostoiksi. Taudin leviämistä voidaan tarkastella myös korkealla abstraktiolla, kun tarkastellaan kaupunkien tai taajamaverkostoa, joka on yhdistetty teiden, rautateiden tai lentoyhtiöiden kautta. Tietokonevirukset voivat levitä tietokoneverkoissa. Huhut tai uutiset yritystarjouksista ja -sopimuksista voivat levitä myös ihmisten sosiaalisessa mediassa. Kaikissa näissä skenaarioissa "infektio" leviää monimutkaisen verkon linkkien kautta muuttaen solmujen "tiloja" palautuvasti tai peruuttamattomasti. Esimerkiksi epidemiologisessa skenaariossa yksilöt siirtyvät "herkästä" tilasta "tartunnan saaneeseen" tilaan. Tiettyjen solmujen tilat "tartunta" leviämisen yhteydessä voivat saada binääriarvoja (kuten "uutinen vastaanotettu/ei vastaanotettu"), erillisiä arvoja (herkkä/tartunnan saanut/parantunut) tai jopa jatkuvia arvoja. (kuten tartunnan saaneiden ihmisten osuus kaupungissa). Yhteistä kaikissa näissä skenaarioissa on, että "tartunnan" leviäminen johtaa muutokseen verkkosolmujen tilassa. Tätä silmällä pitäen on ehdotettu perkolaatiokeskeisyyttä ( PC ) , joka mittaa solmun tärkeyttä verkon kautta tapahtuvaan perkolaatioon osallistumisen kannalta. Tätä toimenpidettä ehdottivat Pairavinan ym . [28] .

Vuotokeskeisyys määritellään tietylle solmulle ja tiettynä ajankohtana solmun läpi kulkevien "tihkupolkujen" osuutena. "Vuotopolku" on lyhin polku solmuparin välillä, kun lähdesolmu on vuototilassa (esim. Kohdesolmu voi olla perkolaatiotilassa, ei-perkolaatiotilassa tai osittaisessa perkolaatiotilassa.

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^{ TV}}}

missä on lyhimpien reittien kokonaismäärä solmusta solmuun ja on tällaisten läpi kulkevien polkujen lukumäärä . Solmun vuototilaa hetkellä merkitään ja on olemassa kaksi erikoistapausta, milloin mikä osoittaa tiukan tilan hetkellä , ja milloin , joka tarkoittaa täydellistä vuotoa hetkellä . Näiden arvojen väliset arvot tarkoittavat osittaisia vuototiloja (esimerkiksi kaupunkiverkostossa tämä voi olla tartunnan saaneiden ihmisten prosenttiosuus kaupungissa). ${\displaystyle \sigma _{sr))$ $s$ $r$ $\sigma _{sr}(v)$ $v$ $i$ $t$ ${\näyttötyyli {x^{t}}_{i}}$ ${x^{t}}_{i}=0$ $t$ ${x^{t}}_{i}=1$ $t$

Vuotopolun painotukset riippuvat lähdesolmuille osoitetuista vuototasoista perustuen oletukseen, että mitä korkeampi lähdesolmun vuototaso on, sitä tärkeämpiä kyseisestä solmusta lähtevät reitit. Solmut, jotka sijaitsevat lyhimmällä polulla alkaen korkean perkolaation solmuista, ovat siksi mahdollisesti tärkeämpiä perkolaatiolle. PC:n määritelmää voidaan myös laajentaa kattamaan myös kohdesolmupainot. Vuotokeskeisyyden laskenta suoritetaan ajoissa nopeasta Brandes-algoritmista lainatulla tehokkaalla toteutuksella, ja jos laskelmissa on otettava huomioon päätesolmujen painot, pahin tapausaika on . $O(NM)$ $O(N^{3})$

Crossclick-keskeisyys

Yksittäisen solmun poikkiklikkikeskeisyys kompleksisessa graafissa määrittää solmun yhteydet eri klikkeihin . Solmu, jolla on korkea ristiinnapsautuskeskeisyys, edistää tiedon tai sairauden leviämistä kaaviossa. Klikit ovat aligraafia, joissa jokainen solmu on yhteydessä kaikkiin muihin klikkisolmuihin. Solmun ristiklikkauskeskeisyys tietylle graafille , jossa on kärkipisteet ja reunat, on merkitty ja yhtä suuri kuin niiden klikkien lukumäärä, joihin kärkipiste kuuluu. Tätä mittaa käytettiin Faganin paperissa [29] , mutta Everett ja Borgatti ehdottivat sitä ensimmäisen kerran vuonna 1998 nimellä "klikkipäällekkäisyys keskeinen". $v$ $G:=(V,E)$ $|V|$ $|E|$ $X(v)$ $v$

Freeman-keskeisyys

Minkä tahansa verkon keskeisyys on mitta siitä, kuinka keskeinen sen keskeisin solmu on muihin solmuihin verrattuna [10] . Keskeisyyden mitta lasketaan sitten (a) verkon keskeisimmän solmun ja kaikkien muiden solmujen välisten keskeisyyserojen summana ja (b) jaetaan tämä arvo minkä tahansa verkon minkä tahansa verkon teoreettisesti suurimmalla tällaisella erojen summalla. samankokoinen [10] . Silloin millä tahansa keskeisyysmitalla voi olla oma keskeisyysmitta. Muodollisesti, jos on pisteen keskeisyysmitta , if on suurin tällainen mitta verkossa, ja jos $C_{x}(p_{i})$ $i$ $C_{x}(p_{*})$

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

on suurin pisteen keskeisyyden erojen summa mille tahansa graafille, jossa on sama määrä solmuja, silloin verkon keskeisyys on [10] $C_{x}$

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

Eropohjaiset keskeisen mittarit

Saadakseen parempia tuloksia tietyn verkon solmujen luokittelussa, Alvarez-Socorro (et al.) [30] käyttää erilaisuuden mittaa (luokitteluteorialle ja data-analyysille ominaista) parantaakseen keskeisyyden mittaa monimutkaisissa verkoissa. Tätä havainnollistaa vaikutuksen aste laskemalla kunkin solmun keskeisyys ratkaisemalla ominaisarvoongelma

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

jossa (koordinaattinen tulo), ja on mielivaltainen erilaisuusmatriisi , joka on määritelty erilaisuusmitan avulla. Esimerkiksi kaavan antaman Jaccardin erilaisuuden kautta $W_{ij}=A_{ij}D_{ij}$ $D_{ij}$

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

Tämän toimenpiteen avulla voimme kvantifioida kunkin solmun topologisen panoksen (jota kutsutaan panoskeskeisyydeksi) tietyn solmun keskeisyyteen, jolloin saadaan suurempi paino/tärkeyssuhde niille solmuille, joilla on suurempi ero, koska tämä sallii tietyn solmun saavuttaa solmuja, jotka ei ole tavoitettavissa suoraan.

Huomaa, että on ei-negatiivinen, koska ja ovat ei-negatiivisia matriiseja, joten voimme käyttää Frobenius-Perron-lausetta varmistaaksemme, että yllä olevan ongelman ratkaisu on ainutlaatuinen ei-negatiivisen c :n kanssa , mikä mahdollistaa sen, että voimme saada jokaisessa verkon solmussa. Siten i:nnen solmun keskeisyys on yhtä suuri kuin $W$ $A$ $D$ ${\displaystyle \lambda =\lambda _{max))$

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

missä on yhtä suuri kuin verkon solmujen lukumäärä. Alvarez-Socorro (et al.) [31] testasi joitakin verkostoja ja erilaisuusmittareita [31] ja tutkituissa tapauksissa saatiin parempia tuloksia. $n$

Yleistykset

Empiiriset ja teoreettiset tutkimukset yleistävät keskeisyyden käsitteen staattisten verkkojen kontekstissa dynaamisiin keskeisyyksiin [32] ajasta riippuvaisten ja lyhytikäisten verkkojen yhteydessä [33] [34] [35] .

Painotettujen verkkojen yleistystä varten katso Opsal ym . [36] .

Keskeisyyden käsite on myös yleistynyt ryhmätasolle. Esimerkiksi ryhmävälityksen aste osoittaa ryhmän läpi kulkevien solmuparien (eli minimipituisten polkujen) osuuden ryhmään kuulumattomista solmuista [37] [38] .

Katso myös

Muistiinpanot

↑ Osa terminologiasta on poimittu A. S. Semenovin ja M. V. Bartoshin artikkelista "ASIAN INTERNETIN VERKOSTON STABILITEETIN ARVIOINTI SUHTEIDEN KESKUSTEN INDIKAATTOREILLA" . Venäjänkielisen kirjallisuuden termit eivät ole vakiintuneet. Joten Evin I. A.:n artikkelissa Monimutkaiset verkot: Johdanto teoriaan termin "välitysaste" sijasta käytetään termejä "solmukuorma", "suurin tärkeät yhteydet". Verkkomittarit -sivulla termin "yhteysaste" sijasta käytetään kirjaimellista käännöstä "keskeisyys asteen mukaan" termien "aste ..." - "keskeisyys ..." sijaan. Joskus termiä "keskeisyys" käytetään termin "keskeisyys" sijasta.
↑ Newman, 2010 .
↑ 1 2 3 4 Bonacich, 1987 , s. 1170-1182.
↑ 1 2 3 4 5 6 Borgatti, 2005 , s. 55–71.
↑ 1 2 3 Negre, Morzan, Hendrickson et al., 2018 , s. E12201-E12208.
↑ 1 2 3 4 Borgatti, Everett, 2006 , s. 466–484.
↑ 1 2 Benzi, Klymko, 2013 , s. 686–706.
↑ Michalak, Aadithya, Szczepański, Ravindran, Jennings, 2013 , s. 607-650.
↑ Krackhardt, 1990 , s. 342-369.
↑ 1 2 3 4 5 Freeman, 1979 , s. 215–239.
↑ 12 Asianajaja , 2015 , s. 8665.
↑ da Silva, Viana, da F. Costa, 2012 , s. P07005.
↑ Bauer ja Lizier, 2012 , s. 68007.
↑ Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013 , s. 1–13.
↑ Ghoshal, Barabsi, 2011 , s. 394.
↑ Bavelas, 1950 , s. 725–730.
↑ Sabidussi, 1966 , s. 581–603.
↑ Marchiori, Latora, 2000 , s. 539–546.
↑ Dekker, 2005 .
↑ Rochat, 2009 .
↑ Freeman, 1977 , s. 35–41.
↑ 1 2 3 Brandes, 2001 , s. 163-177.
↑ 12 Newman , 2007 , s. 1-12.
↑ 12 American Mathematical Society . (määrätön)
↑ Katz, 1953 , s. 39–43.
↑ Bonacich, 1991 , s. 155-168.
↑ Miten Google luokittelee verkkosivut? Arkistoitu alkuperäisestä 31. tammikuuta 2012. 20Q: Verkkoelämästä
↑ Piraveenan, Prokopenko, Hossain, 2013 , s. e53095.
↑ Faghani, 2013 , s. 1815-1826
↑ Alvarez-Socorro, Herrera-Almarza, González-Díaz, 2015 , s. 17095.
↑ Alvarez-Socorro AJ, Herrera-Almarza LA, González-Díaz. Erilaisuusmittauksiin perustuva lisätieto ominaiskeskityksestä paljastaa monimutkaisten verkkojen keskussolmut . Nature Publishing Group. (määrätön)
↑ Braha, Bar-Yam, 2006 , s. 59–63.
↑ Hill, Braha, 2010 , s. 046105.
↑ Gross, Sayama, 2009 .
↑ Holme, Saramaki, 2013 .
↑ Opsahl, Agneessens, Skvoretz, 2010 , s. 245–251.
↑ Everett, Borgatti, 2005 , s. 57–76.
↑ Puzis, Yagil, Elovici, Braha, 2009 .

Kirjallisuus

Newman MEJ Networks: Johdanto. — Oxford, Iso-Britannia: Oxford University Press, 2010.
Newman MEJ Verkostojen matematiikka, // The New Palgrave Encyclopedia of Economics . - Basingstoke, Palgrave Macmillan, 2007.

Phillip Bonacich. Valta ja keskeisyys: Toimenpiteiden perhe // American Journal of Sociology. - 1987. - T. 92 , no. 5 . - doi : 10.1086/228631 .
Bonacich P. Samanaikaiset ryhmä- ja yksilökeskeisyydet // Sosiaaliset verkostot. - 1991. - T. 13 , no. 2 . - doi : 10.1016/0378-8733(91)90018-o .
Stephen P. Borgatti. Keskeisyys ja verkkovirta // Sosiaaliset verkostot. - 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. Omavektorikeskeisyys proteiinien allosteeristen reittien karakterisointiin // Proceedings of the National Academy of Sciences. - 2018. - T. 115 . - doi : 10.1073/pnas.1810452115 .
Stephen P. Borgatti, Martin G. Everett. Graafiteoreettinen näkemys keskeisyydestä // Sosiaaliset verkostot. - 2006. - T. 28 , no. 4 . - doi : 10.1016/j.socnet.2005.11.005 .
Michele Benz, Christine Klymko. Matriisianalyysi eri keskitetyistä mittareista // SIAM Journal on Matrix Analysis and Applications. - 2013. - T. 36 , no. 2 . - doi : 10.1137/130950550 . - arXiv : 1312.6722 .
Tomasz P. Michalak, Karthik V. Aadithya, Piotr L. Szczepański, Balaraman Ravindran, Nicholas R. Jennings. Shapley-arvon tehokas laskenta peliteoreettiselle verkkokeskeisyydelle // Journal of Artificial Intelligence Research. - 2013. - T. 46 .
David Krackhardt. Poliittisen maiseman arviointi: rakenne, kognitio ja valta organisaatioissa // Administrative Science Quarterly. - 1990. - Kesäkuu ( nide 35 , numero 2 ). - doi : 10.2307/2393394 . — .
Renato da Silva, Matheus Viana, Luciano da F. Costa. Epidemian ennustaminen levittäjien yksittäisten ominaisuuksien perusteella // J. Stat. Mech.: Theory Exp.. - 2012. - T. 2012 . - doi : 10.1088/1742-5468/2012/07/p07005 . - . - arXiv : 1202.0024 .
Frank Bauer, Joseph Lizier. Vaikuttavien levittäjien tunnistaminen ja tartuntamäärien tehokas arvioiminen epidemiamalleissa: Kävelylaskennan lähestymistapa // Europhys Lett. - 2012. - T. 99 . - S. 68007 . - doi : 10.1209/0295-5075/99/68007 . - . - arXiv : 1203.0502 .
Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefanic. Epidemiakeskeisyys – onko verkon oheissolmuilla aliarvioitu epidemiavaikutus? // The European Physical Journal B. - 2013. - T. 86 , nro 10 . - doi : 10.1140/epjb/e2013-31025-5 . - arXiv : 1110.2558 .
Ghoshal G., Barabsi AL Luokituksen vakaus ja superstabiilit solmut monimutkaisissa verkoissa. // NatCommun. - 2011. - T. 2 . - doi : 10.1038/ncomms1396 . — .
Glenn lakimies. Verkon kaikkien solmujen levitystehon ymmärtäminen: jatkuvan ajan perspektiivi // Sci Rep. - 2015. - T. 5 . - doi : 10.1038/srep08665 . - . - arXiv : 1405.6707 . — PMID 25727453 .
Linton C. Freeman. Keskeisyys sosiaalisissa verkostoissa: käsitteellinen selvennys // Sosiaaliset verkostot. - 1979. - Vol. 1 , numero. 3 . — S. 215–239 . - doi : 10.1016/0378-8733(78)90021-7 . Arkistoitu alkuperäisestä 22. helmikuuta 2016.
Linton Freeman. Joukko keskeisyyden mittareita, jotka perustuvat väliin // Sosiometria. - 1977. - T. 40 , no. 1 . — s. 35–41 . - doi : 10.2307/3033543 . — .
Alex Bavelas. Viestintämallit tehtäväkeskeisissä ryhmissä // J. Acoust. soc. Olen. - 1950. - T. 22 , no. 6 .
Sabidussi G. Sabidussi. Graafin keskeisyysindeksi // Psychometriics. - 1966. - T. 31 , no. 4 . - doi : 10.1007/bf02289527 . — PMID 5232444 .
Massimo Marchiori, Vito Latora. Harmonia pienessä maailmassa // Physica A: Tilastollinen mekaniikka ja sen sovellukset. - 2000. - T. 285 , no. 3-4 . - doi : 10.1016/s0378-4371(00)00311-3 . - . - arXiv : cond-mat/0008357 .
Anthony Decker. Käsitteellinen etäisyys sosiaalisen verkoston analyysissä // Journal of Social Structure. - 2005. - T. 6 , no. 3 .
Yannick Rochat. Läheisyyskeskeisyys laajennettu liittämättömiin kaavioihin: Harmoninen keskeisyysindeksi // Applications of Social Network Analysis, ASNA 2009 . – 2009.
Ulrik Brandes. Nopeampi algoritmi keskinäisyyden keskittämiseen // Journal of Mathematical Sociology. - 2001. - T. 25 , no. 2 . - doi : 10.1080/0022250x.2001.9990249 .
Newman MEJ Verkkojen matematiikka .
Katz L. Sosiometrisesta indeksistä johdettu uusi tilaindeksi // Psychometrics. - 1953. - S. 39-43 .
Piraveenan M., Prokopenko M., Hossain L. Perkolaatiokeskeisyys: Solmujen graafisen teoreettisen vaikutuksen kvantifiointi verkkojen perkolaation aikana // PLOS ONE. - 2013. - T. 8 , no. 1 . - doi : 10.1371/journal.pone.0053095 . - . — PMID 23349699 .
Mohamamd Reza Faghani. Tutkimus XSS-madojen leviämisestä ja havaitsemismekanismeista online-sosiaalisissa verkostoissa // IEEE Transactions on Information Forensics and Security. - 2013. - T. 8 , no. 11 . - doi : 10.1109/TIFS.2013.2280884 .
Alvarez-Socorro AJ, Herrera-Almarza GC, González-Díaz LA Erilaisuusmittauksiin perustuva omakeskeisyys paljastaa keskussolmuja monimutkaisissa verkoissa // Scientific Reports. - 2015. - marraskuu ( osa 5 ). - doi : 10.1038/srep17095 . - . — PMID 26603652 .
Braha D., Bar-Yam Y. Keskeisyydestä väliaikaiseen maineeseen: Dynaaminen keskeisyys monimutkaisissa verkoissa // Monimutkaisuus. - 2006. - T. 12 , no. 2 . - doi : 10.1002/cplx.20156 . - . - arXiv : fysiikka/0611295 .
Hill SA, Braha D. Dynamic Model of Time-Dependent Complex Networks // Physical Review E. - 2010. - Vol. 82 , no. 4 . - doi : 10.1103/physreve.82.046105 . - . - arXiv : 0901.4407 . — PMID 21230343 .
Mukautuvat verkot: teoria, mallit ja sovellukset / Gross T., Sayama H.. - Springer, 2009.
Holme P., Saramaki J. Temporal Networks. - Springer, 2013.
Tore Opsahl, Filip Agneessens, John Skvoretz. Solmukeskeisyys painotetuissa verkoissa: Yleistysaste ja lyhimmät polut // Sosiaaliset verkostot. - 2010. - T. 32 , no. 3 . - doi : 10.1016/j.socnet.2010.03.006 . Arkistoitu alkuperäisestä 26. helmikuuta 2018.
Everett MG, Borgatti SP Keskeisyyden laajentaminen. Teoksessa PJ Carrington, J. Scott ja S. Wasserman (toim.) // Sosiaalisen verkoston analyysin mallit ja menetelmät. - New York: Cambridge University Press, 2005. - S. 57-76.
Puzis R., Yagil D., Elovici Y., Braha D. Yhteistyöhyökkäys Internetin käyttäjien nimettömyyttä vastaan // Internet Research. - 2009. - T. 19 , no. 1 . Arkistoitu alkuperäisestä 7. joulukuuta 2013.

Lue lisää lukemista varten

Koschützki, D.; Lehmann, K.A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. ja Zlotowski, O. (2005) Keskiarvoindeksit. Teoksessa Brandes, U. ja Erlebach, T. (toim.) Network Analysis: Methodological Foundations , pp. 16-61, LNCS 3418, Springer-Verlag.