Кац центральность - Katz centrality

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

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

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

Измерение

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

Центральность Каца вычисляет относительное влияние узла в сети, измеряя количество ближайших соседей (узлов первой степени), а также всех других узлов в сети, которые подключаются к рассматриваемому узлу через этих непосредственных соседей. Однако соединения с удаленными соседями наказываются коэффициентом затухания. ${ displaystyle alpha}$.^[4] Каждому пути или соединению между парой узлов назначается вес, определяемый ${ 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}$.

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

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

${ displaystyle C _ { mathrm {Katz}} (i) = sum _ {k = 1} ^ { infty} sum _ {j = 1} ^ {n} alpha ^ {k} (A ^ { k}) _ {ji}}$

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

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

Здесь ${ displaystyle I}$ - единичная матрица, ${ displaystyle { overrightarrow {I}}}$ вектор размера п (п количество узлов), состоящих из единиц. ${ displaystyle A ^ {T}}$ обозначает транспонированная матрица из А и ${ Displaystyle (I- альфа A ^ {T}) ^ {- 1}}$ обозначает инверсия матриц срока ${ displaystyle (I- alpha A ^ {T})}$.^[5]

Расширение этой структуры позволяет рассчитывать прогулки в динамическом режиме.^[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 {есть край от узла}} i { text {к узлу}} j { text {at time}} t_ {k} 0 & { text {else}} end {case}}}$

Моменты времени ${ displaystyle t_ {0}$ упорядочены, но не обязательно расположены на одинаковом расстоянии. ${ 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]} вправо) ^ {- 1}.}$

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

${ displaystyle { hat { mathcal {Q}}} ^ {[k]} = { frac {{ hat { mathcal {Q}}} ^ {[k-1]} left (I- альфа 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]

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