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

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

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

Измерение

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

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

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

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

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

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

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

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

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

Сеть производит данные вида:

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

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

\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}}

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

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

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

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

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

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}

.

Альфа-центральность

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

Ссылки

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

[katz1953-1] Кац, Л. (1953). Новый индекс статуса, полученный на основе социометрического анализа. Психометрика, 39–43.

[hanneman2005-2] Ханнеман, Р.А., и Риддл, М. (2005). Введение в методы социальных сетей. Получено с http://faculty.ucr.edu/~hanneman/nettext/.

[vigna2016-3] Винья, С. (2016). «Спектральный рейтинг» . Сетевая наука . 4 (4): 433–445. дои : 10.1017/nws.2016.21 . hdl : 2434/527942 .

[aggarwal2011-4] Аггарвал, CC (2011). Анализ данных социальных сетей. Нью-Йорк, штат Нью-Йорк: Спрингер.

[junker2008-5] Jump up to: ^а ^б Юнкер Б.Х. и Шрайбер Ф. (2008). Анализ биологических сетей. Хобокен, Нью-Джерси: John Wiley & Sons.

[grindrod2011communicability-6] Гриндрод, Питер; Парсонс, Марк С; Хайэм, Десмонд Дж; Эстрада, Эрнесто (2011). «Коммуникабельность в развивающихся сетях» (PDF) . Физический обзор E . 83 (4). APS: 046120. Бибкод : 2011PhRvE..83d6120G . дои : 10.1103/PhysRevE.83.046120 . ПМИД 21599253 .

[grindrod2010Dynamical-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 .

[newman2010-11] Jump up to: ^а ^б Ньюман, Мэн (2010). Сети: Введение. Нью-Йорк, штат Нью-Йорк: Издательство Оксфордского университета.

[laflin2013discovering-12] Лафлин, Питер; Манцарис, Александр V; Эйнли, Фиона; Отли, Аманда; Гриндрод, Питер; Хайэм, Десмонд Дж (2013). «Обнаружение и подтверждение влияния в динамичной социальной сети». Анализ социальных сетей и майнинг . 3 (4). Спрингер: 1311–1323 гг. дои : 10.1007/s13278-013-0143-7 . S2CID 7125694 .

[jmckay2017-13] Флетчер, Джек Маккей; Веннекерс, Томас (2017). «От структуры к активности: использование показателей центральности для прогнозирования активности нейронов» . Международный журнал нейронных систем . 28 (2): 1750013. doi : 10.1142/S0129065717500137 . hdl : 10026.1/9713 . ПМИД 28076982 .

[mantzaris2013fMRI-14] Манцарис, Александр В.; Даниэль С. Бассетт; Николас Ф. Уимбс; Эрнесто Эстрада; Мейсон А. Портер; Питер Дж. Муха; Скотт Т. Графтон; Десмонд Дж. Хайэм (2013). «Центральность динамической сети обобщает обучение человеческого мозга». Журнал сложных сетей . 1 (1): 83–92. arXiv : 1207.5047 . дои : 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» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]