Средишњост

У оквиру теорије графова и анализе мрежа, постоје различити начини мерења средишњости чвора унутар графа, који одређује релативну важност чвора у односу на граф (нпр. колико је особа утицајна у оквиру неке друштвене групе или колико је соба важна у кући итд.). Многи концепти средишњности били су прво развијени у анализи социјалних група, и многи од термина за мерење средишњости рефлектују своје социолошко порекло.^[1]

Постоје 4 мерења средишњости која су широко коришћена у анализи мрежа: средишњост по степену, релациона средишњост, средишњост по блискости и средишњост по својственом вектору. За оцену и проширење општости ка оптерећеним мрежама, погледајте Opsahl et al. (2010).^[2]

Степен средишњости

Историјски први и концептуално најједноставнији степен средишњости, дефинисан је као број веза чвора (са другим чворовима). Степен нпр. може бити интерпретиран као процена ризика да дати чвор буде под утицајем било чега што пролази кроз мрежу (вирус, информација итд.). У случају усмереног графа, обично дефинишемо две одвојене мере степена средишњости: улазни и излазни степен. Улазни степен је број грана које улазе у чвор, а излазни број грана које излазе из чвора. Када се гране интерпретирају као неки позитивни аспекти као што су рецимо пријатељство и сарадња, улазни степен је интерпретиран као популарност, а излазни као друштвеност. Степен средишњости чвора $v$ , за дати граф $G:=(V,E)$ са $|V|$ чворова и $|E|$ грана, је дефинисан као: $C_{D}(v)={\text{deg}}(v)$ Израчунавање степена средишњости за све чворове у графу користи $\Theta (V^{2})$ у презентацији графа помоћу матрице суседства, а за гране узима $\Theta (E)$ у истој матричној презентацији.

Понекад треба наћи средишњост графа унутар графа. Дефиниција средишњости чвора може се проширити на цео граф. Нека $v*$ буде чвор са највишим степеном средишњости у графу $G$ . Нека $X:=(Y,Z)$ буде граф са гранама чвора $Y$ који максимизује следећу суму (док је $y*$ чвор са највишим степеном средишњости у графу $X$ ):

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

Следи, степен средишњости графа $G$ је:

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

Вредност $H$ је највећа када граф $X$ садржи један централни чвор који је повезан са свим осталим чворовима, и у том случају $H=(n-1)(n-2)$ .

Средишњост по блискости

У повезаним графовима постоји природна мера за дистанцу између свих парова чворова, дефинисана дужином најкраћег пута. Удаљеност чвора в је дефинисана сумом растојања тог чвора од свих осталих, док је блискост дефинисана као инверз удаљености.^[3] Дакле, што је већа средишњост чвора мања је његова укупна дистанца од осталих чворова. Блискост се може узети као мера колико ће требати времена да информација од чвора в дође до свих осталих чворова.^[4]

У класичној дефиницији средишњости по блискости, ширење информација се моделира коришћењем најкраћих путева. Овај модел не мора бити најреалистичнији за све типове комуникационих сценарија. Дакле, повезане дефиниције биле су разматране као мера блискости, као мерење средишњности помоћу случајног пута који су представили Нох и Ригер (2004). Овај модел мери брзину којом поруке које се крећу случајним путањама долазе до чвора из неког другог дела графа.^[5]

Информациона средишњост коју су представили Стифенсон и Зелен 1989. је други начин мерења блискости, који има неке сличности са моделом Ноха и Ригера. У суштини, он мери хармонијску средину од дужине путева који се завршавају чвором i, која је мања ако i има много малих путева ка другим чворовима.^[6]

Запазите да је по дефиницији графовских растојања, средишњост по блискости свих чворова у неповезаном графу била 0. У раду Дангелчева 2006. везаног за рањивост мрежа, дефиниција блискости модификована је тако да може бити лакше израчуната и може бити примењена на неповезане графове:^[7]

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

Још једну примену на неповезане графове предложио је Опсал 2010.^[8]

Релациона средишњост

Релациона средишњост је начин мерења средишњости чвора унутар графа. Релациона средишњост квантификује колико се пута чвор понаша као мост најкраћег пута између нека два чвора. Овај начин мерења конципирао је Линтон Фриман ради мерења колико контроле нека особа има над комуникацијом између других људи у друштвеној групи.^[9] По његовом концепту, чворови за које је вероватније да ће се наћи на неком случајно изабраном најкраћем путу између два случајно изабрана чвора имају високу релациону средишњост.

Релациона средишњост чвора $v$ у графу $G:=(V,E)$ са $V$ чворова рачуна се на следећи начин:

За сваки пар чворова (s,t), израчуна |најкраћи пут између њих.
За сваки пар чворова (s,t), одреди најкраћи пут који садржи чвор који се разматра (овде, чвор v).
Сумира тај пут за све парове чворова (s,t).

Компактније се релациона средишњост може представити као:^[10]

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

где је $\sigma _{st}$ укупан број најкраћих путева од чвора $s$ до чвора $t$ и $\sigma _{st}(v)$ је број тих путева који пролазе кроз чвор $v$ . Релациона средишњост може бити нормализована дељењем добијеног броја са бројем парова чворова који не садрже v, који за усмерене графове износи $(n-1)(n-2)$ , а за неусмерене $(n-1)(n-2)/2$ . На пример, у неусмереном звезда-графу, централни чвор (који се налази у сваком могућем најкраћем путу) би имао релациону средишњост $(n-1)(n-2)/2$ (1, ако се нормализује) док би листови (којих нема ни у једном најкраћем путу) имали релациону средишњост 0.

Са аспекта израчунавања, и релациона средишњост по блискости свих чворова у графу захтевају рачунање најкраћих путева између сваког пара чворова графа, што захтева $\Theta (V^{3})$ време користећи Флојд-Воршалов алгоритам. Ипак, код графове чије су матрице већином попуњене нулама, Џонсонов алгоритам може бити ефикаснији, захтевајући $O(V^{2}\log V+VE)$ за извршавање. У случају нетежинских графова израчунавање се може извршити помоћу Брандовог алгоритма^[10] који захтева $O(VE)$ времена. У нормалним ситуацијама, ови алгоритми претпостављају да су графови неусмерени и повезани са могућношћу појаве циклова и вишеструких грана. Када је предмет обраде граф који представља социјалну мрежу, често су графови без циклова и вишеструких грана да би се очувала једнакост (пошто гране представљају повезаност између људи). У овом случају, Брандов алгоритам ће коначан резултат са два да би урачунао сваки најкраћи пут који је двапут бројан.^[10]

Средишњост по својственом вектору

Средишњост по својственом вектору је мерење утицаја чвора у мрежи. Приписује релативне вредности сваком чвору у мрежи на основу концепта по којем конекције ка чворовима са високом вредношћу више доприносе вредности чвора него исто конекције са чворовима који имају мању релативну вредност. Гуглово рангирање страница је варијанта мерења средишњости по својственом вектору.^[11] Још један врло сличан начин мерења средишњости је Кацова средишњост.

Коришћење матрице суседства за одређивање средишњости по својственом вектору

За дати граф $G:=(V,E)$ са $|V|$ бројем чворова нека је $A=(a_{v,t})$ матрица суседства. Скор средишњости за неки чвор $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}$

где је $M(v)$ низ суседа чвора $v$ a $\lambda$ је константа. Уз мало преуређивања ово се може написати у векторској нотацији као једнакост:

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

У општем случају, постојаће много различитих вредности за $\lambda$ за свако решење проблема средишњости преко својственог вектора које постоји. Какогод, додатни захтев да све вредности у својственом вектору буду позитивне имплицира (по Перон- Фробениус теореми) да само највећа вредност у својственом вектору резултује траженим резултатом средишњости.^[12] $v^{th}$ члан својственог вектора даје резултат средишњости за чвор $v$ у мрежи.

Кацова средишњост и рангирање страница

Кацова средишњост^[13] је генерализација степене средишњости. Степена средишњост мери број директних суседа, а Кацова средишњост мери број свих чворова који могу бити повезани неким путем, док је допринос удаљеног чвора окарактерисан фактором слабљења $\alpha \in (0,1)$ . Математички, он је дефинисан са $x_{i}=\sum _{k=1}^{\infty }\sum _{j=1}^{N}\alpha ^{k}(A^{k})_{ij}$ .

Кацова средишњост се такође може интерпретирати као варијанта средишњости по својственом вектору. Још једна форма Кацове средишњости је $x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).$ У поређењу са изразом за средишњост по својственом вектору, $x_{j}$ је замењено са $x_{j}+1$ .

Доказано је да је^[14] највећа вредност у вектору средишњости граница са Кацову средишњост јер $\alpha$ не може прећи раније поменуту вредност $1/\lambda$ .

Рангирање страница задовољава следећу једнакост: $x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},$ где је $L(j)=\sum _{j}a_{ij}$ број суседа чвора $j$ . У поређењу са средишњости по својственом вектору и Кацовој средишњости, главна разлика је фактор скалирања $L(j)$ . Још једна разлика је између рангирања страница и средишњости по својственом вектору је та да вектор рангирања страница има обрнуте индексе у односу на својствени вектор средишњости.^[15]

Дефиниција и карактеризација индекса средишњости

Поред већ поменутих класичних индекса средишњости, постоји још на десетине спецификованијих индекса средишњости. Упркос појму који интуитивно наводи на супротан закључак још увек не постоји дефиниција или карактеризација индекса средишњости која може на све њих да се примени.^[16] Врло општа дефиниција би гласила овако:

Индекс средишњости је функција над чворовима графа. То је структурни индекс, одн. су графови $G$ and $H$ изоморфни и $\Phi$ пресликавање чворова графа $G$ - $V(G)$ у V(H), онда средишњост чвора $v$ у $G$ мора бити иста као средишњост чвора $\Phi (v)$ у $H$ . По конвенцији, што је већи индекс средишњости чвора, већа је његова заступљеност у графу.^[17]

Ова дефиниција обухвата сва класична мерења средишњости, али неће сва мерања која задовољавају ову дефиницију бити прихваћена као индекси средишњости. Боргати и Еверет сумирају да индекс средишњости мери позицију чвора у оквиру предефинисаног низа шетњи. Они карактеризују индексе средишњости по четири фактора: сет шетњи, да ли је дужина или број ових шетњи разматран, позиција чвора у шетњама, и како како су бројеви приписани путевима сумирани при мерењу.^[16] Ово води ка карактеризацији по начину на који је индекс средишњости израчунат. У другачијој карактеризацији, Боргати разликује индексе по путањама које они разматрају и који тип протока мреже имплицирају.^[18] Потоњи карактеризује индексе средишњости по квалитету њихове предикције који је чвор најсредишњији за дату мрежу и њен проток. Ова карактеризација пружа могућност одабира који индекс средишњости користити.

Централизација

Централизација било које мреже је мера колико је њен централни чвор централан у односу на централност осталих чворова.^[19] Општу дефиницију централизације за нетежинске графове предложио је Линтон Фриман (1979). Мере централизације (а) рачунају суму разлика централности између најцентралнијег чвора и осталих чворова; (б) деле овај износ са теоретски највећом сумом разлика у било којој мрежи истог степена.^[19] Тако, свака мера централности може имати своју сопствену меру централности. Дефинисано формално, ако је $C_{x}(p_{i})$ нека централност тачке $i$ , ако је $C_{x}(p_{*})$ највећа мера у мрежи, и ако је $max\sum _{j=1}^{N}C_{x}(p_{*})-C_{x}(p_{i})$ највећа сума разлика у тачки централности $C_{x}$ за било који граф са истим бројем чворова, онда је централизације мреже:^[19]

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

Референце

^ Newman, M.E.J. 2010. Networks: An Introduction. Oxford, UK: Oxford University Press.
^ Opsahl, Tore; Agneessens, Filip; Skvoretz, John (2010). „Node centrality in weighted networks: Generalizing degree and shortest paths”. Social Networks. 32 (3): 245. doi:10.1016/j.socnet.2010.03.006. Архивирано из оригинала 26. 02. 2018. г. Приступљено 28. 05. 2013.
^ Sabidussi, G. (1966) The centrality index of a graph. Psychometrika 31, 581–603.
^ M.E.J. Newman (2005), A measure of betweenness centrality based on random walks, 27, стр. 39—54, arXiv:cond-mat/0309045 , doi:10.1016/j.socnet.2004.11.009 Текст „Social Networks” игнорисан (помоћ). Papercore summary http://papercore.org/Newman2005^{[мртва веза]}
^ J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).
^ Stephenson, K. A. and Zelen, M., 1989. Rethinking centrality: Methods and examples. Social Networks 11, 1–37.
^ Dangalchev Ch., Residual Closeness in Networks, Phisica A 365, 556 (2006).
^ Opsahl, Tore. „Closeness centrality in networks with disconnected components”.
^ Freeman, Linton (1977). „A set of measures of centrality based upon betweenness”. Sociometry. 40: 35—41.
^ ^а ^б ^в Brandes, Ulrik (2001). „A faster algorithm for betweenness centrality” (PDF). Journal of Mathematical Sociology. 25: 163—177. Приступљено 10. 11. 2011. Paperore summary http://papercore.org/Brandes2001^{[мртва веза]}
^ Feature Column from the AMS
^ M. E. J. Newman. „The mathematics of networks” (PDF). Приступљено 9. 11. 2006.
^ Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.
^ Bonacich, P., 1991. Simultaneous group and individual centralities. Social Networks 13, 155–168.
^ How does Google rank webpages? Архивирано на сајту Wayback Machine (31. јануар 2012) 20Q: About Networked Life
^ ^а ^б Borgatti, Stephen P.; Everett, Martin G. (2005). „A Graph-Theoretic Perspective on Centrality”. Social Networks. Elsevier. 28: 466—484. doi:10.1016/j.socnet.2005.11.005.
^ Koschützki, Dirk; Katharina A. Lehmann, Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl, Oliver Zlotowski (2005). „Centrality Indices”. Ур.: Ulrik Brandes, Thomas Erlebach. Network Analysis – Methodological Foundations. LNCS 3418. Springer Verlag, Heidelberg, Germany. стр. 16—60. ISBN 978-3-540-24979-5.
^ Borgatti, Stephen P. (2005). „Centrality and Network Flow”. Social Networks. Elsevier. 27: 55—71.
^ ^а ^б ^в Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215–239.

Додатна литература

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.

[NewmanNetworks-1] Newman, M.E.J. 2010. Networks: An Introduction. Oxford, UK: Oxford University Press.

[2] Opsahl, Tore; Agneessens, Filip; Skvoretz, John (2010). „Node centrality in weighted networks: Generalizing degree and shortest paths”. Social Networks. 32 (3): 245. doi:10.1016/j.socnet.2010.03.006. Архивирано из оригинала 26. 02. 2018. г. Приступљено 28. 05. 2013.

[3] Sabidussi, G. (1966) The centrality index of a graph. Psychometrika 31, 581–603.

[4] M.E.J. Newman (2005), A measure of betweenness centrality based on random walks, 27, стр. 39—54, arXiv:cond-mat/0309045 , doi:10.1016/j.socnet.2004.11.009 Текст „Social Networks” игнорисан (помоћ). Papercore summary http://papercore.org/Newman2005^{[мртва веза]}

[5] J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).

[6] Stephenson, K. A. and Zelen, M., 1989. Rethinking centrality: Methods and examples. Social Networks 11, 1–37.

[Dan-7] Dangalchev Ch., Residual Closeness in Networks, Phisica A 365, 556 (2006).

[opsahl2010-8] Opsahl, Tore. „Closeness centrality in networks with disconnected components”.

[freeman1977-9] Freeman, Linton (1977). „A set of measures of centrality based upon betweenness”. Sociometry. 40: 35—41.

[brandes-10] а ^б ^в Brandes, Ulrik (2001). „A faster algorithm for betweenness centrality” (PDF). Journal of Mathematical Sociology. 25: 163—177. Приступљено 10. 11. 2011. Paperore summary http://papercore.org/Brandes2001^{[мртва веза]}

[ams-11] Feature Column from the AMS

[12] M. E. J. Newman. „The mathematics of networks” (PDF). Приступљено 9. 11. 2006.

[13] Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.

[14] Bonacich, P., 1991. Simultaneous group and individual centralities. Social Networks 13, 155–168.

[15] How does Google rank webpages? Архивирано на сајту Wayback Machine (31. јануар 2012) 20Q: About Networked Life

[Borgatti2005-16] а ^б Borgatti, Stephen P.; Everett, Martin G. (2005). „A Graph-Theoretic Perspective on Centrality”. Social Networks. Elsevier. 28: 466—484. doi:10.1016/j.socnet.2005.11.005.

[Kosch2005-17] Koschützki, Dirk; Katharina A. Lehmann, Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl, Oliver Zlotowski (2005). „Centrality Indices”. Ур.: Ulrik Brandes, Thomas Erlebach. Network Analysis – Methodological Foundations. LNCS 3418. Springer Verlag, Heidelberg, Germany. стр. 16—60. ISBN 978-3-540-24979-5.

[18] Borgatti, Stephen P. (2005). „Centrality and Network Flow”. Social Networks. Elsevier. 27: 55—71.

[Freeman1979-19] а ^б ^в Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215–239.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]