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

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

• 1 Определение и характеристика индексов центральности
  • 1.1 Характеристика сетевыми потоками
  • 1.2 Характеристика структурой обхода
  • 1.3 Централизованность радиального объема существует на спектре
  • 1.4 Центральность в теории игр
• 2 Важные ограничения
• 3 Центральность по степени
• 4 Центральность по близости
  • 4.1 Гармоническая центральность
• 5 Центральность по промежуточности
• 6 Центральность по собственному вектору
  • 6.1 Использование матрицы смежности для определения центральности собственного вектора <360
  • 15 Примечания и ссылки
  • 16 Дополнительная литература
  Определение и характеристика индексов центральности

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

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

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

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

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

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

  Характеристика структурой обхода

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

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

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

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

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

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

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

  $\sum \; k\; =\; 0\; \infty \; AR\; k\; \beta \; k\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{\backslash \; infty\}\; A\_\; \{R\}\; ^\; \{k\}\; \backslash \; beta\; ^\; \{k\}\}$

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

  $\sum \; k\; =\; 0\; \infty \; (AR\; \beta )\; kk!\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \{\backslash \; frac\; \{(A\_\; \{R\}\; \backslash \; beta)\; ^\; \{k\}\}\; \{k!\}\}\}$

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

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

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

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

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

  

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

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

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

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

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

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

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

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

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

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

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

  $CD\; (v)\; =\; deg\; \; (v)\; \{\backslash \; displaystyle\; C\_\; \{D\}\; (v)\; =\; \backslash \; deg\; (v)\}$

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

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

  $H\; =\; \sum \; j\; =\; 1\; |\; Y\; |\; [CD\; (y\; *)\; -\; CD\; (yj)]\; \{\backslash \; displaystyle\; H\; =\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{|\; Y\; |\}\; [C\_\; \{D\}\; (y\; *)\; -\; C\_\; \{D\}\; (y\_\; \{j\}))]\}$

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

  $CD\; (G)\; =\; \sum \; i\; =\; 1\; |\; V\; |\; [CD\; (v\; *)\; -\; CD\; (vi)]\; H\; \{\backslash \; displaystyle\; C\_\; \{D\}\; (G)\; =\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{|\; V\; |\}\; [C\_\; \{D\}\; (v\; *)\; -C\_\; \{D\}\; (v\_\; \{i\})]\}\; \{H\}\}\}$

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

  $H\; =\; (n\; -\; 1)\; \cdot \; ((\; n\; -\; 1)\; -\; 1)\; знак\; равно\; n\; 2\; -\; 3\; n\; +\; 2.\; \{\backslash \; displaystyle\; H\; =\; (n-1)\; \backslash \; cdot\; ((n-1)\; -1)\; =\; n\; ^\; \{2\}\; -3n\; +\; 2.\}$

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

  $CD\; (G)\; =\; \sum \; i\; =\; 1\; |\; V\; |\; [C\; D\; (v\; \ast )\; -\; C\; D\; (v\; i)]\; |\; V\; |\; 2\; -\; 3\; |\; V\; |\; +\; 2\; \{\backslash \; displaystyle\; C\_\; \{D\}\; (G)\; =\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{|\; V\; |\}\; [C\_\; \{D\}\; (v\; *)\; -\; C\_\; \{D\}\; (v\_\; \{i\}))]\}\; \{|\; V\; |\; ^\; \{2\}\; -3\; |\; V\; |\; +2\}\}\}$

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

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

  Близость была определена Алексом Бавеласом (1950) как , обратная удаленности, то есть:

  $C\; (x)\; Знак\; равно\; 1\; \sum \; yd\; (y,\; x)\; \{\backslash \; displaystyle\; C\; (x)\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sum\; \_\; \{y\}\; d\; (y,\; x)\}\}\}$

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

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

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

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

  $H\; (\; Икс)\; знак\; равно\; \sum \; Y\; \ne \; Икс\; 1\; d\; (Y,\; Икс)\; \{\backslash \; Displaystyle\; H\; (x)\; =\; \backslash \; sum\; \_\; \{y\; \backslash \; neq\; x\}\; \{\backslash \; frac\; \{1\}\; \{d\; (y,\; x)\}\}\}$

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

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

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

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

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

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

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

  $CB\; (v)\; =\; \sum \; s\; \ne \; v\; \ne \; t\; \in \; V\; \sigma \; st\; (v)\; \sigma \; st\; \{\; \backslash \; Displaystyle\; C\_\; \{B\}\; (v)\; =\; \backslash \; sum\; \_\; \{s\; \backslash \; neq\; v\; \backslash \; neq\; t\; \backslash \; in\; V\}\; \{\backslash \; frac\; \{\backslash \; sigma\; \_\; \{st\}\; (v)\}\; \{\backslash \; sigma\; \_\; \{st\}\}\}\}$

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

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

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

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

  Использование функций для определения центральности собственного вектора

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

  $xv\; =\; 1\; \lambda \; \sum \; t\; \in \; M\; (v)\; xt\; =\; 1\; \lambda \; \sum \; t\; \in \; G\; av,\; txt\; \{\backslash \; displaystyle\; x\_\; \{v\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; lambda\}\}\; \backslash \; sum\; \_\; \{t\; \backslash \; in\; M\; (v)\}\; x\_\; \{t\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; lambda\}\}\; \backslash \; sum\; \_\; \{t\; \backslash \; in\; G\}\; a\_\; \{v,\; t\}\; x\_\; \{t\}\}$

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

  $A\; x\; =\; \lambda \; x\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Ax\}\; =\; \{\backslash \; lambda\}\; \backslash \; mathbf\; \{x\}\}$

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

  Центральная Каца

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

  $xi\; =\; \sum \; k\; =\; 1\; \infty \; \sum \; j\; =\; 1\; N\; \alpha \; k\; (A\; k)\; ji\; \{\backslash \; displaystyle\; x\_\; \{i\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{\backslash \; infty\}\; \backslash \; amount\; \_\; \{j\; =\; 1\}\; ^\; \{N\}\; \backslash \; alpha\; ^\; \{k\}\; (A\; ^\; \{k\})\; \_\; \{ji\}\}$

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

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

  $x\; i\; =\; \alpha \; \sum \; j\; =\; 1\; N\; a\; i\; j\; (x\; j\; +\; 1).\; \{\backslash \; displaystyle\; x\_\; \{i\}\; =\; \backslash \; alpha\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{N\}\; a\_\; \{ij\}\; (x\_\; \{j\}\; +1).\}$

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

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

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

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

  $xi\; =\; \alpha \; \sum \; jajixj\; L\; (j)\; +\; 1\; -\; \alpha \; N,\; \{\backslash \; displaystyle\; x\_\; \{i\}\; =\; \backslash \; alpha\; \backslash \; sum\; \_\; \{j\}\; a\_\; \{ji\}\; \{\backslash \; frac\; \{x\_\; \{j\}\}\; \{L\; (j)\}\}\; +\; \{\backslash \; frac\; \{1-\; \backslash \; alpha\}\; \{N\}\},\}$

  где

  $L\; (\; j)\; =\; \sum \; iaji\; \{\backslash \; displaystyle\; L\; (j)\; =\; \backslash \; sum\; \_\; \{i\}\; a\_\; \{ji\}\}$

  - количество соседей узла $j\; \{\backslash \; displaystyle\; j\}$(или количество исходящих ссылок в ориентированном графе). Один из основных отличий коэффициент масштабирования $L\; (j)\; \{\backslash \; displaystyle\; L\; (j)\}$. Другое различие между PageRank и центральностью собственного вектора заключается в том, что вектор PageRank является левым собственным вектором (обратите внимание, что коэффициент $aji\; \{\backslash \; displaystyle\; a\_\; \{ji\}\}$имеет обратные индексы).

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

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

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

  $ПК\; t\; (v)\; =\; 1\; N\; -\; 2\; \sum \; s\; \ne \; v\; \ne \; r\; \sigma \; sr\; (v)\; \sigma \; srxts\; \sum \; [xti]\; -\; xtv\; \{\backslash \; displaystyle\; PC\; ^\; \{t\}\; (v)\; =\; \{\backslash \; frac\; \{1\}\; \{N-2\}\}\; \backslash \; sum\; \_\; \{s\; \backslash \; neq\; v\; \backslash \; neq\; r\}\; \{\backslash \; frac\; \{\backslash \; sigma\; \_\; \{sr\}\; (v)\}\; \{\backslash \; sigma\; \_\; \{sr\}\}\}\; \{\backslash \; frac\; \{\{x\; ^\; \{t\; \}\}\; \_\; \{s\}\}\; \{\{\backslash \; sum\; \{[\{x\; ^\; \{t\}\}\; \_\; \{i\}\}]\}\; -\; \{x\; ^\; \{t\}\}\; \_\; \{v\}\}\}\}$

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

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

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

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

  Централизация Freeman

  централизация любой сети является мерой того, насколько центральным является ее самый центральный узел по отношению к тому, насколько центральными являются все остальные узлы. Затем меры централизации: (а) вычисляют сумму различий в центральности между самым центральным узлом в сети и всеми другими узлами; и (б) разделить это количество на теоретически наибольшую сумму разностей в любой сети того же размера. Таким образом, каждая мера центральности может иметь свою меру централизации. Определен формально, если $C\; x\; (pi)\; \{\backslash \; displaystyle\; C\_\; \{x\}\; (p\_\; \{i\})\}$- любая мера центральности точки $i\; \{\backslash \; displaystyle\; i\}$, если $C\; x\; (p\; \ast )\; \{\backslash \; displaystyle\; C\_\; \{x\}\; (p\; \_\; \{*\})\}$является наибольшим таким показателем в сети, и если:

  $max\; \sum \; я\; знак\; равно\; 1\; NC\; x\; (p\; *)\; -\; C\; x\; (pi)\; \{\backslash \; displaystyle\; \backslash \; max\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; C\_\; \{x\}\; (p\; \_\; \{*\})\; -\; C\_\; \{x\}\; (p\_\; \{i\})\}$

  - наибольшая сумма различий в центральности точек $C\; x\; \{\backslash \; displaystyle\; C\_\; \{x\}\}$для любого графа с одинаковым количеством узлов, тогда централизация сеть выглядит так:

  $C\; x\; =\; \sum \; i\; =\; 1\; NC\; x\; (p\; \ast )\; -\; C\; x\; (pi)\; max\; \sum \; i\; =\; 1\; NC\; x\; (p\; \ast )\; -\; C\; x\; (pi).\; \{\backslash \; displaystyle\; C\_\; \{x\}\; =\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; C\_\; \{x\}\; (p\; \_\; \{*\})\; -\; C\_\; \{x\}\; (p\_\; \{i\})\}\; \{\backslash \; max\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; C\_\; \{x\}\; (p\; \_\; \{*\})\; -\; C\_\; \{x\}\; (p\_\; \{i\})\}\}.\}$

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

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

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

  где $W\; ij\; =\; A\; ij\; D\; ij\; \{\backslash \; displaystyle\; W\_\; \{ij\}\; =\; A\_\; \{ij\}\; D\_\; \{ij\}\}$(произведение "координаты-координаты") и $D\; ij\; \{\backslash \; displaystyle\; D\_\; \{ij\}\}$- произвольная матрица несходства, определенная с помощью несимметричного показателя, например, Jaccard несходство, заданное

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

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

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

  $ci\; =\; 1\; n\; \sum \; j\; =\; 1\; n\; W\; ijcj,\; j\; =\; 1,\; \cdots ,\; n\; \{\backslash \; displaystyle\; c\_\; \{i\}\; =\; \{\backslash \; dfrac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{n\}\; W\_\; \{ij\}\; c\_\; \{j\},\; \backslash ,\; \backslash ,\; \backslash ,\; \backslash ,\; \backslash ,\; \backslash ,\; j\; =\; 1,\; \backslash \; cdots,\; n\}$

  где $n\; \{\backslash \; displaystyle\; n\}$- количество узлов в сети. Было протестировано несколько мер и сетей несходства для получения улучшенных результатов в изученных случаях.

  Расширения

  Эмпирические и теоретические концепции исследования расширили центральных сетей в контексте статических сетей до динамической среды временных центральных сетей.

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

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

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