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

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Составная часть Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список  / матрица смежности Список  / матрица заболеваемости Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
МетрикиАлгоритмы
Центральность Степень Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес-модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия / SIR
СпискиКатегории
Темы Программное обеспечение Сетевые ученые Категория: Теория сетей Категория: Теория графов
v т е

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

Он похож на Google «S PageRank и к собственному вектору центральности . ^[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 , если узел я подключен к узлу J и 0 в противном случае. Степени A указывают на наличие (или отсутствие) связей между двумя узлами через посредников. Например, в матрице if element указывает на то, что узел 2 и узел 12 соединены некоторым блужданием длины 3. Если обозначает центральность по Кацу узла  i , то математически:${\ displaystyle (a_ {ij})}$${\ displaystyle A ^ {3}}$${\displaystyle (a_{2,12})=1}$${\displaystyle C_{\mathrm {Katz} }(i)}$

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

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

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

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

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

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

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

Ссылки [ править ]