Центральность по близости

Концепция теории графов

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

Число рядом с каждым узлом — это расстояние от этого узла до квадратного красного узла, измеренное длиной кратчайшего пути. Зеленые края иллюстрируют один из двух кратчайших путей между узлом красного квадрата и узлом красного круга. Следовательно, близость узла красного квадрата равна 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. Бибкод : 1950ASAJ...22..725B. дои : 10.1121/1.1906679.
2. Сабидусси, Г (1966). «Индекс центральности графа». Психометрика . 31 (4): 581–603. дои : 10.1007/bf02289527. hdl : 10338.dmlcz/101401 . PMID  5232444. S2CID  119981743.
3. Харари, Фрэнк (1959). «Статус и контрастатус». Социометрия . 22 (1): 23–43. дои : 10.2307/2785610. JSTOR  2785610.
4. Хаге, Пер; Харари, Фрэнк (1995). «Эксцентриситет и центральность в сетях». Социальные сети . 17 (1): 57–63. дои : 10.1016/0378-8733(94)00248-9.
5. Вухти, Стефан; Стадлер, Питер Ф. (2003). «Центры сложных сетей». Журнал теоретической биологии . 223 (1): 45–53. Бибкод : 2003JThBi.223...45W. дои : 10.1016/S0022-5193(03)00071-7. ПМИД  12782116.
6. Ньюман, MEJ (2010). Сети: введение. Оксфорд: Издательство Оксфордского университета. ISBN 978-0-19-920665-0. ОСЛК  456837194.
7. Латора, Вито (2017). Сложные сети: принципы, методы и приложения. Винченцо Никосия, Джованни Руссо. Кембридж, Великобритания. ISBN 978-1-316-21600-2. ОСЛК  1004620089.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
8. Косия, Мишель (2021). Атлас для начинающего сетевого ученого . arXiv : 2101.00863 . ISBN 9788797282403.
9. Болланд, Джон М. (1988). «Выбор центральности: анализ эффективности четырех моделей центральности в реальных и смоделированных сетях». Социальные сети . 10 (3): 233–253. дои : 10.1016/0378-8733(88)90014-7.
10. Брандес, Ульрик; Хильденбранд, январь (2014). «Наименьшие графы с отдельными одноэлементными центрами». Сетевая наука . 2 (3): 416–418. дои : 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). «Связывание центральности сети измеряет близость и степень». Физика связи . 5 (1): 172. arXiv : 2108.01149 . Бибкод : 2022CmPhy...5..172E. дои : 10.1038/s42005-022-00949-5. ISSN  2399-3650. S2CID  236881169.
13. Валенте, Томас В.; Коронж, Кэтрин; Лакон, Синтия; Костенбейдер, Элизабет (1 января 2008 г.). «Насколько коррелированы меры сетевой централизации?». Связи (Торонто, Онтарио) . 28 (1): 16–26. ISSN  0226-1766. ПМЦ 2875682 . ПМИД  20505784. 
14. Ни, Чаокун; Сугимото, Кэссиди ; Цзян, Цзепу (2011). Нойонс, Эд; Нгулубе, Патрик; Лета, Жаклин (ред.). «Степень, близость и взаимосвязь: применение измерений централизации группы для диахронического исследования макродисциплинарной эволюции» (PDF) : 605. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
15. Ян, Эрджиа; Дин, Ин (2009). «Применение мер централизации для анализа воздействия: анализ сети соавторства». Журнал Американского общества информатики и технологий . 60 (10): 2107–2118. arXiv : 1012.4862 . дои : 10.1002/asi.21128. S2CID  261294843.
16. Поцелуй, Кристина; Бихлер, Мартин (2008). «Идентификация влиятельных лиц — Измерение влияния в сетях клиентов». Системы поддержки принятия решений . 46 (1): 233–253. дои : 10.1016/j.dss.2008.06.007. S2CID  9783337.
17. Ван, Цзяэ; Мо, Хуэйхуэй; Ван, Фахуи; Джин, Фэнджун (2011). «Изучение сетевой структуры и узловой централизации сети воздушного транспорта Китая: комплексный сетевой подход». Журнал транспортной географии . 19 (4): 712–721. дои : 10.1016/j.jtrangeo.2010.08.012.
18. Кошюцкий, Дирк; Шрайбер, Фальк (2008). «Методы центрального анализа биологических сетей и их применение к сетям регуляции генов». Регуляция генов и системная биология . 2 : 193–201. дои : 10.4137/GRSB.S702. ISSN  1177-6250. ПМК 2733090 . ПМИД  19787083. 
19. Хан, Мэтью В.; Керн, Эндрю Д. (2005). «Сравнительная геномика центральности и существенности в трех эукариотических сетях взаимодействия белков». Молекулярная биология и эволюция . 22 (4): 803–806. дои : 10.1093/molbev/msi072 . ISSN  1537-1719. ПМИД  15616139.
20. Ма, Х.-В.; Цзэн, А.-П. (22 июля 2003 г.). «Структура связности, гигантский сильный компонент и центральность метаболических сетей». Биоинформатика . 19 (11): 1423–1430. doi : 10.1093/биоинформатика/btg177 . ISSN  1367-4803. ПМИД  12874056.
21. Бошан, Мюррей (1965). «Улучшенный индекс центральности». Поведенческая наука . 10 (2): 161–163. дои : 10.1002/bs.3830100205. ПМИД  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. Торе Опсал (20 марта 2010 г.). «Центральность близости в сетях с отключенными компонентами».
27. Болди, Паоло; Винья, Себастьяно (2014), «Аксиомы центральности», Internet Mathematics , 10 (3–4): 222–262, doi : 10.1080/15427951.2013.865686
28. Харрис, Чонси Д. (1954). «Рынок как фактор локализации промышленности в США». Анналы Ассоциации американских географов . 44 (4): 315–348. дои : 10.2307/2561395. JSTOR  2561395.
29. Гутберлет, Тереза. Дешевый уголь против доступа к рынку: роль природных ресурсов и спроса в индустриализации Германии. Рабочий документ. 2014.
30. Ч, Дангальчев (2006). «Остаточная закрытость в сетях». Физика А. 365 (2): 556. Бибкод : 2006PhyA..365..556D. doi :10.1016/j.physa.2005.12.020.
31. Ч, Дангальчев (2020). «Дополнительная близость и рост сетей». Фундамента информатики . 176 (1): 1–15. дои : 10.3233/FI-2020-1960. S2CID  226300861.
32. Дангальчев, Чавдар (2023). «Близость некоторых операций с графами». arXiv : 2308.14491 [cs.DM].
33. Ч, Дангальчев (2018). «Остаточная близость обобщенных графов Торна». Фундамента информатики . 162 (1): 1–15. дои : 10.3233/FI-2018-1710. S2CID  52073138.
34. Ч, Дангальчев (2011). «Остаточная близость и генерализованная близость». Международный журнал основ компьютерных наук . 22 (8): 1939–1948. дои : 10.1142/s0129054111009136.
35. Стивенсон, Калифорния; Зелен, М. (1989). «Переосмысление центральности: методы и примеры». Социальные сети . 11 :1–37. дои : 10.1016/0378-8733(89)90016-6.
36. Нет, Джей Ди; Ригер, Х. (2004). «Случайные блуждания по сложным сетям». Физ. Преподобный Летт . 92 (11): 118701. arXiv : cond-mat/0307719 . Бибкод : 2004PhRvL..92k8701N. doi : 10.1103/physrevlett.92.118701. PMID  15089179. S2CID  14767557.
37. Тран, Тьен-Дзунг; Квон, Юнг-Гын (2014). «Иерархическая близость эффективно предсказывает гены заболеваний в направленной сигнальной сети». Вычислительная биология и химия . 53 : 191–197. doi :10.1016/j.compbiolchem.2014.08.023. ПМИД  25462327.