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

Простая социальная сеть: узлы представляют людей или объекты, а рёбра между узлами представляют некоторые связи между объектами

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

Например, на рисунке справа представим, что измеряется центральность «Джона» и что ${\displaystyle \alpha =0,5}$. Вес, назначенный каждой связи, которая соединяет «Джона (John)» с его непосредственными соседями «Джейн (Jane)» и «Бобом (Bob)», будет равен ${\displaystyle (0,5)^{1}=0,5}$. Поскольку «Жозе (Jose)» связен с «Джоном» косвенно через «Боба», вес, назначенный этому соединению (состоящему из двух связей), будет равен ${\displaystyle (0,5)^{2}=0,25}$. Аналогично, вес, назначенный связи между «Агнетой (Agneta)» и «Джоном» через «Азиза (Aziz)» и «Джейн», будет равен ${\displaystyle (0,5)^{3}=0,125}$, а вес, назначенный связи между «Агнетой» и «Джоном» через «Диего (Diego)», «Жозе» и «Боба», будет равен ${\displaystyle (0,5)^{4}=0,0625}$.

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

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

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

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

где:

${\displaystyle E}$ — единичная матрица;

${\displaystyle {\overrightarrow {I}}}$ — вектор размера n (n равно числу узлов), состоящий из единиц;

${\displaystyle A^{T}}$ — транспонированная матрица матрицы A;

${\displaystyle (E-\alpha A^{T})^{-1}}$ — обратимая матрица матрицы ${\displaystyle (E-\alpha A^{T})}$[5].

Расширение этой концепции позволяет вычислять маршруты в динамических условиях[6][7]. Направление времени сохраняется, так что вклад асимметричен в направлении распространения информации.

Сети дают данные вида:

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

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

${\displaystyle \left(A^{[k]}\right)_{ij}=1}$, если существует ребро из узла ${\displaystyle i}$ в узел ${\displaystyle j}$ в момент ${\displaystyle t_{k}}$, и равно 0 в противном случае.

Моменты времени ${\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(E-\alpha A^{[0]}\right)^{-1}\cdots \left(E-\alpha A^{[M]}\right)^{-1}~.}$

В нормализованном виде:

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

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

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

Центральность по Кацу можно использовать для вычисления центральности в ориентированных сетях, таких как сети цитат и World Wide Web[8]. Наиболее она пригодна при анализе ориентированных ацикличных графов, в которых традиционно используемые меры, такие как степень влиятельности, становятся бессмысленными[8].

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

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