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

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

Определение

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

C (x) = \frac{1}{\sum_{y} d (y, x)} .

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

C (x) = \frac{N}{\sum_{y} d (y, x)} .

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

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

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

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

H (x) = \sum_{y \neq x} \frac{1}{d (y, x)} .

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

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

Варианты

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

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

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

D (x) = \sum_{y \neq x} α^{d (y, x)},

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

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

↑ Граф-колючка графа G — это граф, полученный добавлением каждому узлу графа G некоторого числа дополнительных висячих вершин, то есть вершин, связанных только с этом узлом Шаблон:Harv.

[1] Граф-колючка графа G — это граф, полученный добавлением каждому узлу графа G некоторого числа дополнительных висячих вершин, то есть вершин, связанных только с этом узлом Шаблон:Harv.

[1]

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

Содержание

Определение

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

Варианты

См. также

Примечания

Литература

Навигация

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

Определение

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

Варианты

См. также

Примечания

Литература

Навигация

Поиск