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

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список  / матрица смежности Список  / матрица заболеваемости Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
МетрикиАлгоритмы
Центральность Степень Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия / SIR
СпискиКатегории
Темы Программного обеспечения Сетевые ученые Категория: Теория сетей Категория: Теория графов
v т е

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

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

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

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

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

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

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

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

Характеристика по структуре прогулки [ править ]

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

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

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

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

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

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

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

${\ Displaystyle \ сумма _ {к = 0} ^ {\ infty} A_ {R} ^ {k} \ beta ^ {k}}$

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

${\ displaystyle \ sum _ {к = 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] ) для измерения двустороннего прямого влияния между игроками применяется индекс силы Шепли-Шубика , а не значение Шепли . Распределение действительно является типом центрированности векторов. Он используется для сортировки объектов больших данных в Hu (2020) ^[11], таких как ранжирование колледжей США.

Важные ограничения [ править ]

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

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

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

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

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

Центральная степень [ править ]

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

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

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

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

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

${\ Displaystyle Н = \ сумма _ {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}}}$

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

${\displaystyle TMK={\frac {\sum _{i=1}^{|V|}[deg(v)]^{2}}{\sum _{i=1}^{|V|}deg(v)}}}$

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

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

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

Закрытость была определена Alex Bavelas (1950) в качестве обратной части отдаленности , ^{[20] [21]} , что это:

${\displaystyle C(x)={\frac {1}{\sum _{y}d(y,x)}}}$

где - расстояние между вершинами и . Однако, говоря о центральности по близости, люди обычно ссылаются на ее нормализованную форму, обычно задаваемую предыдущей формулой, умноженной на , где - количество узлов в графе. Эта настройка позволяет сравнивать узлы графов разного размера.${\displaystyle d(y,x)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle N-1}$${\displaystyle N}$

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

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

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

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

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

Harmonic сосредоточенность была предложена Marchiori и Latora (2000) ^[22] , а затем независимо от Dekker (2005), используя имя "значная центральность" ^[23] и Рош (2009). ^[24]

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

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

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

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

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

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

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

Центральность собственного вектора [ править ]

Центральное место собственного вектора (также называемый eigencentrality ) является мерой влияния узла в сети . Он присваивает относительные оценки всем узлам в сети на основе концепции, согласно которой соединения с узлами с высокими оценками вносят больший вклад в оценку рассматриваемого узла, чем равные соединения с узлами с низкими показателями. ^{[27] [6]} Google «s PageRank и сосредоточенность Katz представляют собой варианты собственного вектора центральности. ^[28]

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

Для данного графа с числом вершин пусть будет матрицей смежности , т.е. если вершина связана с вершиной , и в противном случае. Оценка относительной центральности вершины может быть определена как:${\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 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} }$

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

Центральность Каца [ править ]

Центральность Каца ^[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 [ править ]

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), которая конкретно измеряет важность узлов с точки зрения помощи перколяции по сети. Эта мера была предложена Piraveenan et al.^[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}$

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

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

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

Централизация Фримена [ править ]

Централизацией любой сети является мерой того , как центральный его самый центральный узел по отношению к тому, как центральный все остальные узлы. ^[13] Затем меры централизации: (а) вычисляют сумму различий в центральности между самым центральным узлом в сети и всеми другими узлами; и (б) разделить это количество на теоретически наибольшую сумму разностей в любой сети того же размера. ^[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},\,\,\,\,\,\,j=1,\cdots ,n}$

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

Расширения [ править ]

Эмпирические и теоретические исследования расширили понятие центральности в контексте статических сетей до динамической центральности ^[37] в контексте зависящих от времени и темпоральных сетей. ^{[38] [39] [40]}

Для обобщения взвешенных сетей см. Opsahl et al. (2010). ^[41]

Концепция центральности была распространена и на групповой уровень. Например, центральность группового промежуточного звена показывает долю геодезических, соединяющих пары не входящих в группу членов, которые проходят через группу. ^{[42] [43]}

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

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

Примечания и ссылки [ править ]

Дальнейшее чтение [ править ]

• Koschützki, D .; Lehmann, KA; Peeters, L .; Richter, S .; Тенфельде-Подель, Д., Злотовски, О. (2005) Индексы центральности. В Брандес, У. и Эрлебах, Т. (ред.) Сетевой анализ: методологические основы , стр. 16–61, LNCS 3418, Springer-Verlag.