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

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

Близость была определена Bavelas (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)}}.}$

Нормализация позволяет сравнивать узлы графов разного размера.

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

В несвязных графиках [ править ]

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

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

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

Эта идея была явно сформулирована для неориентированных графов под названием оцененная центральность Деккером (2005) ^[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)}}}.}.$

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

Если граф создается путем связывания узла графа с узлом графа, то объединенная близость равна:${\ 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));}$

если граф создается путем сворачивания узла графа и узла графа в один узел, то близость равна: ^[12]${\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})+2D(p)D(q).}$

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]