Betweenness centrality

Percolation centrality on painotetun betweenness centralityn versio, mutta siinä otetaan huomioon kunkin lyhimmän polun lähde- ja kohdesolmujen ”tila” painoa laskettaessa. ’Tartunnan’ perkolaatiota esiintyy monimutkaisissa verkoissa useissa skenaarioissa. Esimerkiksi virus- tai bakteeri-infektio voi levitä ihmisten sosiaalisissa verkostoissa, joita kutsutaan kontaktiverkostoiksi. Tautien leviämistä voidaan tarkastella myös korkeammalla abstraktiotasolla tarkastelemalla kaupunkien tai asutuskeskusten verkostoa, joka on yhteydessä toisiinsa tie-, rautatie- tai lentoyhteyksillä. Tietokonevirukset voivat levitä tietokoneverkkojen kautta. Myös huhut tai uutiset liiketoimintatarjouksista ja sopimuksista voivat levitä ihmisten sosiaalisten verkostojen kautta. Kaikissa näissä skenaarioissa ”tartunta” leviää monimutkaisen verkon linkkien välityksellä ja muuttaa solmujen ”tiloja” leviämisen myötä joko palautuvasti tai muuten. Esimerkiksi epidemiologisessa skenaariossa yksilöt siirtyvät tartunnalle alttiista tilasta tartunnan leviämisen myötä tartunnan saaneeseen tilaan. Tilat, joita yksittäiset solmut voivat edellä mainituissa esimerkeissä ottaa, voivat olla binäärisiä (kuten uutisen vastaanotettu/ei vastaanotettu), diskreettejä (altis/tartunnan saanut/toipunut) tai jopa jatkuvia (kuten tartunnan saaneiden ihmisten osuus kaupungissa), kun tartunta leviää. Kaikille näille skenaarioille on yhteistä se, että tartunnan leviäminen johtaa solmujen tilojen muuttumiseen verkoissa. Tätä silmällä pitäen ehdotettiin perkolaatiokeskeisyyttä (PC, Percolation Centrality), joka mittaa erityisesti solmujen merkitystä verkoston läpi tapahtuvan perkolaation edistämisessä. Tätä mittaria ehdottivat Piraveenan et al.

Perkolation centrality määritellään tietylle solmulle tiettynä ajankohtana kyseisen solmun kautta kulkevien ”perkoloivien polkujen” osuutena. ’Perkoloitunut polku’ on lyhin polku solmuparin välillä, jossa lähdesolmu on perkolioitunut (esim. tartunnan saanut). Kohdesolmu voi olla perkooloitunut tai ei-perkooloitunut tai osittain perkooloitunut.

P C t ( v ) = 1 N – 2 ∑ s ≠ v ≠ r σ s r ( v ) σ s r x t s ∑ – x t v {\displaystyle PC^{t}(v)={\frac {1}{N-2}}\summa _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}}{\frac {{x^{t}}}_{s}}{{\summa {}-{x^{t}}}_{v}}}}

joissa σ s r {\displaystyle \sigma _{sr}}}

on lyhimpien polkujen kokonaismäärä solmusta s {\displaystyle s}

solmuun r {\displaystyle r}

ja σ s r ( v ) {\displaystyle \sigma _{sr}(v)}

on niiden polkujen lukumäärä, jotka kulkevat v {\displaystyle v}

kautta. Solmun i perkolaatiotila {\displaystyle i}

hetkellä t {\displaystyle t}

merkitään x t i {\displaystyle {x^{t}}_{i}}}

ja kaksi erikoistapausta ovat, kun x t i = 0 {\displaystyle {x^{t}}_{i}=0}

, mikä tarkoittaa ei-perkooloitua tilaa hetkellä t {\displaystyle t}

kun taas kun x t i = 1 {\displaystyle {x^{t}}_{i}=1}

mikä tarkoittaa täysin perkoloivaa tilaa hetkellä t {\displaystyle t}

. Väliin jäävät arvot ilmaisevat osittain perkooloituneita tiloja ( esim. paikkakuntien verkostossa tämä olisi tartunnan saaneiden ihmisten prosenttiosuus kyseisessä kaupungissa).

Perkoloitumispoluille liitetyt painotukset riippuvat lähdesolmuille määritetyistä perkolaatiotasoista, mikä perustuu siihen lähtökohtaan, että mitä korkeampi lähdesolmun perkolaatiotaso on, sitä tärkeämpiä ovat kyseisestä solmusta lähtevät polut. Näin ollen solmut, jotka sijaitsevat lyhimmillä poluilla, jotka lähtevät korkeasti perkoloiduista solmuista, ovat mahdollisesti tärkeämpiä perkolaation kannalta. PC:n määritelmää voidaan myös laajentaa siten, että se sisältää myös kohdesolmujen painot. Perkolaatiokeskeisyyslaskelmat kestävät O ( N M ) {\displaystyle O(NM)}.

ajassa Brandesin nopeasta algoritmista omaksutulla tehokkaalla toteutuksella, ja jos laskennassa on otettava huomioon kohdesolmujen painot, pahimmassa tapauksessa aika on O ( N 3 ) {\displaystyle O(N^{3})}.