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

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

В теории графов центральность по Кацу или альфа-центральность узла является мерой центральности в сети . Она была введена Лео Кацем в 1953 году и используется для измерения относительной степени влияния субъекта (или узла) в социальной сети . ^[1] В отличие от типичных мер центральности, которые рассматривают только кратчайший путь ( геодезический ) между парой субъектов, центральность по Кацу измеряет влияние, принимая во внимание общее количество переходов между парой субъектов. ^[2]

Он похож на PageRank Google и центральность собственного вектора . ^[3]

Центральность Катца вычисляет относительное влияние узла в сети, измеряя количество непосредственных соседей (узлы первой степени), а также всех других узлов в сети, которые подключаются к рассматриваемому узлу через этих непосредственных соседей. Однако соединения, установленные с удаленными соседями, штрафуются коэффициентом затухания . ^[4] Каждому пути или соединению между парой узлов назначается вес, определяемый и расстоянием между узлами как .${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha ^{d}}$

Например, на рисунке справа предположим, что измеряется центральность Джона и что . Вес, назначенный каждой связи, которая соединяет Джона с его непосредственными соседями Джейн и Бобом, будет . Поскольку Хосе соединяется с Джоном косвенно через Боба, вес, назначенный этой связи (состоящей из двух связей), будет . Аналогично вес, назначенный связи между Агнетой и Джоном через Азиза и Джейн, будет , а вес, назначенный связи между Агнетой и Джоном через Диего, Хосе и Боба, будет .${\displaystyle \alpha =0.5}$${\displaystyle (0.5)^{1}=0.5}$${\displaystyle (0.5)^{2}=0.25}$${\displaystyle (0.5)^{3}=0.125}$${\displaystyle (0.5)^{4}=0.0625}$

Пусть A — матрица смежности рассматриваемой сети. Элементы A — это переменные, которые принимают значение 1, если узел i соединен с узлом j , и 0 в противном случае. Степени A указывают на наличие (или отсутствие) связей между двумя узлами через посредников. Например, в матрице , если элемент , это указывает на то, что узел 2 и узел 12 соединены некоторым путем длины 3. Если обозначает центральность по Кацу узла  i , то, учитывая значение , математически:${\displaystyle (a_{ij})}$${\displaystyle A^{3}}$${\displaystyle (a_{2,12})=1}$${\displaystyle C_{\mathrm {Katz} }(i)}$${\displaystyle \alpha \in (0,1)}$

${\displaystyle C_{\mathrm {Katz} }(i)=\sum _{k=1}^{\infty }\sum _{j=1}^{n}\alpha ^{k}(A^{k})_{ji}}$

Обратите внимание, что приведенное выше определение использует тот факт, что элемент в месте расположения отражает общее число связей степени между узлами и . Значение коэффициента затухания должно быть выбрано таким образом, чтобы оно было меньше, чем обратная величина абсолютного значения наибольшего собственного значения A . [ ^5] В этом случае для вычисления центральности Катца можно использовать следующее выражение:${\displaystyle (i,j)}$${\displaystyle A^{k}}$${\displaystyle k}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \alpha }$

${\displaystyle {\overrightarrow {C}}_{\mathrm {Katz} }=((I-\alpha A^{T})^{-1}-I){\overrightarrow {I}}}$

Здесь — единичная матрица, — вектор размера n ( n — число узлов), состоящий из единиц. обозначает транспонированную матрицу A, а обозначает инверсию матрицы члена . ^[5]${\displaystyle I}$${\displaystyle {\overrightarrow {I}}}$${\displaystyle A^{T}}$${\displaystyle (I-\alpha A^{T})^{-1}}$${\displaystyle (I-\alpha A^{T})}$

Расширение этой структуры позволяет вычислять обходы в динамической обстановке. ^{[6] [7]} Принимая зависящую от времени серию снимков смежности сети переходных ребер, представлена ​​зависимость обходов от вклада в кумулятивный эффект. Стрела времени сохраняется, так что вклад активности асимметричен в направлении распространения информации.

Сеть, производящая данные в форме:

${\displaystyle \left\{A^{[k]}\in \mathbb {R} ^{N\times N}\right\}\qquad {\text{for}}\quad k=0,1,2,\ldots ,M,}$

представляющая матрицу смежности в каждый момент времени . Следовательно:${\displaystyle t_{k}}$

${\displaystyle \left(A^{[k]}\right)_{ij}={\begin{cases}1&{\text{there is an edge from node }}i{\text{ to node }}j{\text{ at time }}t_{k}\\0&{\text{otherwise}}\end{cases}}}$

Временные точки упорядочены, но не обязательно равномерно распределены. для которого есть взвешенный подсчет числа динамических обходов длины от узла к узлу . Форма для динамической коммуникабельности между участвующими узлами:${\displaystyle t_{0}<t_{1}<\cdots <t_{M}}$${\displaystyle Q\in \mathbb {R} ^{N\times N}}$${\displaystyle (Q)_{ij}}$${\displaystyle w}$${\displaystyle i}$${\displaystyle j}$

${\displaystyle {\mathcal {Q}}=\left(I-\alpha A^{[0]}\right)^{-1}\cdots \left(I-\alpha A^{[M]}\right)^{-1}.}$

Это можно нормализовать с помощью:

${\displaystyle {\hat {\mathcal {Q}}}^{[k]}={\frac {{\hat {\mathcal {Q}}}^{[k-1]}\left(I-\alpha A^{[k]}\right)^{-1}}{\left\|{\hat {\mathcal {Q}}}^{[k-1]}\left(I-\alpha A^{[k]}\right)^{-1}\right\|}}.}$

Таким образом, меры центральности, которые количественно определяют, насколько эффективно узел может «транслировать» и «принимать» динамические сообщения по сети:${\displaystyle n}$

${\displaystyle C_{n}^{\mathrm {broadcast} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{nk}\quad \mathrm {and} \quad C_{n}^{\mathrm {receive} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{kn}}$.

Для графа с матрицей смежности центральность по Кацу определяется следующим образом:${\displaystyle A_{i,j}}$

${\displaystyle {\vec {x}}=(I-\alpha A^{T})^{-1}{\vec {e}}-{\vec {e}}\,}$

где — внешняя важность, придаваемая узлу , а — неотрицательный коэффициент затухания, который должен быть меньше, чем обратная величина спектрального радиуса . В исходном определении Каца ^[8] использовался постоянный вектор . Хаббелл ^[9] ввел использование общего .${\displaystyle e_{j}}$${\displaystyle j}$${\displaystyle \alpha }$${\displaystyle A}$${\displaystyle {\vec {e}}}$${\displaystyle {\vec {e}}}$

Полвека спустя Боначич и Ллойд ^[10] определили альфа-центральность как:

${\displaystyle {\vec {x}}=(I-\alpha A^{T})^{-1}{\vec {e}}\,}$

что по сути идентично центральности Катца. Точнее, оценка узла отличается ровно на , поэтому если является постоянным, то порядок, индуцированный на узлах, идентичен.${\displaystyle j}$${\displaystyle e_{j}}$${\displaystyle {\vec {e}}}$

Центральность по Кацу можно использовать для вычисления центральности в направленных сетях, таких как сети цитирования и Всемирная паутина. ^[11]

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

Центральность по Кацу также может использоваться для оценки относительного статуса или влияния субъектов в социальной сети. Работа, представленная в ^[12], показывает пример применения динамической версии центральности по Кацу к данным из Twitter и фокусируется на конкретных брендах, имеющих стабильных лидеров обсуждений. Приложение позволяет сравнивать методологию с методологией экспертов-людей в этой области и то, как результаты согласуются с группой экспертов по социальным сетям.

В нейронауке обнаружено, что центральность Катца коррелирует с относительной частотой срабатывания нейронов в нейронной сети. ^[13] Временное расширение центральности Катца применяется к данным фМРТ, полученным в ходе эксперимента по музыкальному обучению в ^[14] , где данные собираются у субъектов до и после процесса обучения. Результаты показывают, что изменения в структуре сети в течение музыкального воздействия создают в каждом сеансе количественную оценку перекрестной коммуникабельности, которая производит кластеры в соответствии с успешностью обучения.

Обобщенная форма центральности Катца может использоваться в качестве интуитивной системы ранжирования для спортивных команд, например, в студенческом футболе . ^[15]

Альфа-центральность реализована в библиотеке igraph для сетевого анализа и визуализации. ^[16]