Центральность

Часть серии статей о
Сетевая наука
Теория
График Сложная сеть Заражение Маленький мир Без чешуи Структура сообщества Перколяция Эволюция Управляемость Графическое изображение Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Преимущественное присоединение Теория равновесия Сетевой эффект Социальное влияние
Типы сетей
Информационный (вычислительный) Телекоммуникации Транспорт Социальный Научное сотрудничество Биологический Искусственная нейронная сеть Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Путь Вершина Список смежности  / матрица Список  / матрица случаев Типы Двудольный Полный Направленный Гипер Помечено Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Мотив Кластеризация Распределение степеней Assortativity Distance Modularity Efficiency
Models
Topology Random graph Erdős–Rényi Barabási–Albert Bianconi–Barabási Fitness model Watts–Strogatz Exponential random (ERGM) Random geometric (RGG) Hyperbolic (HGN) Hierarchical Stochastic block Blockmodeling Maximum entropy Soft configuration LFR Benchmark Dynamics Boolean network agent based Epidemic/SIR
Lists Categories
Topics Software Network scientists Category:Network theory Category:Graph theory
v t e

В теории графов и сетевом анализе индикаторы центральности присваивают номера или рейтинги узлам в графе в соответствии с их положением в сети. Приложения включают определение наиболее влиятельных лиц в социальной сети , ключевых узлов инфраструктуры в Интернете или городских сетях , суперраспространителей заболеваний и мозговых сетей. ^{[1] [2]} Концепции центральности были впервые разработаны в анализе социальных сетей , и многие из терминов, используемых для измерения центральности, отражают их социологическое происхождение. ^[3]

Индексы центральности являются ответами на вопрос «Что характеризует важную вершину?» Ответ дается в терминах действительной функции на вершинах графа, где полученные значения, как ожидается, обеспечат ранжирование, которое идентифицирует наиболее важные узлы. ^{[4] [5] [6]}

Слово «важность» имеет широкий спектр значений, что приводит к множеству различных определений центральности. Были предложены две схемы категоризации. «Важность» может быть понята в отношении типа потока или передачи по сети. Это позволяет классифицировать центральности по типу потока, который они считают важным. ^[5] «Важность» может быть альтернативно понята как участие в связности сети. Это позволяет классифицировать центральности на основе того, как они измеряют связность. ^[7] Оба этих подхода делят центральности на отдельные категории. Еще один вывод заключается в том, что центральность, которая подходит для одной категории, часто «ошибается» при применении к другой категории. ^[5]

Многие, хотя и не все, меры центральности эффективно подсчитывают количество путей (также называемых обходами) некоторого типа, проходящих через заданную вершину; меры различаются тем, как определяются и подсчитываются соответствующие обходы. Ограничение рассмотрения этой группой позволяет таксономию, которая помещает многие центральности в спектр от тех, которые связаны с обходами длины один (степенная центральность) до бесконечных обходов (центрированность по собственному вектору). ^{[4] [8]} Другие меры центральности, такие как центральность по промежуточности, фокусируются не только на общей связанности, но и на занимаемых позициях, которые имеют решающее значение для связности сети.

Сеть можно считать описанием путей, по которым что-то течет. Это позволяет характеризовать на основе типа потока и типа пути, закодированного центральностью. Поток может быть основан на передачах, где каждый неделимый элемент идет от одного узла к другому, как посылка, идущая от места доставки к дому клиента. Второй случай - последовательное дублирование, в котором элемент реплицируется так, что он есть и у источника, и у цели. Примером является распространение информации через сплетни, при этом информация распространяется частным образом, и как исходный, так и целевой узлы информируются в конце процесса. Последний случай - параллельное дублирование, при котором элемент дублируется по нескольким ссылкам одновременно, как радиопередача, которая предоставляет одну и ту же информацию многим слушателям одновременно. ^[5]

Аналогично, тип пути может быть ограничен геодезическими (кратчайшие пути), путями (ни одна вершина не посещается более одного раза), тропами (вершины могут посещаться несколько раз, ни одно ребро не пересекается более одного раза) или прогулками (вершины и ребра могут посещаться/пересекаться несколько раз). ^[5]

Альтернативная классификация может быть получена из того, как построена центральность. Она снова разделяется на два класса. Центральности бывают радиальными и медиальными. Радиальные центральности подсчитывают маршруты, которые начинаются/заканчиваются в данной вершине. Центральности степени и собственного значения являются примерами радиальных центральностей, подсчитывая количество маршрутов длины один или бесконечности. Медиальные центральности подсчитывают маршруты, которые проходят через данную вершину. Каноническим примером является центральность Фримена по промежуточности, количество кратчайших путей, которые проходят через данную вершину. ^[7]

Аналогично, подсчет может охватывать либо объем , либо длину прогулок. Объем — это общее количество прогулок заданного типа. Три примера из предыдущего абзаца попадают в эту категорию. Длина охватывает расстояние от заданной вершины до остальных вершин в графе. Центральность по близости, общее геодезическое расстояние от заданной вершины до всех остальных вершин, является наиболее известным примером. ^[7] Обратите внимание, что эта классификация не зависит от типа подсчитанной прогулки (т. е. прогулка, тропа, путь, геодезическая).

Боргатти и Эверетт предполагают, что эта типология дает представление о том, как лучше всего сравнивать меры центральности. Центральности, помещенные в один и тот же ящик в этой классификации 2×2, достаточно похожи, чтобы сделать правдоподобные альтернативы; можно разумно сравнить, что лучше для данного приложения. Однако меры из разных ящиков категорически различны. Любая оценка относительной пригодности может происходить только в контексте предопределения того, какая категория более применима, что делает сравнение спорным. ^[7]

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

Боначич показал, что если ассоциация определяется в терминах обходов , то семейство центральностей может быть определено на основе длины рассматриваемого обхода. ^[4] Степень центральности учитывает обходы длиной один, в то время как центральность по собственному значению учитывает обходы длиной бесконечность. Альтернативные определения ассоциации также разумны. Альфа-центральность позволяет вершинам иметь внешний источник влияния. Подграфовая центральность Эстрады предлагает учитывать только замкнутые пути (треугольники, квадраты и т. д.).

Сердцем таких мер является наблюдение, что степени матрицы смежности графа дают количество обходов длины, заданной этой степенью. Аналогично, экспонента матрицы также тесно связана с количеством обходов заданной длины. Начальное преобразование матрицы смежности позволяет по-другому определить тип подсчитанного обхода. При любом подходе центральность вершины может быть выражена как бесконечная сумма, либо

${\displaystyle \sum _{k=0}^{\infty }A_{R}^{k}\beta ^{k}}$

для матричных степеней или или

${\displaystyle \sum _{k=0}^{\infty }{\frac {(A_{R}\beta )^{k}}{k!}}}$

для матричных экспонент, где

• ${\displaystyle k}$длина прогулки,
• ${\displaystyle A_{R}}$— преобразованная матрица смежности, а
• ${\displaystyle \beta }$— параметр дисконтирования, обеспечивающий сходимость суммы.

Семейство мер Боначича не преобразует матрицу смежности. Альфа-центральность заменяет матрицу смежности ее резольвентой . Подграфовая центральность заменяет матрицу смежности ее следом. Поразительный вывод заключается в том, что независимо от первоначального преобразования матрицы смежности все такие подходы имеют общее предельное поведение. По мере приближения к нулю индексы сходятся к степени центральности. По мере приближения к максимальному значению индексы сходятся к собственному значению центральности. ^[8]${\displaystyle \beta }$${\displaystyle \beta }$

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

Например, рассмотрим задачу остановки эпидемии. Глядя на изображение сети выше, какие узлы следует вакцинировать? Основываясь на ранее описанных мерах, мы хотим распознать узлы, которые являются наиболее важными в распространении болезни. Подходы, основанные только на центральности, которые фокусируются на индивидуальных особенностях узлов, могут быть не очень хорошей идеей. Узлы в красном квадрате по отдельности не могут остановить распространение болезни, но рассматривая их как группу, мы ясно видим, что они могут остановить болезнь, если она началась в узлах , , и . Теоретико-игровые центральности пытаются консультироваться с описанными проблемами и возможностями, используя инструменты из теории игр. Подход, предложенный в ^[9], использует число Шепли . Из-за сложности вычисления числа Шепли по времени большинство усилий в этой области направлено на реализацию новых алгоритмов и методов, которые полагаются на особую топологию сети или особый характер проблемы. Такой подход может привести к снижению сложности по времени с экспоненциальной до полиномиальной.${\displaystyle v_{1}}$${\displaystyle v_{4}}$${\displaystyle v_{5}}$

Аналогично, распределение полномочий концепции решения ( ^[10] ) применяет индекс мощности Шепли-Шубика , а не значение Шепли , для измерения двустороннего прямого влияния между игроками. Распределение действительно является типом центральности собственного вектора. Оно используется для сортировки объектов больших данных в Ху (2020), ^[11], таких как рейтинг колледжей США.

Индексы центральности имеют два важных ограничения, одно очевидное, а другое тонкое. Очевидное ограничение заключается в том, что центральность, которая оптимальна для одного приложения, часто неоптимальна для другого приложения. Действительно, если бы это было не так, нам не нужно было бы так много различных центральностей. Иллюстрацией этого явления служит граф воздушных змеев Кракхардта , для которого три различных понятия центральности дают три различных выбора самой центральной вершины. ^[12]

Более тонким ограничением является распространенное заблуждение, что центральность вершин указывает на относительную важность вершин. Индексы центральности явно предназначены для создания рейтинга, который позволяет указывать на наиболее важные вершины. ^{[4] [5]} С этим они справляются хорошо, при только что отмеченном ограничении. Они не предназначены для измерения влияния узлов в целом. Недавно сетевые физики начали разрабатывать метрики влияния узлов для решения этой проблемы.

Ошибка двоякая. Во-первых, ранжирование только упорядочивает вершины по важности, оно не количественно определяет разницу в важности между различными уровнями ранжирования. Это можно смягчить, применив централизацию Фримена к рассматриваемой мере центральности, что дает некоторое представление о важности узлов в зависимости от различий в их оценках централизации. Кроме того, централизация Фримена позволяет сравнивать несколько сетей, сравнивая их самые высокие оценки централизации. ^[13]

Во-вторых, признаки, которые (правильно) идентифицируют наиболее важные вершины в данной сети/приложении, не обязательно обобщаются на остальные вершины. Для большинства других сетевых узлов рейтинги могут быть бессмысленными. ^{[14] [15] [16] [17]} Это объясняет, почему, например, только первые несколько результатов поиска изображений Google отображаются в разумном порядке. Pagerank — крайне нестабильная мера, показывающая частые смены ранга после небольших корректировок параметра jump. ^[18]

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

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

Степень центральности вершины для данного графа с вершинами и ребрами определяется как${\displaystyle v}$${\displaystyle G:=(V,E)}$${\displaystyle |V|}$${\displaystyle |E|}$

${\displaystyle C_{D}(v)=\deg(v)}$

Вычисление степени центральности для всех узлов графа требует плотного представления матрицы смежности графа, а для ребер — разреженного представления матрицы .${\displaystyle \Theta (V^{2})}$ ${\displaystyle \Theta (E)}$

Определение центральности на уровне узлов можно распространить на весь граф, и в этом случае мы говорим о централизации графа . ^[19] Пусть будет узлом с наивысшей степенью центральности в . Пусть будет -узловым связным графом, который максимизирует следующую величину (при этом будет узлом с наивысшей степенью центральности в ):${\displaystyle v*}$${\displaystyle G}$${\displaystyle X:=(Y,Z)}$${\displaystyle |Y|}$${\displaystyle y*}$${\displaystyle X}$

${\displaystyle H=\sum _{j=1}^{|Y|}[C_{D}(y*)-C_{D}(y_{j})]}$

Соответственно, степень централизации графа следующая:${\displaystyle G}$

${\displaystyle C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})]}{H}}}$

Значение максимизируется, когда граф содержит один центральный узел, с которым соединены все остальные узлы ( звездчатый граф ), и в этом случае${\displaystyle H}$${\displaystyle X}$

${\displaystyle H=(n-1)\cdot ((n-1)-1)=n^{2}-3n+2.}$

Итак, для любого графика${\displaystyle G:=(V,E),}$

${\displaystyle C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})]}{|V|^{2}-3|V|+2}}}$

Кроме того, новая обширная глобальная мера степени центральности под названием «Склонность к созданию центра» (TMH) определяется следующим образом: ^[2]

${\displaystyle {\text{TMH}}={\frac {\sum _{i=1}^{|V|}\deg(v)^{2}}{\sum _{i=1}^{|V|}\deg(v)}}}$

где TMH увеличивается с появлением степени центральности в сети.

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

Близость была определена Алексом Бавеласом (1950) как обратная величина удаленности , [ ^{20] [21]} то есть где — расстояние между вершинами u и v . Однако, говоря о центральности близости, люди обычно имеют в виду ее нормализованную форму, заданную предыдущей формулой, умноженной на , где — число узлов в графе${\textstyle C_{B}(v)=(\sum _{u}d(u,v))^{-1}}$${\displaystyle d(u,v)}$${\displaystyle N-1}$${\displaystyle N}$

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

Эта нормализация позволяет проводить сравнения между узлами графов разных размеров. Для многих графов существует сильная корреляция между обратной величиной близости и логарифмом степени, ^[22] где — степень вершины v, а α и β — константы для каждой сети.${\displaystyle (C(v))^{-1}\approx -\alpha \ln(k_{v})+\beta }$${\displaystyle k_{v}}$

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

В (не обязательно связном) графе гармоническая центральность меняет местами сумму и обратные операции в определении центральности близости:

${\displaystyle H(v)=\sum _{u|u\neq v}{\frac {1}{d(u,v)}}}$

где если нет пути от u до v . Гармоническую центральность можно нормализовать, разделив на , где — количество узлов в графе.${\displaystyle 1/d(u,v)=0}$${\displaystyle N-1}$${\displaystyle N}$

Гармоническая центральность была предложена Марчиори и Латорой (2000) ^[23] , а затем независимо Деккером (2005), использовавшим название «ценностная центральность» ^[24] , и Роша (2009). ^[25]

Посредническая ценность — это мера центральности вершины в графе ( существует также посредническая ценность ребер , которая здесь не обсуждается). Посредническая ценность количественно определяет количество раз, когда узел действует как мост на кратчайшем пути между двумя другими узлами. Она была введена как мера для количественной оценки контроля человека над коммуникацией между другими людьми в социальной сети Линтоном Фрименом . ^[26] В его концепции вершины, которые имеют высокую вероятность появления на случайно выбранном кратчайшем пути между двумя случайно выбранными вершинами, имеют высокую посредническую ценность.

Промежуточность вершины в графе с вершинами вычисляется следующим образом:${\displaystyle v}$${\displaystyle G:=(V,E)}$${\displaystyle V}$

1. Для каждой пары вершин ( s , t ) вычислите кратчайшие пути между ними.
2. Для каждой пары вершин ( s , t ) определите долю кратчайших путей, проходящих через рассматриваемую вершину (в данном случае вершину v ).
3. Просуммируйте эту дробь по всем парам вершин ( s , t ).

Более компактно промежуточность можно представить как: ^[27]

${\displaystyle C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

где — общее число кратчайших путей от узла до узла , а — число тех путей, которые проходят через . Промежуточность может быть нормализована путем деления на число пар вершин, не включая v , что для ориентированных графов равно , а для неориентированных графов равно . Например, в неориентированном звездном графе центральная вершина (которая содержится в каждом возможном кратчайшем пути) будет иметь промежуточность (1, если нормализована), в то время как листья (которые не содержатся ни в одном кратчайшем пути) будут иметь промежуточность 0.${\displaystyle \sigma _{st}}$${\displaystyle s}$${\displaystyle t}$${\displaystyle \sigma _{st}(v)}$${\displaystyle v}$${\displaystyle (n-1)(n-2)}$${\displaystyle (n-1)(n-2)/2}$${\displaystyle (n-1)(n-2)/2}$

С точки зрения вычислений, как центральность по промежуточности, так и центральность по близости всех вершин в графе включают вычисление кратчайших путей между всеми парами вершин на графе, что требует времени с алгоритмом Флойда-Уоршелла . Однако на разреженных графах алгоритм Джонсона может быть более эффективным, требуя времени. В случае невзвешенных графов вычисления могут быть выполнены с помощью алгоритма Брандеса ^[27], который требует времени. Обычно эти алгоритмы предполагают, что графы неориентированные и связаны с учетом петель и множественных ребер. Когда речь идет о сетевых графах, часто графы не имеют петель или множественных ребер для поддержания простых отношений (где ребра представляют связи между двумя людьми или вершинами). В этом случае использование алгоритма Брандеса разделит окончательные баллы центральности на 2, чтобы учесть, что каждый кратчайший путь учитывается дважды. ^[27]${\displaystyle O(V^{3})}$${\displaystyle O(|V||E|+|V|^{2}\log |V|)}$${\displaystyle O(|V||E|)}$

Центральность собственного вектора (также называемая собственной центральностью ) — это мера влияния узла в сети . Она присваивает относительные баллы всем узлам в сети на основе концепции, что связи с узлами с высокой оценкой вносят больший вклад в оценку рассматриваемого узла, чем равные связи с узлами с низкой оценкой. ^[28] [ ^6] PageRank Google и центральность Каца являются вариантами центральности собственного вектора. ^[29]

Для заданного графа с числом вершин пусть будет матрицей смежности , т.е. если вершина связана с вершиной , и в противном случае. Относительная оценка центральности вершины может быть определена как неотрицательное решение по множеству вершин уравнений:${\displaystyle G:=(V,E)}$${\displaystyle |V|}$${\displaystyle A=(a_{v,t})}$${\displaystyle a_{v,t}=1}$${\displaystyle v}$${\displaystyle t}$${\displaystyle a_{v,t}=0}$${\displaystyle x_{v}}$${\displaystyle v}$${\displaystyle v\in V}$

${\displaystyle x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _{t\in G}a_{v,t}x_{t}}$

где — набор соседей и — константа. С небольшой перестановкой это можно переписать в векторной записи как уравнение собственного вектора${\displaystyle M(v)}$${\displaystyle v}$${\displaystyle \lambda }$

${\displaystyle \mathbf {Ax} ={\lambda }\mathbf {x} }$.

В общем случае будет много различных собственных значений , для которых существует ненулевое решение собственного вектора. Поскольку элементы матрицы смежности неотрицательны, существует единственное наибольшее собственное значение, которое является действительным и положительным, согласно теореме Перрона–Фробениуса . Это наибольшее собственное значение приводит к желаемой мере центральности. ^[28] Компонента соответствующего собственного вектора затем дает относительную оценку центральности вершины в сети. Собственный вектор определяется только с точностью до общего множителя, поэтому хорошо определены только отношения центральностей вершин. Чтобы определить абсолютную оценку, необходимо нормализовать собственный вектор, например, так, чтобы сумма по всем вершинам равнялась 1 или общему числу вершин n . Итерация мощности является одним из многих алгоритмов собственных значений , которые можно использовать для нахождения этого доминирующего собственного вектора. ^[29] Более того, это можно обобщить так, что записи в A могут быть действительными числами, представляющими силу связи, как в стохастической матрице .${\displaystyle \lambda }$${\displaystyle v^{th}}$${\displaystyle v}$

Центральность по Кацу ^[30] является обобщением степени центральности. Степень центральности измеряет количество непосредственных соседей, а центральность по Кацу измеряет количество всех узлов, которые могут быть соединены через путь, в то время как вклады удаленных узлов штрафуются. Математически это определяется как

${\displaystyle x_{i}=\sum _{k=1}^{\infty }\sum _{j=1}^{N}\alpha ^{k}(A^{k})_{ji}}$

где - коэффициент затухания в .${\displaystyle \alpha }$${\displaystyle (0,1)}$

Центральность по Кацу можно рассматривать как вариант центральности по собственному вектору. Другая форма центральности по Кацу —

${\displaystyle x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).}$

По сравнению с выражением центральности собственного вектора, заменяется на ${\displaystyle x_{j}}$${\displaystyle x_{j}+1.}$

Показано ^[31] , что главный собственный вектор (связанный с наибольшим собственным значением матрицы смежности) является пределом центральности Каца при приближении снизу.${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle {\tfrac {1}{\lambda }}}$

PageRank удовлетворяет следующему уравнению

${\displaystyle x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},}$

где

${\displaystyle L(j)=\sum _{i}a_{ji}}$

— это число соседей узла (или число исходящих ссылок в направленном графе). По сравнению с центральностью по собственному вектору и центральностью по Кацу, одним из основных отличий является масштабный коэффициент . Другое отличие между PageRank и центральностью по собственному вектору заключается в том, что вектор PageRank является левым собственным вектором (обратите внимание, что у коэффициента индексы перевернуты). ^[32]${\displaystyle j}$${\displaystyle L(j)}$${\displaystyle a_{ji}}$

Существует множество мер центральности для определения «важности» отдельного узла в сложной сети. Однако эти меры количественно определяют важность узла в чисто топологических терминах, и значение узла никак не зависит от «состояния» узла. Оно остается постоянным независимо от динамики сети. Это верно даже для взвешенных мер промежуточности. Однако узел вполне может быть расположен в центре с точки зрения промежуточности центральности или другой меры центральности, но может не быть «центрально» расположенным в контексте сети, в которой есть просачивание. Просачивание «заражения» происходит в сложных сетях в ряде сценариев. Например, вирусная или бактериальная инфекция может распространяться по социальным сетям людей, известным как контактные сети. Распространение болезни также можно рассматривать на более высоком уровне абстракции, рассматривая сеть городов или населенных пунктов, соединенных автомобильным, железнодорожным или воздушным сообщением. Компьютерные вирусы могут распространяться по компьютерным сетям. Слухи или новости о деловых предложениях и сделках также могут распространяться через социальные сети людей. Во всех этих сценариях «инфекция» распространяется по связям сложной сети, изменяя «состояния» узлов по мере своего распространения, как восстанавливаемые, так и нет. Например, в эпидемиологическом сценарии люди переходят из «восприимчивого» в «заражённое» состояние по мере распространения инфекции. Состояния, которые могут принимать отдельные узлы в приведенных выше примерах, могут быть бинарными (например, получил/не получил новость), дискретными (восприимчив/заражён/выздоровел) или даже непрерывными (например, доля инфицированных людей в городе) по мере распространения инфекции. Общей чертой во всех этих сценариях является то, что распространение инфекции приводит к изменению состояний узлов в сетях. С учётом этого была предложена центральность перколяции (PC), которая специально измеряет важность узлов с точки зрения содействия просачиванию через сеть. Эта мера была предложена Пиравенаном и др. ^[33]

Центральность перколяции определяется для данного узла в данный момент времени как доля «просачиваемых путей», проходящих через этот узел. «Просачиваемый путь» — это кратчайший путь между парой узлов, где исходный узел просачивается (например, заражен). Целевой узел может быть просачиваемым или непросачиваемым, или находиться в частично просачивающемся состоянии.

${\displaystyle PC^{t}(v)={\frac {1}{N-2}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}}{\frac {{x^{t}}_{s}}{{\sum {[{x^{t}}_{i}}]}-{x^{t}}_{v}}}}$

где — общее количество кратчайших путей от узла к узлу , а — количество тех путей, которые проходят через . Состояние перколяции узла в момент времени обозначается как и два особых случая: когда , что указывает на неперколированное состояние в момент времени, тогда как когда , что указывает на полностью перколированное состояние в момент времени . Значения между ними указывают на частично перколированные состояния (например, в сети поселков это будет процент людей, инфицированных в этом городе).${\displaystyle \sigma _{sr}}$${\displaystyle s}$${\displaystyle r}$${\displaystyle \sigma _{sr}(v)}$${\displaystyle v}$${\displaystyle i}$${\displaystyle t}$${\displaystyle {x^{t}}_{i}}$${\displaystyle {x^{t}}_{i}=0}$${\displaystyle t}$${\displaystyle {x^{t}}_{i}=1}$${\displaystyle t}$

Прикрепленные веса к путям перколяции зависят от уровней перколяции, назначенных исходным узлам, исходя из предпосылки, что чем выше уровень перколяции исходного узла, тем важнее пути, исходящие из этого узла. Узлы, которые лежат на кратчайших путях, исходящих из высокоперколированных узлов, поэтому потенциально более важны для перколяции. Определение PC также может быть расширено, чтобы включить также веса целевых узлов. Расчеты центральности перколяции выполняются во времени с эффективной реализацией, принятой из быстрого алгоритма Брандеса, и если расчет должен учитывать веса целевых узлов, то худшее время составляет .${\displaystyle O(NM)}$${\displaystyle O(N^{3})}$

Кросс-кликовая центральность одного узла в сложном графе определяет связность узла с различными кликами . Узел с высокой кросс-кликовой связностью облегчает распространение информации или болезни в графе. Клики — это подграфы, в которых каждый узел соединен с каждым другим узлом в клике. Кросс-кликовая связность узла для данного графа с вершинами и ребрами определяется как , где — количество клик, к которым принадлежит вершина. Эта мера была использована Фагани в 2013 году ^[34], но впервые была предложена Эвереттом и Боргатти в 1998 году, где они назвали ее клико-перекрывающейся центральностью.${\displaystyle v}$${\displaystyle G:=(V,E)}$${\displaystyle |V|}$${\displaystyle |E|}$${\displaystyle X(v)}$${\displaystyle X(v)}$${\displaystyle v}$

Централизация любой сети является мерой того, насколько ее самый центральный узел является центральным по отношению к тому, насколько центральными являются все остальные узлы. ^{[13] Затем меры} централизации (a) вычисляют сумму разностей в центральности между самым центральным узлом в сети и всеми остальными узлами; и (b) делят эту величину на теоретически наибольшую такую ​​сумму разностей в любой сети того же размера. ^[13] Таким образом, каждая мера центральности может иметь свою собственную меру централизации. Определено формально, если — любая мера центральности точки , если — наибольшая такая мера в сети, и если:${\displaystyle C_{x}(p_{i})}$${\displaystyle i}$${\displaystyle C_{x}(p_{*})}$

${\displaystyle \max \sum _{i=1}^{N}(C_{x}(p_{*})-C_{x}(p_{i}))}$

представляет собой наибольшую сумму разностей в центральности точек для любого графа с тем же числом узлов, тогда централизация сети равна: ^[13]${\displaystyle C_{x}}$

${\displaystyle C_{x}={\frac {\sum _{i=1}^{N}(C_{x}(p_{*})-C_{x}(p_{i}))}{\max \sum _{i=1}^{N}(C_{x}(p_{*})-C_{x}(p_{i}))}}.}$

Идея принадлежит Линтону Фримену .

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

${\displaystyle W\mathbf {c} =\lambda \mathbf {c} }$

где (произведение координат на координату) и является произвольной матрицей несходства , определяемой через меру несходства, например, несходство Жаккара , заданное как${\displaystyle W_{ij}=A_{ij}D_{ij}}$${\displaystyle D_{ij}}$

${\displaystyle D_{ij}=1-{\dfrac {|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|}}}$

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

Примечательно, что неотрицательно, поскольку и являются неотрицательными матрицами, поэтому мы можем использовать теорему Перрона–Фробениуса, чтобы гарантировать, что указанная выше задача имеет единственное решение для λ  =  λ _max с неотрицательным c , что позволяет нам вывести центральность каждого узла в сети. Следовательно, центральность i-го узла равна${\displaystyle W}$${\displaystyle A}$${\displaystyle D}$

${\displaystyle c_{i}={\dfrac {1}{n}}\sum _{j=1}^{n}W_{ij}c_{j},\,\,\,\,\,\,i=1,\cdots ,n}$

где - количество узлов в сети. Несколько мер различия и сетей были протестированы в ^[36], получив улучшенные результаты в изученных случаях.${\displaystyle n}$

Транспортные сети, такие как дорожные сети и железнодорожные сети, широко изучаются в транспортной науке и городском планировании. Ряд недавних исследований были сосредоточены на использовании мер центральности для анализа транспортных сетей. Хотя многие из этих исследований просто используют общие меры центральности, такие как Betweenness Centrality, также были определены специальные меры центральности для анализа транспортных сетей. Среди них выделяется Transportation Centrality . ^[37]

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

Транспортная центральность данного узла v определяется как: ^[37]

${\displaystyle TC(v)=1/((N-1)(N-2))\Sigma _{s\neq v\neq t}{\frac {\Sigma _{i\in P_{s,t}^{v}}e^{-\beta C_{s,t}^{i}}}{\Sigma _{j\in P_{s,t}^{v}}e^{-\beta C_{s,t}^{j}}}}}$

• Альфа-центральность
• Структура ядро-периферия
• Расстояние в графиках

• Кошюцки, Д.; Леманн, КА; Питерс, Л.; Рихтер, С.; Тенфельде-Подель, Д. и Злотовски, О. (2005) Индексы центральности. В Брандес, У. и Эрлебах, Т. (ред.) Сетевой анализ: методологические основы , стр. 16–61, LNCS 3418, Springer-Verlag.