Центральность узла по Кацу — мера центральности в сети . Понятие центральности ввёл Лео Кац в 1953; она была использована для измерения относительной степени влияния действующего объекта (или узла) внутри социальной сети . В отличие от типичных мер центральности, которые рассматривают только кратчайшие пути ( геодезические ) между парой действующих объектов, центральность по Кацу измеряет влияние путём принятия во внимание общего числа маршрутов между парой действующих объектов .

Показатель подобен ссылочному ранжированию PageRank компании Google и степени влиятельности .

Измерение

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

Например, на рисунке справа представим, что измеряется центральность «Джона» и что ${\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 . В этом случае следующее выражение может быть использовано для вычисления центральности по Кацу:

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

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

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

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

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

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

Примечания

Литература