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

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

Определение

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

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

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

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

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

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

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

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

H ( x ) = ∑ y ≠ x 1 d ( y , x ) . {displaystyle H(x)=sum _{y eq x}{frac {1}{d(y,x)}}.}

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

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

Варианты

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

D ( x ) = ∑ y ≠ x 1 2 d ( y , x ) . {displaystyle D(x)=sum _{y eq x}{frac {1}{2^{d(y,x)}}}.}

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

Если граф G 1 + G 2 {displaystyle G_{1}+G_{2}} создаётся путём соединения узла p {displaystyle p} графа G 1 {displaystyle G_{1}} с узлом q {displaystyle q} графа G 2 {displaystyle G_{2}} , то степень близости комбинированного графа равна: D ( G 1 + G 2 ) = D ( G 1 ) + D ( G 2 ) + ( 1 + D ( p ) ) ( 1 + D ( q ) ) . {displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q)).}

Если граф T ( G ) {displaystyle T(G)} является графом-колючкой (англ. thorn graph) графа G {displaystyle G} , имеющего n {displaystyle n} узлов, то степень близости T ( G ) {displaystyle T(G)} равна: D ( T ( G ) ) = 9 4 D ( G ) + n . {displaystyle D(T(G))={frac {9}{4}}D(G)+n.}

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

D ( x ) = ∑ y ≠ x   α d ( y , x ) , {displaystyle D(x)=sum _{y eq x} {alpha ^{d(y,x)}},}

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

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

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