Središnjost

Primeri A) Stepen središnjosti, B) Središnjost po bliskosti, C) Relaciona središnjost, D) Središnjost po svojstvenom vektoru, E) Katz centrality and F) Alpha centrality istog grafa.

U okviru teorije grafova i analize mreža, postoje različiti načini merenja središnjosti čvora unutar grafa, koji određuje relativnu važnost čvora u odnosu na graf (npr. koliko je osoba uticajna u okviru neke društvene grupe ili koliko je soba važna u kući itd.). Mnogi koncepti središnjnosti bili su prvo razvijeni u analizi socijalnih grupa, i mnogi od termina za merenje središnjosti reflektuju svoje sociološko poreklo.

Postoje 4 merenja središnjosti koja su široko korišćena u analizi mreža: središnjost po stepenu, relaciona središnjost, središnjost po bliskosti i središnjost po svojstvenom vektoru. Za ocenu i proširenje opštosti ka opterećenim mrežama, pogledajte Opsahl et al. (2010).

Stepen središnjosti

Istorijski prvi i konceptualno najjednostavniji stepen središnjosti, definisan je kao broj veza čvora (sa drugim čvorovima). Stepen npr. može biti interpretiran kao procena rizika da dati čvor bude pod uticajem bilo čega što prolazi kroz mrežu (virus, informacija itd.). U slučaju usmerenog grafa, obično definišemo dve odvojene mere stepena središnjosti: ulazni i izlazni stepen. Ulazni stepen je broj grana koje ulaze u čvor, a izlazni broj grana koje izlaze iz čvora. Kada se grane interpretiraju kao neki pozitivni aspekti kao što su recimo prijateljstvo i saradnja, ulazni stepen je interpretiran kao popularnost, a izlazni kao društvenost. Stepen središnjosti čvora $v$, za dati graf $G:=(V,E)$ sa $|V|$ čvorova i $|E|$ grana, je definisan kao: $C_{D}(v)={\text{deg}}(v)$ Izračunavanje stepena središnjosti za sve čvorove u grafu koristi $\Theta (V^{2})$ u prezentaciji grafa pomoću matrice susedstva, a za grane uzima $\Theta (E)$ u istoj matričnoj prezentaciji.

Ponekad treba naći središnjost grafa unutar grafa. Definicija središnjosti čvora može se proširiti na ceo graf. Neka $v*$ bude čvor sa najvišim stepenom središnjosti u grafu $G$. Neka $X:=(Y,Z)$ bude graf sa granama čvora $Y$ koji maksimizuje sledeću sumu (dok je $y*$ čvor sa najvišim stepenom središnjosti u grafu $X$):

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

Sledi, stepen središnjosti grafa $G$ je:

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

Vrednost $H$ je najveća kada graf $X$ sadrži jedan centralni čvor koji je povezan sa svim ostalim čvorovima, i u tom slučaju $H=(n-1)(n-2)$.

Središnjost po bliskosti

U povezanim grafovima postoji prirodna mera za distancu između svih parova čvorova, definisana dužinom najkraćeg puta. Udaljenost čvora v je definisana sumom rastojanja tog čvora od svih ostalih, dok je bliskost definisana kao inverz udaljenosti. Dakle, što je veća središnjost čvora manja je njegova ukupna distanca od ostalih čvorova. Bliskost se može uzeti kao mera koliko će trebati vremena da informacija od čvora v dođe do svih ostalih čvorova.

U klasičnoj definiciji središnjosti po bliskosti, širenje informacija se modelira korišćenjem najkraćih puteva. Ovaj model ne mora biti najrealističniji za sve tipove komunikacionih scenarija. Dakle, povezane definicije bile su razmatrane kao mera bliskosti, kao merenje središnjnosti pomoću slučajnog puta koji su predstavili Noh i Riger (2004). Ovaj model meri brzinu kojom poruke koje se kreću slučajnim putanjama dolaze do čvora iz nekog drugog dela grafa.

Informaciona središnjost koju su predstavili Stifenson i Zelen 1989. je drugi način merenja bliskosti, koji ima neke sličnosti sa modelom Noha i Rigera. U suštini, on meri harmonijsku sredinu od dužine puteva koji se završavaju čvorom i, koja je manja ako i ima mnogo malih puteva ka drugim čvorovima.

Zapazite da je po definiciji grafovskih rastojanja, središnjost po bliskosti svih čvorova u nepovezanom grafu bila 0. U radu Dangelčeva 2006. vezanog za ranjivost mreža, definicija bliskosti modifikovana je tako da može biti lakše izračunata i može biti primenjena na nepovezane grafove:

$C_{C}(v)=\sum _{t\in V\setminus v}2^{-d_{G}(v,t)}.$

Još jednu primenu na nepovezane grafove predložio je Opsal 2010.

Relaciona središnjost

Hue (from red=0 to blue=max) shows the node betweenness.

Relaciona središnjost je način merenja središnjosti čvora unutar grafa. Relaciona središnjost kvantifikuje koliko se puta čvor ponaša kao most najkraćeg puta između neka dva čvora. Ovaj način merenja koncipirao je Linton Friman radi merenja koliko kontrole neka osoba ima nad komunikacijom između drugih ljudi u društvenoj grupi. Po njegovom konceptu, čvorovi za koje je verovatnije da će se naći na nekom slučajno izabranom najkraćem putu između dva slučajno izabrana čvora imaju visoku relacionu središnjost.

Relaciona središnjost čvora $v$ u grafu $G:=(V,E)$ sa $V$ čvorova računa se na sledeći način:

1. Za svaki par čvorova (s,t), izračuna |najkraći put između njih.
2. Za svaki par čvorova (s,t), odredi najkraći put koji sadrži čvor koji se razmatra (ovde, čvor v).
3. Sumira taj put za sve parove čvorova (s,t).

Kompaktnije se relaciona središnjost može predstaviti kao:

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

gde je $\sigma _{st}$ ukupan broj najkraćih puteva od čvora $s$ do čvora $t$ i $\sigma _{st}(v)$ je broj tih puteva koji prolaze kroz čvor $v$. Relaciona središnjost može biti normalizovana deljenjem dobijenog broja sa brojem parova čvorova koji ne sadrže v, koji za usmerene grafove iznosi $(n-1)(n-2)$, a za neusmerene $(n-1)(n-2)/2$. Na primer, u neusmerenom zvezda-grafu, centralni čvor (koji se nalazi u svakom mogućem najkraćem putu) bi imao relacionu središnjost $(n-1)(n-2)/2$ (1, ako se normalizuje) dok bi listovi (kojih nema ni u jednom najkraćem putu) imali relacionu središnjost 0.

Sa aspekta izračunavanja, i relaciona središnjost po bliskosti svih čvorova u grafu zahtevaju računanje najkraćih puteva između svakog para čvorova grafa, što zahteva $\Theta (V^{3})$ vreme koristeći Flojd-Voršalov algoritam. Ipak, kod grafove čije su matrice većinom popunjene nulama, Džonsonov algoritam može biti efikasniji, zahtevajući $O(V^{2}\log V+VE)$ za izvršavanje. U slučaju netežinskih grafova izračunavanje se može izvršiti pomoću Brandovog algoritma koji zahteva $O(VE)$ vremena. U normalnim situacijama, ovi algoritmi pretpostavljaju da su grafovi neusmereni i povezani sa mogućnošću pojave ciklova i višestrukih grana. Kada je predmet obrade graf koji predstavlja socijalnu mrežu, često su grafovi bez ciklova i višestrukih grana da bi se očuvala jednakost (pošto grane predstavljaju povezanost između ljudi). U ovom slučaju, Brandov algoritam će konačan rezultat sa dva da bi uračunao svaki najkraći put koji je dvaput brojan.

Središnjost po svojstvenom vektoru

Središnjost po svojstvenom vektoru je merenje uticaja čvora u mreži. Pripisuje relativne vrednosti svakom čvoru u mreži na osnovu koncepta po kojem konekcije ka čvorovima sa visokom vrednošću više doprinose vrednosti čvora nego isto konekcije sa čvorovima koji imaju manju relativnu vrednost. Guglovo rangiranje stranica je varijanta merenja središnjosti po svojstvenom vektoru. Još jedan vrlo sličan način merenja središnjosti je Kacova središnjost.

Korišćenje matrice susedstva za određivanje središnjosti po svojstvenom vektoru

Za dati graf $G:=(V,E)$ sa $|V|$ brojem čvorova neka je $A=(a_{v,t})$ matrica susedstva. Skor središnjosti za neki čvor $v$ može biti definisan na sledeći način:

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

gde je $M(v)$ niz suseda čvora $v$ a $\lambda$ je konstanta. Uz malo preuređivanja ovo se može napisati u vektorskoj notaciji kao jednakost:

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

U opštem slučaju, postojaće mnogo različitih vrednosti za $\lambda$ za svako rešenje problema središnjosti preko svojstvenog vektora koje postoji. Kakogod, dodatni zahtev da sve vrednosti u svojstvenom vektoru budu pozitivne implicira (po Peron- Frobenius teoremi) da samo najveća vrednost u svojstvenom vektoru rezultuje traženim rezultatom središnjosti. $v^{th}$ član svojstvenog vektora daje rezultat središnjosti za čvor $v$ u mreži.

Kacova središnjost i rangiranje stranica

Kacova središnjost je generalizacija stepene središnjosti. Stepena središnjost meri broj direktnih suseda, a Kacova središnjost meri broj svih čvorova koji mogu biti povezani nekim putem, dok je doprinos udaljenog čvora okarakterisan faktorom slabljenja $\alpha \in (0,1)$. Matematički, on je definisan sa $x_{i}=\sum _{k=1}^{\infty }\sum _{j=1}^{N}\alpha ^{k}(A^{k})_{ij}$.

Kacova središnjost se takođe može interpretirati kao varijanta središnjosti po svojstvenom vektoru. Još jedna forma Kacove središnjosti je $x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).$ U poređenju sa izrazom za središnjost po svojstvenom vektoru, $x_{j}$ je zamenjeno sa $x_{j}+1$.

Dokazano je da je najveća vrednost u vektoru središnjosti granica sa Kacovu središnjost jer $\alpha$ ne može preći ranije pomenutu vrednost $1/\lambda$.

Rangiranje stranica zadovoljava sledeću jednakost: $x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},$ gde je $L(j)=\sum _{j}a_{ij}$ broj suseda čvora $j$. U poređenju sa središnjosti po svojstvenom vektoru i Kacovoj središnjosti, glavna razlika je faktor skaliranja $L(j)$. Još jedna razlika je između rangiranja stranica i središnjosti po svojstvenom vektoru je ta da vektor rangiranja stranica ima obrnute indekse u odnosu na svojstveni vektor središnjosti.

Definicija i karakterizacija indeksa središnjosti

Pored već pomenutih klasičnih indeksa središnjosti, postoji još na desetine specifikovanijih indeksa središnjosti. Uprkos pojmu koji intuitivno navodi na suprotan zaključak još uvek ne postoji definicija ili karakterizacija indeksa središnjosti koja može na sve njih da se primeni. Vrlo opšta definicija bi glasila ovako:

Indeks središnjosti je funkcija nad čvorovima grafa. To je strukturni indeks, odn. su grafovi $G$ and $H$ izomorfni i $\Phi$ preslikavanje čvorova grafa $G$- $V(G)$ u V(H), onda središnjost čvora $v$ u $G$ mora biti ista kao središnjost čvora $\Phi (v)$ u $H$. Po konvenciji, što je veći indeks središnjosti čvora, veća je njegova zastupljenost u grafu.

Ova definicija obuhvata sva klasična merenja središnjosti, ali neće sva meranja koja zadovoljavaju ovu definiciju biti prihvaćena kao indeksi središnjosti. Borgati i Everet sumiraju da indeks središnjosti meri poziciju čvora u okviru predefinisanog niza šetnji. Oni karakterizuju indekse središnjosti po četiri faktora: set šetnji, da li je dužina ili broj ovih šetnji razmatran, pozicija čvora u šetnjama, i kako kako su brojevi pripisani putevima sumirani pri merenju. Ovo vodi ka karakterizaciji po načinu na koji je indeks središnjosti izračunat. U drugačijoj karakterizaciji, Borgati razlikuje indekse po putanjama koje oni razmatraju i koji tip protoka mreže impliciraju. Potonji karakterizuje indekse središnjosti po kvalitetu njihove predikcije koji je čvor najsredišnjiji za datu mrežu i njen protok. Ova karakterizacija pruža mogućnost odabira koji indeks središnjosti koristiti.

Centralizacija

Centralizacija bilo koje mreže je mera koliko je njen centralni čvor centralan u odnosu na centralnost ostalih čvorova. Opštu definiciju centralizacije za netežinske grafove predložio je Linton Friman (1979). Mere centralizacije (a) računaju sumu razlika centralnosti između najcentralnijeg čvora i ostalih čvorova; (b) dele ovaj iznos sa teoretski najvećom sumom razlika u bilo kojoj mreži istog stepena. Tako, svaka mera centralnosti može imati svoju sopstvenu meru centralnosti. Definisano formalno, ako je $C_{x}(p_{i})$ neka centralnost tačke $i$, ako je $C_{x}(p_{*})$ najveća mera u mreži, i ako je $max\sum _{j=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})$ najveća suma razlika u tački centralnosti $C_{x}$ za bilo koji graf sa istim brojem čvorova, onda je centralizacije mreže:

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

Dodatna literatura

• Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215–239.
• Sabidussi, G. (1966). The centrality index of a graph. Psychometrika, 31 (4), 581–603.
• Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry 40, 35–41.
• Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.) Network Analysis: Methodological Foundations, pp. 16–61, LNCS 3418, Springer-Verlag.
• Bonacich, P. (1987). Power and Centrality: A Family of Measures, The American Journal of Sociology, 92 (5), pp. 1170–1182.