Степень близости узла (к другим узлам) — это мера центральности в сети, вычисляемая как обратная величина суммы длин кратчайших путей между узлом и всеми другими узлами графа. Таким образом, чем более централен узел, тем ближе он ко всем другим узлам.
Определение Степень близости определил в 1950 году как обратную величину удалённости, то есть
где равно расстоянию между вершинами и . Когда говорят о степени близости, обычно имеют в виду её нормализованную форму, которая представляет собой средние кратчайшие пути вместо их суммы. Она обычно даётся предыдущей формулой, умноженной на , где равно числу узлов графа. Для больших графов эта разница становится несущественной, так что опускается:
Эта поправка позволяет выполнять сравнение между узлами графов различных размеров.
Рассмотрение расстояний из или в другие узлы не имеет смысла для неориентированных графов, в то время как оно может дать совершенно различные результаты для ориентированных графов (например, web-сайт может иметь высокую степень близости для выходящего соединения, но низкую степень близости для входящих соединений).
В несвязных графах Если граф не сильно связан, широко распространена идея использования суммы обратных величин к расстояниям вместо обратной величины к сумме расстояний при соглашении, что :
Наиболее естественной модификацией определения близости Бавеласа является следующий общий принцип, который предложили Марчиони и Латора (2000): в графах с неограниченными расстояниями среднее гармоническое ведёт себя лучше, чем среднее арифметическое. Более того, близость Бавелоса можно описать как ненормализованную обратную величину среднего арифметического расстояний, в то время как гармоническая центральность равна ненормализованной величине, обратной среднему гармоническому расстояний.
Эту идею явно высказал для ориентированных графов Деккер под названием значимая центральность () и Рочат под названием гармоническая центральность (2009). Гарг аксиоматизировал понятие (2009), а Опсал предложил его снова (2010). Понятие изучали на ориентированных графах общего вида Болди и Вигна (2014). Эта идея весьма похожа на потенциал сбыта, предложенный Харрисом (1954), который теперь часто употребляется под названием доступ на рынок.
Варианты Дангалчев (2006) в работе по уязвимости сетей предложил для неориентированных графов другое определение:
Это определение эффективно для несвязанных графов и позволяет использовать удобную формулировку операций над графами. Например:
Если граф создаётся путём соединения узла графа с узлом графа , то степень близости комбинированного графа равна: Если граф является графом-колючкой (Граф-колючка графа G — это граф, полученный добавлением каждому узлу графа G некоторого числа дополнительных висячих вершин, то есть вершин, связанных только с этом узлом .) графа , имеющего узлов, то степень близости равна:
Естественное обобщение определения:
где принадлежит интервалу (0,1). При увеличении с 0 до 1, обобщённая степень близости меняется с локальной характеристики (степени вершины) до глобальной (число связанных узлов).
Информационная центральность Стефенсона и Зелена (1989) является другой мерой близости, которая вычисляет среднее гармоническое расстояний сопротивления в направлении вершины x, которое меньше, если x имеет много путей с малым сопротивлением, соединяющих её с другими вершинами.
В классическом определении степени близости распространение информации моделируется с помощью кратчайших путей. Эта модель может оказаться не вполне реалистичной для некоторых типов сценариев коммуникации. Обсуждались связанные определения меры близости, такие как , которую предложили Нох и Ригер (2004). Этот показатель измеряет скорость, с какой случайные маршруты сообщений достигают вершины отовсюду из графа — вариант степени близости на основе случайных блужданий. Трана и Квона (2014) является расширенным показателем степени близости на основе другого подхода, чтобы обойти ограничения степени близости для графов, не обладающих сильной связностью. Иерархическая центральность явно включает информацию о наборе других узлов, на которые может повлиять данный узел.
См. также Центральность
Степень посредничества
Примечания
Литература
Категория:Инварианты графов Категория:Анализ сетей