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

Мера центральности в сети, основанная на узловом влиянии

В теории графов центральность Каца или альфа -центральность узла является мерой центральности в сети . Он был введен Лео Кацем в 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 в противном случае. Степени А указывают на наличие (или отсутствие) связей между двумя узлами через посредников. Например, в матрице , если элемент , это указывает, что узел 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]

Рекомендации

1. Кац, Л. (1953). Новый индекс статуса, полученный на основе социометрического анализа. Психометрика, 39–43.
2. Ханнеман, Р.А., и Риддл, М. (2005). Введение в методы социальных сетей. Получено с http://faculty.ucr.edu/~hanneman/nettext/.
3. Винья, С. (2016). «Спектральный рейтинг». Сетевая наука . 4 (4): 433–445. дои : 10.1017/nws.2016.21 . hdl : 2434/527942 .
4. Аггарвал, CC (2011). Анализ данных социальных сетей. Нью-Йорк, штат Нью-Йорк: Спрингер.
5. Юнкер, Б.Х., и Шрайбер, Ф. (2008). Анализ биологических сетей. Хобокен, Нью-Джерси: John Wiley & Sons.
6. Гриндрод, Питер; Парсонс, Марк С; Хайэм, Десмонд Дж; Эстрада, Эрнесто (2011). «Коммуникабельность в развивающихся сетях» (PDF) . Физический обзор E . 83 (4). APS: 046120. Бибкод : 2011PhRvE..83d6120G. doi : 10.1103/PhysRevE.83.046120. ПМИД  21599253.
7. Питер Гриндрод; Десмонд Дж. Хайэм. (2010). «Развивающиеся графы: динамические модели, обратные задачи и распространение». Учеб. Р. Сок. А.​ 466 (2115): 753–770. Бибкод : 2010RSPSA.466..753G. дои : 10.1098/rspa.2009.0456 .
8. Лео Кац (1953). «Новый индекс статуса, полученный на основе социометрического анализа». Психометрика . 18 (1): 39–43. дои : 10.1007/BF02289026. S2CID  121768822.
9. Чарльз Х. Хаббелл (1965). «Подход ввода-вывода к идентификации клик». Социометрия . 28 (4): 377–399. дои : 10.2307/2785990. JSTOR  2785990.
10. П. Боначич, П. Ллойд (2001). «Меры центральности, подобные собственным векторам, для асимметричных отношений». Социальные сети . 23 (3): 191–201. CiteSeerX 10.1.1.226.2113 . дои : 10.1016/S0378-8733(01)00038-7. 
11. Ньюман, Мэн (2010). Сети: Введение. Нью-Йорк, штат Нью-Йорк: Издательство Оксфордского университета.
12. Лафлин, Питер; Манцарис, Александр V; Эйнли, Фиона; Отли, Аманда; Гриндрод, Питер; Хайэм, Десмонд Дж (2013). «Обнаружение и подтверждение влияния в динамичной социальной сети». Анализ социальных сетей и майнинг . 3 (4). Спрингер: 1311–1323 гг. дои : 10.1007/s13278-013-0143-7. S2CID  7125694.
13. Флетчер, Джек Маккей; Веннекерс, Томас (2017). «От структуры к активности: использование показателей центральности для прогнозирования активности нейронов». Международный журнал нейронных систем . 28 (2): 1750013. doi : 10.1142/S0129065717500137 . hdl : 10026.1/9713 . ПМИД  28076982.
14. Манцарис, Александр В.; Даниэль С. Бассетт; Николас Ф. Уимбс; Эрнесто Эстрада; Мейсон А. Портер; Питер Дж. Муха; Скотт Т. Графтон; Десмонд Дж. Хайэм (2013). «Центральность динамической сети обобщает обучение человеческого мозга». Журнал сложных сетей . 1 (1): 83–92. arXiv : 1207.5047 . doi : 10.1093/comnet/cnt001.
15. Пак, Джуйонг; Ньюман, MEJ (31 октября 2005 г.). «Сетевая система рейтинга американского студенческого футбола». Журнал статистической механики: теория и эксперимент . 2005 (10): P10014. arXiv : физика/0505169 . дои : 10.1088/1742-5468/2005/10/P10014. ISSN  1742-5468. S2CID  15120571.
16. «Добро пожаловать в новый дом igraph» .