Степень близости

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

Определение

Степень близости определил Алекс Бавелас^[англ.] в 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)}}.}$

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

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

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

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

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

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

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

Варианты

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

${\displaystyle D(x)=\sum _{y\neq x}{\frac {1}{2^{d(y,x)}}}.}$

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

1. Если граф ${\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)).}$
2. Если граф ${\displaystyle T(G)}$ является графом-колючкой (англ. thorn graph^[12]) графа ${\displaystyle G}$, имеющего ${\displaystyle n}$ узлов, то степень близости ${\displaystyle T(G)}$ равна^[13]: ${\displaystyle D(T(G))={\frac {9}{4}}D(G)+n.}$

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

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

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

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

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

См. также

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