Sovitteluaste

Välitysaste on kaavion keskeisyyden mitta lyhimpiin reitteihin perustuen . Jokaiselle yhdistetyn graafin kärkiparille on vähintään yksi (lyhyin) polku pisteiden välillä, jolle joko reunojen määrä, jota pitkin polku kulkee (painottamattomille graafille) tai näiden reunojen painojen summa (painotetuille graafille) kaaviot) on minimaalinen. Jokaisen kärjen välitysaste on yhtä suuri kuin näiden kärjen läpi kulkevien lyhimpien polkujen lukumäärä.

Välitysaste on laajalti käytössä verkostoteoriassa - se heijastaa sitä, missä määrin kärkipisteet ovat muiden pisteiden välillä. Esimerkiksi tietoliikenneverkossa solmu, jolla on korkein välitysaste, hallitsee verkkoa enemmän, kun enemmän tietoa kulkee kyseisen solmun kautta. Mediation aste on kehitetty yleiseksi keskeisyyden mittariksi - sitä voidaan soveltaa monenlaisiin verkostoteorian ongelmiin, mukaan lukien sosiaalisiin verkostoihin , biologiseen, kuljetukseen ja tieteelliseen yhteistyöhön liittyvät ongelmat [1] .

Vaikka aikaisemmat kirjoittajat kuvasivatkin intuitiivisesti keskeyttä välitysasteen avulla, Freeman [2] esitti ensimmäisen muodollisen määritelmän välitysasteelle.

Määritelmä

Solmuvälityksen aste saadaan seuraavasti: $v$

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

jossa on yhtä suuri kuin lyhimpien polkujen kokonaismäärä solmusta solmuun ja on yhtä suuri kuin näiden läpi kulkevien polkujen lukumäärä . ${\displaystyle \sigma _{st))$ $s$ $t$ $\sigma _{st}(v)$ $v$

Huomaa, että välitysaste on yhtä suuri kuin niiden solmuparien osuus, joiden ehto on summausehdon määrittelemä. Siksi on solmupareja, joiden lyhyimmät polut eivät sisällä , joten . Jako on suunnatuille graafiille ja suuntaamattomille graafille, missä on yhtä suuri kuin suurimman komponentin solmujen lukumäärä. Huomaa, että tämä arvo on suurin, kun yksi kärkipiste sisältyy mihin tahansa yksittäiseen lyhimpään polkuun. Usein näin ei tehdä ja normalisointi voidaan tehdä ilman tarkkuuden menetystä. $v$ $g\in [0,1]$ ${\näyttötyyli (N-1) (N-2)}$ $(N-1) (N-2)/2$ $N$

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

joka johtaa

\max(normal)=1

\min(normaali)=0

Painotetut verkot

Painotetussa verkossa solmuja yhdistäviä linkkejä ei enää käsitellä erillisinä vuorovaikutuksina, vaan ne painotetaan suhteessa niiden kapasiteettiin, vaikutukseen, taajuuteen jne., mikä lisää verkon heterogeenisyyteen topologisten vaikutusten lisäksi toisen ulottuvuuden. Solmun välitysaste painotetussa verkossa saadaan sen vierekkäisten reunojen painojen summalla.

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

Milloin ja ovat viereisyys- ja painomatriisit solmujen välillä ja vastaavasti. Samoin kuin asteikko-invarianteissa verkoissa esiintyvä astejakauman potenssilaki, myös tietyn solmun aste noudattaa teholakia. $a_{{ij}}$ $w_{ij}$ $i$ $j$

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

Piikkien vahvuuden keskiarvon tutkiminen välitysasteen kanssa osoittaa, että toiminnallinen käyttäytyminen voidaan approksimoida lausekkeella [3] $s(b)$ $b$

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

Perkolaatiokeskeisyys

Perkolaatiokeskeisyys on painotetun välitysasteen versio, mutta se ottaa huomioon kunkin lyhimmän polun lähde- ja kohdesolmun "tilan" painotusta laskettaessa. Vuotoa tapahtuu monimutkaisissa verkoissa useissa erilaisissa skenaarioissa. Esimerkiksi virus- tai bakteeri-infektio voi levitä ihmisten sosiaalisten verkostojen kautta, joita kutsutaan kontaktiverkostoiksi. Taudin leviämistä voidaan tarkastella myös korkealla abstraktiolla ottamalla huomioon kaupunkien tai asutuskeskusten verkosto, joka on yhdistetty teiden, rautateiden tai lentoyhtiöiden kautta. Tietokonevirukset voivat levitä tietokoneverkoissa. Huhut ja uutiset yritystarjouksista ja -sopimuksista voivat levitä myös ihmisten sosiaalisten verkostojen kautta. Kaikissa näissä skenaarioissa "tartunta" leviää monimutkaisen verkon linkkien kautta ja muuttaa 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 Payravinan ym . [4] .

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

jossa on yhtä suuri kuin lyhimpien reittien kokonaismäärä solmusta solmuun ja on yhtä suuri kuin tällaisten läpi kulkevien polkujen lukumäärä . Solmun vuototila ajanhetkellä merkitään ja on olemassa kaksi erikoistapausta, jolloin , joka ilmaisee tiukkuustilan ajanhetkellä , ja when , joka tarkoittaa täydellistä vuotoa hetkellä . Näiden arvojen väliset arvot osoittavat 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 laskelmat edellyttävät loppusolmujen painojen huomioon ottamista, pahimman tapauksen aika on . $O(NM)$ $O(N^{3})$

Algoritmit

Graafin kaikkien kärkien välitysasteiden ja läheisyysasteiden laskeminen edellyttää lyhimpien polkujen laskemista kaikkien graafin kärkiparien välillä, mikä vie aikaa, kun käytetään Floyd -Warshall-algoritmia , joka on muokattu löytämään kaikki polut yhden polun sijaan kahdelle. valitut solmut. Harvassa graafissa Johnsonin algoritmi tai Brandeisin algoritmi voi olla tehokkaampi, molemmat algoritmit ajavat ajassa . Painottamattomissa kaavioissa mediaatioasteen laskeminen Brandes-algoritmilla vie aikaa [5] . $\Theta (|V|^{3})$ $O(|V|^{2}\log |V|+|V||E|)$ $O(|V||E|)$

Kun lasketaan graafin kaikkien kärkien välitys- ja läheisyysasteita , oletetaan, että graafit ovat suuntaamattomia, yhdistettyjä ja useat reunat ovat sallittuja. Verkkograafien kanssa työskennellessä kaavioissa ei usein ole syklejä tai useita reunoja, jotka heijastavat yksinkertaisia yhteyksiä (tässä reunat edustavat ihmisten välistä yhteyttä). Tässä tapauksessa Brandes-algoritmia käytettäessä lopullinen keskeisyysarvo jaetaan kahdella, jotta jokainen lyhin polku lasketaan kahdesti [6] .

Toinen algoritmi yleistää Freemanin välityksen asteen geodetiikkaan ja Newmanin välityksen asteen kaikille poluille ottamalla käyttöön parametrin, joka ohjaa tutkimuksen ja käytön välistä vaihtoa. Aikamonimutkaisuus on yhtä suuri kuin reunojen lukumäärä graafin solmujen lukumäärää kohden [7] .

Keskeisyyden käsite on myös laajennettu ryhmätasolle [8] . Ryhmävälitysaste ilmaisee niiden geodeettisten osien osuuden, jotka yhdistävät ryhmän ulkopuolisia jäsenpareja, jotka kulkevat solmuryhmän läpi. Brandesin algoritmi kaikkien kärkien mediaatioasteen laskemiseksi on muunnettu laskemaan yhden solmuryhmän ryhmävälitysasteen samalla asymptoottisella käyntiajalla [8] .

Aiheeseen liittyvät käsitteet

Välityksen aste liittyy verkon liitettävyyteen siinä mielessä, että korkean välitysasteen omaavat kärjet voivat mahdollisesti rikkoa graafin, jos ne poistetaan (katso leikkausjoukko ).

Reitin välitysaste yleistää välitysasteen, kun sitä sovelletaan mihin tahansa kaavioon yksinkertaisten polkujen määrittämiseksi ilman jaksoja perustuen vain lyhimmän polun kriteeriin [9] .

Katso myös

Keskeisyys

Muistiinpanot

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

Kirjallisuus

Ulrik Brandes. Nopeampi algoritmi keskinäisyyden keskittämiseen // Journal of Mathematical Sociology. - 2001. - T. 25 , no. 2 . — S. 163–177 . - doi : 10.1080/0022250x.2001.9990249 . Arkistoitu alkuperäisestä 13. lokakuuta 2017.
Linton Freeman. Joukko keskeisyyden mittareita, jotka perustuvat väliin // Sosiometria. - 1977. - T. 40 , no. 1 . — s. 35–41 . - doi : 10.2307/3033543 . — .
Goh KI, Kahng B., Kim D. Kuormanjaon yleinen käyttäytyminen mittakaavattomissa verkoissa // 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 kovarianssiydin: Uusi kovarianssimitta suunnatun graafin solmujen välillä // 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. Pistekeskeisyyden määrittäminen keksimättömissä sosiaalisissa verkostoissa // Sosiometria. - 1974. - T. 37 , no. 1 . — S. 122–130 . - doi : 10.2307/2786472 . — .
Newman MEJ Networks: Johdanto. - Oxford, Iso-Britannia: Oxford University Press, 2010. - ISBN 978-0199206650 .
Shlomi Dolev, Yuval Elovici, Rami Puzis. Routing betweenness centrality // J. ACM. - 2010. - T. 57 , no. 4 . – S. 25:1–25:27 . - doi : 10.1145/1734213.1734219 .
Mahendra Piraveenan. Perkolaatiokeskeisyys: Solmujen graafiteoreettisen vaikutuksen kvantifiointi verkkojen perkolaation aikana // 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. Monimutkaisten painotettujen verkkojen arkkitehtuuri // PNAS. - 2004. - T. 101 , nro 11 .
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.
Shlomi Dolev, Yuval Elovici, Rami Puzis. Routing betweenness centrality // J. ACM. - T. 57 , no. 4 . - doi : 10.1145/1734213.1734219 .