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

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

ОпределениеПравить

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

$C(x)=\frac{1}{\underset{y}{\sum <!--\; \sum \; -->}d(y,x)}.$$C(x)={\frac {1}{\sum _{y}d(y,x)}}.$ 

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

$C(x)=\frac{N}{\underset{y}{\sum <!--\; \sum \; -->}d(y,x)}.$$C(x)={\frac {N}{\sum _{y}d(y,x)}}.$ 

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

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

В несвязных графахПравить

Если граф не сильно связан, широко распространена идея использования суммы обратных величин к расстояниям вместо обратной величины к сумме расстояний при соглашении, что $1/\mathrm{\infty <!--\; \infty \; -->}=0$$1/\infty =0$ :

$H(x)=\underset{y\ne <!--\; \ne \; -->x}{\sum <!--\; \sum \; -->}\frac{1}{d(y,x)}.$$H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}.$ 

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

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

ВариантыПравить

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

$D(x)=\underset{y\ne <!--\; \ne \; -->x}{\sum <!--\; \sum \; -->}\frac{1}{2^{d(y,x)}}.$$D(x)=\sum _{y\neq x}{\frac {1}{2^{d(y,x)}}}.$ 

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

1. Если граф $G_1+G_2$$G_{1}+G_{2}$  создаётся путём соединения узла $p$$p$  графа $G_1$$G_{1}$  с узлом $q$$q$  графа $G_2$$G_{2}$ , то степень близости комбинированного графа равна:$D(G_1+G_2)=D(G_1)+D(G_2)+(1+D(p))(1+D(q)).$$D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q)).$ 
2. Если граф $T(G)$$T(G)$  является графом-колючкой (англ. thorn graph) графа $G$$G$ , имеющего $n$$n$  узлов, то степень близости $T(G)$$T(G)$  равна: $D(T(G))=\frac{9}{4}D(G)+n.$$D(T(G))={\frac {9}{4}}D(G)+n.$ 

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

$D(x)=\underset{y\ne <!--\; \ne \; -->x}{\sum <!--\; \sum \; -->}{\mathrm{\alpha <!--\; \alpha \; -->}}^{d(y,x)},$$D(x)=\sum _{y\neq x}\ {\alpha ^{d(y,x)}},$ 

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

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

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

См. такжеПравить

• Центральность
• Степень бизости по случайным маршрутам^[en]
• Степень посредничества

ЛитератураПравить

• 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. — Bibcode: 2000PhyA..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. — Bibcode: 2004PhRvL..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.