Центральность по близости

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

Число рядом с каждым узлом — это расстояние от этого узла до квадратного красного узла, измеренное длиной кратчайшего пути. Зеленые края иллюстрируют один из двух кратчайших путей между узлом красного квадрата и узлом красного круга. Следовательно, близость узла красного квадрата равна 5/(1+1+1+2+2) = 5/7.

Близость была определена Бавеласом (1950) как величина обратная дальности , , то есть:

$C_{B}(x)={\frac {1}{\sum _{y}d(y,x)}},$

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

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

Нормализация близости упрощает сравнение узлов в графах разного размера. Для больших графов минус один при нормализации становится несущественным и его часто отбрасывают.

Будучи одной из старейших мер центральности, близость часто упоминается в общих обсуждениях мер центральности сети во вводных текстах. или в статьях, сравнивающих различные меры центральности. Значения, полученные с помощью многих показателей центральности, могут быть сильно коррелированы. В частности, близость и степень показана быть связанным во многих сетях посредством приблизительного отношения

${\frac {1}{C(x)}}\approx {\frac {-1}{\ln(z-1)}}\ln(k_{x})+\beta$

где ${\textstyle k_{x}}$ степень вершины $x$ пока $z$ и β — параметры, найденные путем подгонки близости и степени к этой формуле. Параметр z представляет собой коэффициент ветвления, среднюю степень узлов (исключая корневой узел и листья) деревьев кратчайшего пути , используемых для аппроксимации сетей при демонстрации этой взаимосвязи. Это никогда не является точным соотношением, но оно отражает тенденцию, наблюдаемую во многих реальных сетях.

Близость связана с другими масштабами длины, используемыми в сетевых науках. Например, средняя длина кратчайшего пути ${\textstyle \langle \ell \rangle }$, среднее расстояние между вершинами в сети, представляет собой просто среднее значение обратных значений близости

$\langle \ell \rangle ={\frac {1}{N}}\sum _{x}{\frac {1}{C(x)}}={\frac {1}{N(N-1)}}\sum _{x}\sum _{y}d(y,x)$ .

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

Приложения

Близость используется во многих различных контекстах. В библиометрии близость использовалась для изучения того, как ученые выбирают свои журналы и библиографии в различных областях. или для измерения влияния автора на область и его социальный капитал. Было замечено, что при использовании для выбора потенциальных потенциальных клиентов в данных о клиентах близость приводит к значительному увеличению показателя успеха. Было показано, что близость города к сети воздушного транспорта тесно коррелирует с социально-экономическими показателями, такими как валовой региональный внутренний продукт. Близость также применялась к биологическим сетям. где, например, это использовалось для идентификации более 50% глобальных регуляторов в верхних 2% ранжированных генов. или было обнаружено, что существенные гены имеют более высокую близость, чем несущественные гены в сетях взаимодействия белков. В метаболической сети близость узлов позволяет идентифицировать наиболее важные метаболиты.

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

Когда граф не сильно связен , Бошан в 1965 году ввел идею использования суммы обратных расстояний: вместо обратной величины суммы расстояний, с соглашением $1/\infty =0$:

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

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

Эта идея несколько раз всплывала в литературе, часто без коэффициента нормализации. $n-1$: для неориентированных графов под названием «центральность» Деккера (2005). и под названием «Гармоническая центральность» Роша (2009); если бы было аксиомой Гарга (2009) и предложен еще раз позже Опсалом (2010). Он был изучен на общих ориентированных графах Болди и Винья (2014). Эта идея также очень похожа на рыночный потенциал, предложенный Харрисом (1954). который сейчас часто называют доступом к рынку.

Варианты

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

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

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

Если график $G_{1}+G_{2}$ создается путем связывания узла $p$ графа $G_{1}$ узел $q$ графа $G_{2}$ тогда объединенная близость равна:

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

если график $G_{1}+G_{2}$ создается путем свертывания узла $p$ графа $G_{1}$ и узел $q$ графа $G_{2}$ в один узел, то близость равна:

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

Если график $S(G)$ это теневой график графика $G$, который имеет $n$ узлы, то $S(G)$ близость – это:

$D(S(G))=4D(G)+{\frac {n}{2}}.$

Если график $T(G)$ это шип графа $G$, который имеет $n$ узлы, то $T(G)$ близость – это:

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

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

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

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

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

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

См. также

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