Википедия

Центральность узла по Кацу: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
пунктуация, стилевые правки
Строка 1:
'''Центральность узла по Кацу''' — это мера [[Центральность|центральности]] в [[Граф (математика)|сети]]. ЭтуПонятие центральностьцентральности ввёл Лео Кац в 1953 и; она была использована для измерения относительной степени влияния действующего объекта (или узла) внутри [[Социальная сеть (социология)|социальной сети]]{{sfn|Katz|1953|с=39–43}}. В отличие от типичных мер центральности, которые рассматривают только кратчайшие пути ([[Геодезическая|геодезические]]) между парой действующих объектов, Центральностьцентральность по Кацу измеряет влияние путём принятия во внимание общего числа маршрутов между парой действующих объектов{{sfn|Hanneman, Riddle|2005}}.
 
Показатель подобен ссылочному ранжированию [[PageRank]] компании [[Google (компания)|Google]] и [[Степень влиятельности|степени влиятельности]]{{sfn|Vigna|2016|с=433—445}}.
Строка 5:
== Измерение ==
[[Файл:Katz example net.png|thumb|500px|right|Простая социальная сеть: узлы представляют людей или объекты, а рёбра между узлами представляют некоторые связи между объектами]]
Центральность по Кацу вычисляет относительное влияние узла в сети путём измерения числа ближайших соседей (узлы первой степени), а также всех других узлов в сети, которые соединяются через этих ближайших соседей. Соединения с этими удалёнными соседями, однако, уменьшаются на множитель <math>\alpha</math>{{sfn|Aggarwal|2011}}. Любому пути или связи между парой узлов назначается вес, определённый значением <math>\alpha</math> и расстоянием между узлами как <math>\alpha^d</math>. При этом вес соединений с удалёнными соседями уменьшаются на множитель <math>\alpha</math>{{sfn|Aggarwal|2011}}.
 
Например, на рисунке справа представим, что измеряется центральность «Джона» и что <math>\alpha = 0,5</math>. Вес, назначенный каждой связи, которая соединяет «Джона (John)» с его непосредственными соседями «Джейн (Jane)» и «Бобом (Bob)», будет равен <math>(0,5)^1 = 0,5</math>. Поскольку «Жозе (Jose)» связен с «Джоном» косвенно через «Боба», вес, назначенный этому соединению (состоящему из двух связей), будет равен <math>(0,5)^2 = 0,25</math>. Аналогично, вес, назначенный связи между «Агнетой (Agneta)» и «Джоном» через «Азиза (Aziz)» и «Джейн», будет равен <math>(0,5)^3 = 0,125</math>, а вес, назначенный связи между «Агнетой» и «Джоном» через «Диего (Diego)», «Жозе» и «Боба», будет равен <math>(0,5)^4 = 0,0625</math>.
 
== Математическая формулировка ==
Пусть ''A'' будет [[Матрица смежности|матрицей смежности]] рассматриваемой сети. Элементы <math>(a_{ij})</math> матрицы ''A'' являются переменными, которые принимают значение 1, если узел ''i'' связен с узлом ''j'', и значение 0 в противном случае. Степени матрицы ''A'' показывают присутствие (или отсутствие) связей между двумя узлами через посредников. Например, в матрице <math>A^3</math>, если элемент <math>(a_{2,12}) = 1</math>, то это говорит о томозначает, что узлы 2 и 12 связаны некоторым путём длины 3. Если <math>C_{\mathrm{Katz}}(i)</math> обозначает центральность по Кацу узла ''i'', то математически
 
:<math>C_{\mathrm{Katz}}(i) = \sum_{k=1}^\infty \sum_{j=1}^n \alpha^k (A^k)_{ji}</math>
Строка 16:
Заметим, что определение выше использует факт, что элемент в позиции <math>(i,j)</math> матрицы <math>A^k</math> отражает общее число соединений степени <math>k</math> между узлами <math>i</math> и <math>j</math>. Значение множителя затухания <math>\alpha</math> следует выбрать так, чтобы оно было меньше, чем обратное значение абсолютного значения наибольшего [[Собственный вектор|собственного значения]] матрицы ''A''{{sfn|Junker, Schreiber|2008}}. В этом случае следующее выражение может быть использовано для вычисления центральности по Кацу:
 
:<math> \overrightarrow{C}_{\mathrm{Katz}} = ((E - \alpha A^T)^{-1}-E)\overrightarrow{I}</math>,
 
где:
Здесь <math>E</math> — единичная матрица, <math>\overrightarrow{I}</math> — вектор размера ''n'' (''n'' равно числу узлов), состоящий из единиц. <math>A^T</math> означает [[Транспонированная матрица|транспонированную матрицу]] матрицы A, а <math>(E - \alpha A^T)^{-1}</math> означает [[Невырожденная матрица|обратимую матрицу]] матрицы <math>(E - \alpha A^T)</math>{{sfn|Junker, Schreiber|2008}}.
 
<math>E</math> — единичная матрица;
 
<math>\overrightarrow{I}</math> — вектор размера ''n'' (''n'' равно числу узлов), состоящий из единиц;
 
<math>A^T</math> — [[транспонированная матрица]] матрицы A;
 
<math>(E - \alpha A^T)^{-1}</math> — [[Невырожденная матрица|обратимая матрица]] матрицы <math>(E - \alpha A^T)</math>{{sfn|Junker, Schreiber|2008}}.
 
Расширение этой концепции позволяет вычислять маршруты в динамических условиях{{sfn|Grindrod, Parsons, Higham, Estrada |2011}}{{sfn|Grindrod, Higham|2010|с=753–770}}. Направление времени сохраняется, так что вклад асимметричен в направлении распространения информации.
Строка 28 ⟶ 36 :
представляя матрицу смежности в каждый момент времени <math>t_k</math>. Следовательно,
 
:<math>\left( A^{[k]} \right)_{ij} = </math> 1, если существует ребро из узла ''i'' в узел ''j'' в момент <math>t_k</math>, и 0 в противном случае.
 
Моменты времени <math>t_0 < t_1 < \cdots < t_M</math> упорядочены, но не обязательно равномерно распределены. <math>Q \in \R^{N \times N}</math> для каждого <math>(Q)_{ij}</math> является взвешенным счётчиком числа динамических маршрутов длины <math>w</math> из узла <math>i</math> в узел <math>j</math>. Вид динамической коммуникабельности между узлами:
Строка 34 ⟶ 42 :
:<math>\mathcal{Q} = \left(E-\alpha A^{[0]} \right)^{-1} \cdots \left(E - \alpha A^{[M]} \right)^{-1}.</math>
 
В нормализованном виде:
Это можно нормализовать
 
:<math>\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 \|}.</math>
 
Таким образом, центральность измеряетпоказывает как эффективно узел <math>n</math> может «рассылать» и «получать» динамические сообщения по сети,:
 
:<math>C_n^{\mathrm{broadcast}} := \sum_{k=1}^{N} \mathcal{Q}_{nk} \quad </math> и <math>\quad C_n^{\mathrm{receive}} := \sum_{k=1}^{N} \mathcal{Q}_{kn}</math>.
 
== Приложения ==
Центральность по Кацу можно использовать для вычисления центральности в ориентированных сетях, таких как сети цитат и World Wide Web{{sfn|Newman|2010}}. Наиболее она пригодна при анализе ориентированных ацикличных графов, в которых традиционно используемые меры, такие как [[степень влиятельности]], становятся бессмысленными{{sfn|Newman|2010}}.
 
Центральность по Кацу более пригодна при анализе ориентированных ацикличных графов, где традиционно используемые меры, такие как [[степень влиятельности]], становятся бессмысленными{{sfn|Newman|2010}}.
 
Центральность по Кацу можно также использовать в оценке относительного статуса или влияния объектов в социальной сети. Статья Лафлина с соавторами{{sfn|Laflin, Mantzaris и др.|2013}} показываетдемонстрирует анализ применения динамической версии центральности по Кацу к данным Твиттера, и фокусируетсявыявляя на объектахобъекты, которыеимеющие имеютстатус стабильных лидеров обсуждения. ПриложениеПрименение понятия Центральности по Кацу позволяет сравнениесравнивать методологии, с работойпривлекающие человеческих экспертов, ви этой области иоценивать каксогласование результатыих согласуютсярезультатов с панелью экспертов социальных сетей.
 
В [[Нейронауки|нейронауках]] было обнаружено, что центральность по Кацу коррелирует с относительной частотой возбуждения [[нейрон]]ов в нейронной сети {{sfn|Fletcher, Wennekers|2017|с=1750013}}. Временно́е расширение центральности по Кацу применяетсябыло применено к данным [[Функциональная магнитно-резонансная томография|фМРТ]], полученным из экспериментов с музыкальным обучением{{sfn|Mantzaris, Bassett и др.|2013|с=83–92 }}, гдев которых данные собираются до и после процесса обучения. Результаты показали, что изменения в структуре сети создавали в каждой сессии количественные связи, которые образуют кластеры на, так называемой, прямой успешного обучения.
 
== Примечания ==
Источник — https://ru.wikipedia.org/wiki/Центральность_узла_по_Кацу