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

Чтобы узнать о статистической концепции, см. Центральную тенденцию .

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

Определение и характеристика индексов центральности

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

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

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

Характеристика по сетевым потокам

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

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

Характеристика по структуре ходьбы

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

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

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

Центральности радиального объема существуют в спектре

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

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

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

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

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

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

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

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

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

Теоретико-игровая центральность

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

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

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

Важные ограничения

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

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

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

Во-вторых, функции, которые (правильно) идентифицируют наиболее важные вершины в данной сети/приложении, не обязательно распространяются на остальные вершины. Для большинства других сетевых узлов ранжирование может быть бессмысленным. Это объясняет, почему, например, только первые несколько результатов поиска изображений Google появляются в разумном порядке. Рейтинг страницы — крайне нестабильный показатель, показывающий частые изменения ранга после небольших корректировок параметра перехода.

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

Степень центральности

Основная статья: Степень (теория графов)

Примеры: A) Центральность по промежуточности , B) Центральность по близости , C) Центральность по собственному вектору , D) Центральность по степени , E) Гармоническая центральность и F) Центральность по Кацу одного и того же случайного геометрического графа.

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

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

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

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

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

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

Соответственно, степень централизации графа $G$ заключается в следующем:

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

Стоимость $H$ максимизируется, когда график $X$ содержит один центральный узел, к которому подключены все остальные узлы ( звездный граф ), и в данном случае

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

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

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

Кроме того, новая обширная глобальная мера централизации степени под названием Tendency to Make Hub (TMH) определяет следующее:

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

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

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

Основная статья: Центральность по близости

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

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

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

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

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

Гармоническая центральность

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

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

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

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

Центральность посредничества

Основная статья: Центральность посредничества

Оттенок (от красного = 0 до синего = максимум) показывает промежуточное положение узла.

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

Между вершиной $v$ в графике $G:=(V,E)$ с $V$ вершин вычисляется следующим образом:

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

Более компактно посредничество можно представить как:

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

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

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

Центральность собственного вектора

Основная статья: Центральность собственного вектора

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

Использование матрицы смежности для определения центральности собственного вектора

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

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

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

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

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

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

Основная статья: Центральность Каца

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

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

где $\alpha$ является фактором ослабления $(0,1)$.

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

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

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

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

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

Основная статья: PageRank

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

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

где

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

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

Центральность перколяции

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

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

$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}}}$

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

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

Межкликовая центральность

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

Централизация Фримена

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

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

это наибольшая сумма разностей центральности точки $C_{x}$ для любого графа с одинаковым количеством узлов централизация сети равна:

$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}))}}.$

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

Меры центральности, основанные на несходстве

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

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

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

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

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

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

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

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

где $n$ — количество узлов в сети. Несколько мер и сетей несходства были протестированы в получение улучшенных результатов в изученных случаях.

См. также

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

Дальнейшее чтение

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