Степень близости (теория графов)

Перейти к навигацииПерейти к поиску

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

Определение

Степень близости определил Алекс Бавелас[англ.] в 1950 году как обратную величину удалённости[1][2], то есть

где равно расстоянию между вершинами и . Когда говорят о степени близости, обычно имеют в виду её нормализованную форму, которая представляет собой средние кратчайшие пути вместо их суммы. Она обычно даётся предыдущей формулой, умноженной на , где равно числу узлов графа. Для больших графов эта разница становится несущественной, так что опускается:

Эта поправка позволяет выполнять сравнение между узлами графов различных размеров.

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

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

Если граф не сильно связан, широко распространена идея использования суммы обратных величин к расстояниям вместо обратной величины к сумме расстояний при соглашении, что :

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

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

Варианты

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

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

  1. Если граф создаётся путём соединения узла графа с узлом графа , то степень близости комбинированного графа равна:
  2. Если граф является графом-колючкой (англ. thorn graph[12]) графа , имеющего узлов, то степень близости равна[13]:

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

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

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

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

См. также

Примечания

  1. Bavelas, 1950, с. 725–730.
  2. Sabidussi, 1966, с. 581–603.
  3. Marchiori, Latora, 2000, с. 539–546.
  4. Dekker, 2005.
  5. Rochat, 2009.
  6. Garg, 2009.
  7. Opsahl, 2010.
  8. Boldi, Vigna, 2014, с. 222–262.
  9. Harris, 1954, с. 315–348.
  10. Gutberlet, 2014.
  11. Dangalchev, 2006, с. 556.
  12. Граф-колючка графа G — это граф, полученный добавлением каждому узлу графа G некоторого числа дополнительных висячих вершин, то есть вершин, связанных только с этом узлом (Azari 2018).
  13. Dangalchev, 2018, с. 1–15.
  14. Dangalchev, 2011, с. 1939–1948.
  15. Stephenson, Zelen, 1989, с. 1–37.
  16. Noh, Rieger, 2004, с. 118701.
  17. Tran, Kwon, 2014.

Литература

  • Mahdieh Azari. ON THE GUTMAN INDEX OF THORN GRAPHS // Kragujevac J. Sci.. — 2018. — Т. 40. — С. 33—48.
  • Chavdar Dangalchev. Residual Closeness in Networks // Physica A. — 2006. — Т. 365.
  • Chavdar Dangalchev. Residual Closeness of Generalized Thorn Graphs // Fundamenta Informaticae. — 2018. — Т. 162, вып. 1.
  • Chavdar Dangalchev. Residual Closeness and Generalized Closeness // IJFCS. — 2011. — Т. 22, вып. 8.
  • Massimo Marchiori, Vito Latora. Harmony in the small-world // Physica A: Statistical Mechanics and its Applications. — 2000. — Т. 285, вып. 3–4. — doi:10.1016/s0378-4371(00)00311-3. — Bibcode2000PhyA..285..539M. — arXiv:cond-mat/0008357.
  • Anthony Dekker. Conceptual Distance in Social Network Analysis // Journal of Social Structure. — 2005. — Т. 6, вып. 3.
  • Yannick Rochat. Closeness centrality extended to unconnected graphs: The harmonic centrality index // Applications of Social Network Analysis, ASNA 2009. — 2009.
  • Manuj Garg. Axiomatic Foundations of Centrality in Networks. — 2009. — doi:10.2139/ssrn.1372441.
  • Tore Opsahl. Closeness centrality in networks with disconnected components. — 2010. — Март.
  • Paolo Boldi, Sebastiano Vigna. Axioms for Centrality // Internet Mathematics. — 2014. — Т. 10, вып. 3–4. — doi:10.1080/15427951.2013.865686.
  • Harris C. D. The, market as a factor in the localization of industry in the united states // Annals of the association of American geographers. — 1954. — Т. 44, вып. 4.
  • Theresa Gutberlet. Cheap Coal versus Market Access: The Role of Natural Resources and Demand in Germany's Industrialization // Working Paper. — 2014.
  • Alex Bavelas. Communication patterns in task-oriented groups // J. Acoust. Soc. Am. — 1950. — Т. 22, вып. 6.
  • Sabidussi G. The centrality index of a graph // Psychometrika. — 1966. — Т. 31, вып. 4. — doi:10.1007/bf02289527. — PMID 5232444.
  • Stephenson K. A., Zelen M. Rethinking centrality: Methods and examples // Social Networks. — 1989. — Т. 11. — doi:10.1016/0378-8733(89)90016-6.
  • Noh J. D., Rieger H. Random Walks on Complex Networks // Phys. Rev. Lett.. — 2004. — Т. 92, вып. 11. — doi:10.1103/physrevlett.92.118701. — Bibcode2004PhRvL..92k8701N. — arXiv:cond-mat/0307719. — PMID 15089179.
  • Tien-Dzung Tran, Yung-Keun Kwon. Hierarchical closeness efficiently predicts disease genes in a directed signaling network // Computational biology and chemistry. — 2014. — Сентябрь (т. 53PB). — ISSN 1476-928X.