Центральность близости - Closeness centrality

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

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

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

куда ${displaystyle d(y,x)}$ это расстояние между вершинами ${displaystyle x}$ и ${displaystyle y}$. Говоря о центральности по близости, люди обычно ссылаются на ее нормализованную форму, которая представляет собой среднюю длину кратчайших путей вместо их суммы. Обычно это дается предыдущей формулой, умноженной на ${displaystyle N-1}$, куда ${displaystyle N}$ количество узлов в графе. Для больших графиков эта разница становится несущественной, поэтому ${displaystyle -1}$ сбрасывается, что приводит к:

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

Нормализация позволяет сравнивать узлы графов разного размера.

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

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

Когда график не сильно связанный, широко распространена идея использования суммы, обратной величины расстояний, вместо суммы, обратной суммы расстояний, с условием ${displaystyle 1/infty =0}$:

${displaystyle H(x)=sum _{yeq x}{frac {1}{d(y,x)}}.}$

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

Эта идея была явно заявлена ​​для неориентированных графов под названием ценная центральность Деккер (2005)^[4] и под именем гармоническая центральность Роша (2009),^[5] аксиоматизируется Гаргом (2009)^[6] и был снова предложен позже Опсалом (2010).^[7] Он был изучен на общих ориентированных графах Болди и Винья (2014).^[8] Эта идея также очень похожа на рыночный потенциал, предложенный Харрисом (1954).^[9] который сейчас часто называют доступом на рынок.^[10]

Варианты

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

${displaystyle D(x)=sum _{yeq 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));}$

если график ${displaystyle G_{1}+G_{2}}$ создается сворачивающимся узлом ${displaystyle p}$ графика ${displaystyle G_{1}}$ и узел ${displaystyle q}$ графика ${displaystyle G_{2}}$ в один узел, тогда близость:^[12]

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

Если график ${displaystyle T(G)}$ это шип граф графа ${displaystyle G}$, у которого есть ${displaystyle n}$ узлы, то ${displaystyle T(G)}$ близость:^[13]

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

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

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

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

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

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

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

• Центральность
• Центральность близости случайного блуждания
• Центральность посредничества

Рекомендации

1. Алекс Бавелас. Паттерны общения в целевых группах. J. Acoust. Soc. Являюсь, 22(6):725–730, 1950.
2. Сабидусси, G (1966). «Индекс центральности графа». Психометрика. 31 (4): 581–603. Дои:10.1007 / bf02289527. HDL:10338.dmlcz / 101401. PMID  5232444.
3. Марчиори, Массимо; Латора, Вито (2000), «Гармония в маленьком мире», Physica A: Статистическая механика и ее приложения, 285 (3–4): 539–546, arXiv:cond-mat / 0008357, Bibcode:2000PhyA..285..539M, Дои:10.1016 / s0378-4371 (00) 00311-3
4. Деккер, Энтони (2005). «Концептуальная дистанция в анализе социальных сетей». Журнал социальной структуры. 6 (3).
5. Янник Рошат. Центральность по близости распространяется на несвязные графы: индекс гармонической центральности (PDF). Приложения анализа социальных сетей, ASNA 2009.
6. Манудж Гарг (2009), Аксиоматические основы центральности в сетях, Дои:10.2139 / ssrn.1372441
7. Тор Опсаль (2010-03-20). «Централизация близости в сетях с отключенными компонентами».
8. Болди, Паоло; Винья, Себастьяно (2014), «Аксиомы центральности», Интернет-математика, 10 (3–4): 222–262, Дои:10.1080/15427951.2013.865686
9. К. Д. Харрис. Рынок как фактор локализации промышленности в США. Анналы ассоциации американских географов, 44 (4): 315–348, 1954.
10. Гутберлет, Тереза. Дешевый уголь против доступа к рынку: роль природных ресурсов и спроса в индустриализации Германии. Рабочий документ. 2014 г.
11. Ч., Дангалчев (2006). «Остаточная закрытость в сетях». Physica A. 365 (2): 556. Дои:10.1016 / j.physa.2005.12.020.
12. Ч., Дангалчев (2020). «Дополнительная близость и рост сетей». Fundamenta Informaticae. 176 (1): 1–15. Дои:10.3233 / FI-2020-1960.
13. Ч., Дангалчев (2018). «Остаточная близость обобщенных шиповых графов». Fundamenta Informaticae. 162 (1): 1–15. Дои:10.3233 / FI-2018-1710.
14. Ч., Дангалчев (2011). «Остаточная близость и генерализованная близость». IJFCS. 22 (8): 1939–1948. Дои:10.1142 / s0129054111009136.
15. Стефенсон, К. А .; Зелен, М. (1989). «Переосмысление центральности: методы и примеры». Социальные сети. 11: 1–37. Дои:10.1016/0378-8733(89)90016-6.
16. Noh, J.D .; Ригер, Х. (2004). «Случайные блуждания в сложных сетях». Phys. Rev. Lett. 92 (11): 118701. arXiv:cond-mat / 0307719. Bibcode:2004PhRvL..92k8701N. Дои:10.1103 / Physrevlett.92.118701. PMID  15089179.
17. Тран, Т.-Д. и Квон, Ю.-К. Иерархическая близость эффективно предсказывает гены заболеваний в направленной сигнальной сети, вычислительной биологии и химии.