Близость центральности

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

Близость была определена Бавеласом (1950) как величина, обратная удаленности , [ 1 ^{] [2],} то есть:

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

где — расстояние (длина кратчайшего пути) между вершинами и . Эта ненормализованная версия близости иногда называется статусом. ^{[3] [4] [5]} Когда говорят о центральности близости, обычно имеют в виду ее нормализованную форму, которая представляет собой среднюю длину кратчайших путей вместо их суммы. Обычно она определяется предыдущей формулой, умноженной на , где — количество узлов в графе, что дает:${\displaystyle d(y,x)}$${\displaystyle x}$${\displaystyle у}$${\displaystyle N-1}$${\displaystyle N}$

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

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

Как одна из старейших мер центральности, близость часто приводится в общих обсуждениях мер центральности сети во вводных текстах ^{[6] [7] [8]} или в статьях, сравнивающих различные меры центральности. ^{[9] [10] [11] [12]} Значения, полученные многими мерами центральности, могут быть тесно коррелированы. ^{[9] [13] [11]} В частности, было показано ^[12] , что близость и степень связаны во многих сетях через приблизительное отношение

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

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

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

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

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

Близость используется во многих различных контекстах. В библиометрии близость использовалась для изучения того, как ученые выбирают свои журналы и библиографии в различных областях ^[14] или для измерения влияния автора на область и их социального капитала. ^[15] При использовании для выбора потенциальных лидов в данных клиентов близость, как было замечено, приводит к значительному повышению показателя успеха. ^[16] Было показано, что близость города в сети воздушного транспорта тесно связана с социально-экономическими показателями, такими как валовой региональный внутренний продукт. ^[17] Близость также применялась к биологическим сетям ^[5] , где, например, это использовалось для идентификации более 50% глобальных регуляторов в верхних 2% ранжированных генов ^[18] или было обнаружено, что основные гены имеют более высокую близость, чем неосновные гены в сетях взаимодействия белков. ^[19] В метаболической сети близость узлов может идентифицировать наиболее важные метаболиты. ^[20]

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

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

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

Эта идея несколько раз всплывала в литературе, часто без фактора нормализации : для неориентированных графов под названием « оцененная центральность» Деккера (2005) ^[23] и под названием${\displaystyle n-1}$гармоническая центральность по Роша (2009); ^[24] если была аксиоматизирована Гаргом (2009) ^[25] и предложена еще раз позже Опсалом (2010). ^[26] Она была изучена на общих направленных графах Болди и Винья (2014). ^[27] Эта идея также довольно похожа на рыночный потенциал, предложенный Харрисом (1954) ^[28] , который теперь часто называют термином доступ к рынку. ^[29]

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

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

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

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

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

если граф создан путем схлопывания узла графа и узла графа в один узел, то близость равна: ^[31]${\displaystyle G_{1}+G_{2}}$${\displaystyle p}$${\displaystyle G_{1}}$${\displaystyle д}$${\displaystyle G_{2}}$

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

Если граф является теневым графом графа , имеющего узлы, то близость равна: ^[32]${\displaystyle S(G)}$${\displaystyle G}$${\displaystyle n}$${\displaystyle S(G)}$

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

Если граф является графом шипов графа , который имеет узлы, то близость равна: ^[33]${\displaystyle T(G)}$${\displaystyle G}$${\displaystyle n}$${\displaystyle T(G)}$

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

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

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

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

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

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

• Центральность
• Случайная прогулка близость центральность
• Центральность промежуточности