Близость центральности

Понятие в теории графов

В связном графе центральность (или близость ) узла — это мера центральности в сети , вычисляемая как обратная величина суммы длины кратчайших путей между узлом и всеми другими узлами в графе. Таким образом, чем более центральным является узел, тем ближе он ко всем остальным узлам.

Число рядом с каждым узлом — это расстояние от этого узла до квадратного красного узла, измеренное по длине кратчайшего пути. Зеленые ребра иллюстрируют один из двух кратчайших путей между красным квадратным узлом и красным круглым узлом. Таким образом, близость красного квадратного узла равна 5/(1+1+1+2+2) = 5/7.

Близость была определена Бавеласом (1950) как величина, обратная удаленности , [ 1 ^{] [2],} то есть:

${\displaystyle C_{B}(x)={\frac {1}{\sum _{y}d(y,x)}},}$

где — расстояние (длина кратчайшего пути) между вершинами и . Эта ненормализованная версия близости иногда называется статусом. ^{[3] [4] [5]} Когда говорят о центральности близости, обычно имеют в виду ее нормализованную форму, которая представляет собой среднюю длину кратчайших путей вместо их суммы. Обычно она определяется предыдущей формулой, умноженной на , где — количество узлов в графе, что дает: ${\displaystyle d(y,x)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle N-1}$ ${\displaystyle N}$

${\displaystyle C(x)={\frac {N-1}{\sum _{y}d(y,x)}}.}$

Нормализация близости упрощает сравнение узлов в графах разного размера. Для больших графов минус один в нормализации становится несущественным и его часто опускают.

Как одна из старейших мер центральности, близость часто приводится в общих обсуждениях мер центральности сети во вводных текстах ^{[6] [7] [8]} или в статьях, сравнивающих различные меры центральности. ^{[9] [10] [11] [12]} Значения, полученные многими мерами центральности, могут быть тесно коррелированы. ^{[9] [13] [11]} В частности, было показано ^[12] , что близость и степень связаны во многих сетях через приблизительное отношение

${\displaystyle {\frac {1}{C(x)}}\approx {\frac {-1}{\ln(z-1)}}\ln(k_{x})+\beta }$

где — степень вершины , а и β — параметры, найденные путем подгонки близости и степени к этой формуле. Параметр z представляет собой фактор ветвления, среднюю степень узлов (исключая корневой узел и листья) деревьев кратчайших путей, используемых для аппроксимации сетей при демонстрации этой связи. ^[12] Это никогда не является точной связью, но она отражает тенденцию, наблюдаемую во многих реальных сетях. ${\textstyle k_{x}}$ ${\displaystyle x}$ ${\displaystyle z}$

Близость связана с другими шкалами длины, используемыми в сетевой науке. Например, средняя длина кратчайшего пути , среднее расстояние между вершинами в сети, является просто средним значением обратных значений близости ${\textstyle \langle \ell \rangle }$

${\displaystyle \langle \ell \rangle ={\frac {1}{N}}\sum _{x}{\frac {1}{C(x)}}={\frac {1}{N(N-1)}}\sum _{x}\sum _{y}d(y,x)}$.

Учет расстояний от или до всех других узлов не имеет значения в неориентированных графах, тогда как в ориентированных графах он может давать совершенно иные результаты (например, веб-сайт может иметь высокую центральность близости от исходящих ссылок, но низкую центральность близости от входящих ссылок).

Приложения

Близость используется во многих различных контекстах. В библиометрии близость использовалась для изучения того, как ученые выбирают свои журналы и библиографии в различных областях ^[14] или для измерения влияния автора на область и их социального капитала. ^[15] При использовании для выбора потенциальных лидов в данных клиентов близость, как было замечено, приводит к значительному повышению показателя успеха. ^[16] Было показано, что близость города в сети воздушного транспорта тесно связана с социально-экономическими показателями, такими как валовой региональный внутренний продукт. ^[17] Близость также применялась к биологическим сетям ^[5] , где, например, это использовалось для идентификации более 50% глобальных регуляторов в верхних 2% ранжированных генов ^[18] или было обнаружено, что основные гены имеют более высокую близость, чем неосновные гены в сетях взаимодействия белков. ^[19] В метаболической сети близость узлов может идентифицировать наиболее важные метаболиты. ^[20]

В несвязных графиках

Когда граф не является сильно связанным , Бошамп в 1965 году предложил идею использования суммы обратных величин расстояний ^[21] вместо обратной величины суммы расстояний, с соглашением : ${\displaystyle 1/\infty =0}$

${\displaystyle H(x)=\sum _{y\neq x}{\frac {n-1}{d(y,x)}}.}$

Модификация Бошампа следует (гораздо позже по времени) общему принципу, предложенному Марчиори и Латорой (2000) ^[22] , что в графах с бесконечными расстояниями гармоническое среднее ведет себя лучше, чем арифметическое среднее. Действительно, близость Бавеласа можно описать как денормализованную обратную величину арифметического среднего расстояний, тогда как центральность Бошампа является обратной величиной гармонического среднего расстояний.

Эта идея несколько раз всплывала в литературе, часто без фактора нормализации : для неориентированных графов под названием « оцененная центральность» Деккера (2005) ^[23] и под названием ${\displaystyle n-1}$гармоническая центральность по Роша (2009); ^[24] если была аксиоматизирована Гаргом (2009) ^[25] и предложена еще раз позже Опсалом (2010). ^[26] Она была изучена на общих направленных графах Болди и Винья (2014). ^[27] Эта идея также довольно похожа на рыночный потенциал, предложенный Харрисом (1954) ^[28] , который теперь часто называют термином доступ к рынку. ^[29]

Варианты

Дангалчев (2006) ^[30] в работе о сетевой уязвимости предлагает для неориентированных графов другое определение:

${\displaystyle D(x)=\sum _{y\neq x}{\frac {1}{2^{d(y,x)}}}.}$

Это определение эффективно используется для несвязных графов и позволяет создавать удобные формулы для графовых операций. Например:

Если граф создан путем соединения узлов одного графа с узлом другого графа , то объединенная близость равна: ${\displaystyle G_{1}+G_{2}}$ ${\displaystyle p}$ ${\displaystyle G_{1}}$ ${\displaystyle q}$ ${\displaystyle G_{2}}$

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q));}$

если граф создан путем схлопывания узла графа и узла графа в один узел, то близость равна: ^[31] ${\displaystyle G_{1}+G_{2}}$ ${\displaystyle p}$ ${\displaystyle G_{1}}$ ${\displaystyle q}$ ${\displaystyle G_{2}}$

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+2D(p)D(q).}$

Если граф является теневым графом графа , имеющего узлы, то близость равна: ^[32] ${\displaystyle S(G)}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle S(G)}$

${\displaystyle D(S(G))=4D(G)+{\frac {n}{2}}.}$

Если граф является графом шипов графа , который имеет узлы, то близость равна: ^[33] ${\displaystyle T(G)}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle T(G)}$

${\displaystyle D(T(G))={\frac {9}{4}}D(G)+n.}$

Естественным обобщением этого определения является: ^[34]

${\displaystyle D(x)=\sum _{y\neq x}\ {\alpha ^{d(y,x)}},}$

где принадлежит (0,1). При увеличении от 0 до 1 обобщенная близость изменяется от локальной характеристики (степени) до глобальной (числа связанных узлов). ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Информационная центральность Стивенсона и Зелена (1989) — это еще одна мера близости, которая вычисляет гармоническое среднее расстояний сопротивления по направлению к вершине x , которое меньше, если x имеет много путей малого сопротивления, соединяющих ее с другими вершинами. ^[35]

В классическом определении центральности близости распространение информации моделируется с помощью использования кратчайших путей. Эта модель может быть не самой реалистичной для всех типов сценариев связи. Таким образом, были обсуждены связанные определения для измерения близости, такие как центральность близости случайного блуждания, введенная Но и Ригером (2004). Она измеряет скорость, с которой случайно блуждающие сообщения достигают вершины из другого места в графе. ^[36] Иерархическая близость Трана и Квона (2014) ^[37] является расширенной центральностью близости, чтобы иметь дело с еще одним способом ограничения близости в графах, которые не являются сильно связанными. Иерархическая близость явно включает информацию о диапазоне других узлов, на которые может повлиять данный узел.

Смотрите также

• Центральность
• Случайная прогулка близость центральность
• Центральность промежуточности

Ссылки

1. Бавелас, Алекс (1950). «Модели общения в группах, ориентированных на задачу». Журнал Акустического общества Америки . 22 (6): 725–730. Bibcode : 1950ASAJ...22..725B. doi : 10.1121/1.1906679.
2. Sabidussi, G (1966). «Индекс центральности графа». Psychometrika . 31 (4): 581–603. doi :10.1007/bf02289527. hdl : 10338.dmlcz/101401 . PMID  5232444. S2CID  119981743.
3. Харари, Фрэнк (1959). «Статус и контраст». Социометрия . 22 (1): 23–43. doi :10.2307/2785610. JSTOR  2785610.
4. Хаге, Пер; Харари, Фрэнк (1995). «Эксцентричность и центральность в сетях». Социальные сети . 17 (1): 57–63. doi :10.1016/0378-8733(94)00248-9.
5. Wuchty, Stefan; Stadler, Peter F. (2003). "Центры сложных сетей". Журнал теоретической биологии . 223 (1): 45–53. Bibcode :2003JThBi.223...45W. doi :10.1016/S0022-5193(03)00071-7. PMID  12782116.
6. Newman, MEJ (2010). Сети: введение. Оксфорд: Oxford University Press. ISBN 978-0-19-920665-0. OCLC  456837194.
7. Latora, Vito (2017). Complex Networks: principles, methods and applications. Винченцо Никосия, Джованни Руссо. Кембридж, Великобритания. ISBN 978-1-316-21600-2. OCLC  1004620089.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
8. Cosia, Michele (2021). Атлас для начинающих сетевых ученых . arXiv : 2101.00863 . ISBN 9788797282403.
9. Болланд, Джон М. (1988). «Выбор центральности: анализ производительности четырех моделей центральности в реальных и моделируемых сетях». Социальные сети . 10 (3): 233–253. doi :10.1016/0378-8733(88)90014-7.
10. Брандес, Ульрик; Хильденбранд, Ян (2014). «Наименьшие графы с отдельными одиночными центрами». Network Science . 2 (3): 416–418. doi :10.1017/nws.2014.25. ISSN  2050-1242. S2CID  3841410.
11. Шох, Дэвид; Валенте, Томас В.; Брандес, Ульрик (2017). «Корреляции между индексами центральности и классом уникально ранжированных графов». Социальные сети . 50 : 46–54. doi :10.1016/j.socnet.2017.03.010. S2CID  10932381.
12. Эванс, Тим С.; Чен, Биншенг (2022). «Связывание центральности сети с мерами близости и степени». Communications Physics . 5 (1): 172. arXiv : 2108.01149 . Bibcode :2022CmPhy...5..172E. doi :10.1038/s42005-022-00949-5. ISSN  2399-3650. S2CID  236881169.
13. Валенте, Томас В.; Коронжес, Кэтрин; Лакон, Синтия; Костенбадер, Элизабет (01.01.2008). «Насколько коррелируют показатели центральности сети?». Connections (Торонто, Онтарио) . 28 (1): 16–26. ISSN  0226-1766. PMC 2875682. PMID 20505784  . 
14. Ni, Chaoqun; Sugimoto, Cassidy ; Jiang, Jiepu (2011). Noyons, ED; Ngulube, Patrick; Leta, Jacqueline (ред.). «Степень, близость и промежуточность: применение измерений центральности группы для диахронического изучения макродисциплинарной эволюции» (PDF) : 605. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
15. Ян, Эрджиа; Дин, Ин (2009). «Применение мер центральности к анализу воздействия: анализ сетей соавторства». Журнал Американского общества информационной науки и технологий . 60 (10): 2107–2118. arXiv : 1012.4862 . doi : 10.1002/asi.21128. S2CID  261294843.
16. Кисс, Кристин; Бихлер, Мартин (2008). «Идентификация влиятельных лиц — измерение влияния в клиентских сетях». Системы поддержки принятия решений . 46 (1): 233–253. doi :10.1016/j.dss.2008.06.007. S2CID  9783337.
17. Ван, Цзяоэ; Мо, Хуэйхуэй; Ван, Фахуэй; Цзинь, Фэнцзюнь (2011). «Изучение сетевой структуры и узловой центральности сети воздушного транспорта Китая: комплексный сетевой подход». Журнал географии транспорта . 19 (4): 712–721. doi :10.1016/j.jtrangeo.2010.08.012.
18. Koschützki, Dirk; Schreiber, Falk (2008). «Методы анализа центральности для биологических сетей и их применение к сетям генной регуляции». Gene Regulation and Systems Biology . 2 : 193–201. doi :10.4137/GRSB.S702. ISSN  1177-6250. PMC 2733090 . PMID  19787083. 
19. Хан, Мэтью В.; Керн, Эндрю Д. (2005). «Сравнительная геномика центральности и эссенциальности в трех сетях взаимодействия белков эукариот». Молекулярная биология и эволюция . 22 (4): 803–806. doi : 10.1093/molbev/msi072 . ISSN  1537-1719. PMID  15616139.
20. Ma, H.-W.; Zeng, A.-P. (2003-07-22). «Структура связности, гигантский сильный компонент и центральность метаболических сетей». Биоинформатика . 19 (11): 1423–1430. doi : 10.1093/bioinformatics/btg177 . ISSN  1367-4803. PMID  12874056.
21. Beauchamp, Murray (1965). «Улучшенный индекс центральности». Behavioral Science . 10 (2): 161–163. doi :10.1002/bs.3830100205. PMID  14284290.
22. Маркиори, Массимо; Латора, Вито (2000), «Гармония в маленьком мире», Physica A , 285 (3–4): 539–546, arXiv : cond-mat/0008357 , Bibcode : 2000PhyA..285..539M, doi : 10.1016/s0378-4371(00)00311-3, S2CID  10523345
23. Деккер, Энтони (2005). «Концептуальная дистанция в анализе социальных сетей». Журнал социальной структуры . 6 (3).
24. Янник Рочат. Центральность по близости, распространенная на несвязанные графы: индекс гармонической центральности (PDF) . Приложения анализа социальных сетей, ASNA 2009.
25. Манудж Гарг (2009), Аксиоматические основы центральности в сетях , doi :10.2139/ssrn.1372441, S2CID  117717919
26. Торе Опсаль (2010-03-20). «Центральность близости в сетях с разъединенными компонентами».
27. Болди, Паоло; Винья, Себастьяно (2014), «Аксиомы центральности», Internet Mathematics , 10 (3–4): 222–262, doi : 10.1080/15427951.2013.865686
28. Харрис, Чонси Д. (1954). «Рынок как фактор локализации промышленности в Соединенных Штатах». Анналы Ассоциации американских географов . 44 (4): 315–348. doi :10.2307/2561395. JSTOR  2561395.
29. Гутберлет, Тереза. Дешевый уголь против доступа к рынку: роль природных ресурсов и спроса в индустриализации Германии. Рабочий документ. 2014.
30. Ч., Дангалчев (2006). «Остаточная близость в сетях». Physica A. 365 ( 2): 556. Bibcode : 2006PhyA..365..556D. doi : 10.1016/j.physa.2005.12.020.
31. Ч., Дангалчев (2020). «Дополнительная близость и рост сетей». Fundamenta Informaticae . 176 (1): 1–15. doi :10.3233/FI-2020-1960. S2CID  226300861.
32. Дангалчев, Чавдар (2023). «Близость некоторых графовых операций». arXiv : 2308.14491 [cs.DM].
33. Ч., Дангалчев (2018). «Остаточная близость обобщенных графов шипов». Fundamenta Informaticae . 162 (1): 1–15. doi :10.3233/FI-2018-1710. S2CID  52073138.
34. Ч., Дангалчев (2011). «Остаточная близость и обобщенная близость». Международный журнал оснований компьютерной науки . 22 (8): 1939–1948. doi :10.1142/s0129054111009136.
35. Стивенсон, КА; Зелен, М. (1989). «Переосмысление центральности: методы и примеры». Социальные сети . 11 : 1–37. doi :10.1016/0378-8733(89)90016-6.
36. Noh, JD; Rieger, H. (2004). "Случайные блуждания по сложным сетям". Phys. Rev. Lett . 92 (11): 118701. arXiv : cond-mat/0307719 . Bibcode :2004PhRvL..92k8701N. doi :10.1103/physrevlett.92.118701. PMID  15089179. S2CID  14767557.
37. Тран, Тиен-Дзунг; Квон, Юнг-Кын (2014). «Иерархическая близость эффективно предсказывает гены болезней в направленной сигнальной сети». Computational Biology and Chemistry . 53 : 191–197. doi : 10.1016/j.compbiolchem.2014.08.023. PMID  25462327.