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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, рассмотрим задачу остановки эпидемии. Просматривая вышеприведённое изображение сети, какие узлы следует вакцинировать? Опираясь на описанные выше меры, мы хотим распознать узлы, которые наиболее важны в распространении болезни. Использование подходов, основанных только на центральностях, которые фокусируются на индивидуальных свойствах узлов, может не быть хорошей идеей. Узлы в красном прямоугольнике по отдельности не могут остановить распространение болезни, но при рассмотрении их как группы мы ясно видим, что они могут остановить болезнь, если она начинается в узлах ,,. Теоретико-игровые центральности пытаются принять во внимание описанные проблемы и возможности, используя средства теории игр. Подход, предложенный в статье Михаляка (с соавторами), использует вектор Шепли. Ввиду сложности вычисления (по времени) вектора Шепли бо́льшая часть усилий в этой области вкладывается в разработку новых алгоритмов и методов, которые опираются на конкретную топологию сети и специальный характер задачи. Такой подход может сократить временну́ю сложность алгоритма с экспоненциальной до полиномиальной.

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

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

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

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

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

Степень связности

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

Степень связности вершины для данного графа с вершинами и рёбрами, определяется как

Вычисление степени связности для всех узлов в графе занимает время в представлении графа в виде плотной матрицы смежности, а для рёбер занимает время в представлении с разреженной матрицей.