Центральность собственного вектора

В теории графов , собственный вектор центральности (также называемый eigencentrality или престижа оценка ^[1] ) является мерой влияния узла в сети . Относительные оценки присваиваются всем узлам в сети на основе концепции, согласно которой соединения с узлами с высокими оценками вносят больший вклад в оценку рассматриваемого узла, чем равные соединения с узлами с низкими показателями. Высокая оценка собственного вектора означает, что узел связан со многими узлами, которые сами имеют высокие оценки. ^{[2] [3]}

Google «s PageRank и сосредоточенность Katz представляют собой варианты собственного вектора центральности. ^[4]

Использование матрицы смежности для определения центральности собственного вектора [ править ]

Для данного графа с вершинами пусть будет матрица смежности , т.е. если вершина связана с вершиной , и в противном случае. Относительная центральность,, оценка вершины может быть определена как:${\ Displaystyle G: = (V, E)}$${\ displaystyle | V |}$${\ displaystyle A = (a_ {v, t})}$${\ displaystyle a_ {v, t} = 1}$${\ displaystyle v}$${\ displaystyle t}$${\ displaystyle a_ {v, t} = 0}$${\ displaystyle x}$${\ displaystyle v}$

${\displaystyle x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{v}={\frac {1}{\lambda }}\sum _{t\in G}a_{v,t}x_{t}}$

где - множество соседей, а - константа. С небольшой переделкой это можно переписать в векторной записи как уравнение для собственных векторов${\displaystyle M(v)}$${\displaystyle v}$${\displaystyle \lambda }$

${\displaystyle \mathbf {Ax} =\lambda \mathbf {x} }$

В общем, будет много разных собственных значений, для которых существует ненулевое решение по собственному вектору. Однако дополнительное требование, чтобы все элементы в собственном векторе были неотрицательными, влечет (по теореме Перрона – Фробениуса ), что только наибольшее собственное значение дает желаемую меру центральности. ^[5] компонент соответствующего собственного вектора затем дает относительную значимость балл вершины в сети. Собственный вектор определяется только с точностью до общего множителя, поэтому корректно определены только отношения центральностей вершин. Чтобы определить абсолютную оценку, необходимо нормализовать собственный вектор, например, так, чтобы сумма по всем вершинам была равна 1 или общему количеству вершин  n .${\displaystyle \lambda }$${\displaystyle v^{\text{th}}}$${\displaystyle v}$Степенная итерация - это один из многих алгоритмов собственных значений, которые можно использовать для нахождения этого доминирующего собственного вектора. ^[4] Кроме того, это можно обобщить, так что записи в A могут быть действительными числами, представляющими силу соединения, как в стохастической матрице .

Нормализованная оценка центральности собственного вектора [ править ]

Google «s PageRank основан на нормированный собственный вектор центральности или нормализованного престижа, в сочетании со случайным скачка предположения. ^[1] PageRank узла имеет рекурсивную зависимость от PageRank других узлов, которые на него указывают. Нормализованная матрица смежности определяется как:${\displaystyle v}$${\displaystyle N}$

где - степень выхода узла , или в векторной форме:${\displaystyle od(u)}$${\displaystyle u}$

${\displaystyle \mathbf {N} =\mathbf {diag} (\mathbf {Ae} )^{-1}\mathbf {A} }$,

где - вектор единиц, а - диагональная матрица вектора . является стохастической матрицей по строкам.${\displaystyle \mathbf {e} }$${\displaystyle \mathbf {diag} (\mathbf {x} )}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {N} }$

Нормализованная оценка престижа собственного вектора определяется как:

${\displaystyle p(v)=\sum _{u}{N^{T}(v,u)\cdot p(u)},}$

или в векторной форме,

${\displaystyle \mathbf {p} =\mathbf {N} ^{T}\mathbf {p} .}$

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

Центральность собственного вектора - это мера влияния узла на сеть. Если на узел указывают многие узлы (которые также имеют высокую центральность по собственному вектору), то этот узел будет иметь высокую центральность по собственному вектору. ^[6]

Самое раннее использование центральности собственного вектора было сделано Эдмундом Ландау в 1895 году в статье о подсчете очков в шахматных турнирах. ^{[7] [8]}

Совсем недавно исследователи из многих областей проанализировали приложения, проявления и расширения центральности собственных векторов в различных областях:

• Центральность собственного вектора - это единственная мера, удовлетворяющая определенным естественным аксиомам системы ранжирования. ^{[9] [10]}
• В нейробиологии было обнаружено , что центральность собственного вектора нейрона в модельной нейронной сети коррелирует с его относительной частотой срабатывания. ^[6]
• Центральность собственного вектора и связанные с ней концепции использовались для моделирования влияния мнения в социологии и экономике, как и в модели обучения ДеГрута .
• Определение центральности собственного вектора было распространено на мультиплексные или многослойные сети. ^[11]
• В исследовании с использованием данных из Филиппин исследователи показали, что семьи политических кандидатов имели непропорционально высокую центральность собственных векторов в местных сетях смешанных браков. ^[12]
• Центральность собственного вектора и связанные с ней понятия применялись для моделирования различных экономических результатов, включая сотрудничество в социальных сетях. ^[13]

См. Также [ править ]

• Центральность

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