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

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

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

ИзмерениеПравить

 

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

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

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

Математическая формулировкаПравить

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

$C_{\mathrm{K}\mathrm{a}\mathrm{t}\mathrm{z}}(i)=\underset{k=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\underset{j=1}{\overset{n}{\sum <!--\; \sum \; -->}}{\mathrm{\alpha <!--\; \alpha \; -->}}^k(A^k{)}_{ji}.$$C_{\mathrm {Katz} }(i)=\sum _{k=1}^{\infty }\sum _{j=1}^{n}\alpha ^{k}(A^{k})_{ji}~.$ 

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

${\stackrel{\to <!--\; \to \; -->}{C}}_{\mathrm{K}\mathrm{a}\mathrm{t}\mathrm{z}}=((E-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}{A}^T{)}^{-<!--\; -\; -->1}-<!--\; -\; -->E)\stackrel{\to <!--\; \to \; -->}{I},$${\overrightarrow {C}}_{\mathrm {Katz} }=((E-\alpha A^{T})^{-1}-E){\overrightarrow {I}}~,$ 

где:

$E$$E$  — единичная матрица;

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

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

$(E-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}{A}^T{)}^{-<!--\; -\; -->1}$$(E-\alpha A^{T})^{-1}$  — обратимая матрица матрицы $(E-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}{A}^T)$$(E-\alpha A^{T})$ .

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

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

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

представляя матрицу смежности в каждый момент времени $t_k$$t_k$ . Следовательно,

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

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

$\mathcal{Q}={\left(E-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}{A}^{[0]}\right)}^{-<!--\; -\; -->1}\cdots <!--\; \cdots \; -->{\left(E-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}{A}^{[M]}\right)}^{-<!--\; -\; -->1}.$${\mathcal {Q}}=\left(E-\alpha A^{[0]}\right)^{-1}\cdots \left(E-\alpha A^{[M]}\right)^{-1}~.$ 

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

${\stackrel{^<!--\; ^\; -->}{\mathcal{Q}}}^{[k]}=\frac{{\stackrel{^<!--\; ^\; -->}{\mathcal{Q}}}^{[k-<!--\; -\; -->1]}{\left(E-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}{A}^{[k]}\right)}^{-<!--\; -\; -->1}}{\Vert {\stackrel{^<!--\; ^\; -->}{\mathcal{Q}}}^{[k-<!--\; -\; -->1]}{\left(E-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}{A}^{[k]}\right)}^{-<!--\; -\; -->1}\Vert }.$${\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\|}}~.$ 

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

$C_n^{\mathrm{b}\mathrm{r}\mathrm{o}\mathrm{a}\mathrm{d}\mathrm{c}\mathrm{a}\mathrm{s}\mathrm{t}}:=\underset{k=1}{\overset{N}{\sum <!--\; \sum \; -->}}{\mathcal{Q}}_{nk}$$C_{n}^{\mathrm {broadcast} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{nk}\quad$  и $C_n^{\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{e}\mathrm{i}\mathrm{v}\mathrm{e}}:=\underset{k=1}{\overset{N}{\sum <!--\; \sum \; -->}}{\mathcal{Q}}_{kn}.$$\quad C_{n}^{\mathrm {receive} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{kn}~.$ 

ПриложенияПравить

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

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

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