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

В теории графов, центральность собственного вектора (также называемая собственная центральность или оценка престижа ) - это мера влияния узла в сеть. Относительные оценки присваиваются всем узлам в сети на основе концепции, согласно которой соединения с узлами с высокими оценками вносят больший вклад в оценку рассматриваемого узла, чем равные соединения с узлами с низкими показателями. Высокая оценка собственного вектора означает, что узел связан со многими узлами, которые сами имеют высокие баллы.

Google PageRank и центральность Каца являются вариантами собственного вектора центральность.

• 1 Использование матрицы смежности для определения центральности собственного вектора
• 2 Нормализованная оценка центральности собственного вектора
• 3 Приложения
• 4 См. также
• 5 Ссылки

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

$xv\; =\; 1\; \lambda \; \sum \; T\; \in \; M\; (v),\; xt\; =\; 1\; \lambda \; \sum \; t\; \in \; G\; av,\; txt\; \{\backslash \; displaystyle\; x\_\; \{v\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; lambda\}\}\; \backslash \; sum\; \_\; \{t\; \backslash \; in\; M\; (v)\}\; x\_\; \{t\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; lambda\}\}\; \backslash \; sum\; \_\; \{t\; \backslash \; in\; G\}\; a\_\; \{v,\; t\}\; x\_\; \{t\}\}$

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

$A\; x\; =\; \lambda \; x\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Ax\}\; =\; \backslash \; lambda\; \backslash \; mathbf\; \{x\}\}$

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

PageRank <107 в Google >основан на нормированной центральности собственного вектора или нормированном престиже в сочетании с предположением о случайном скачке. PageRank узла $v\; \{\backslash \; displaystyle\; v\}$имеет рекурсивную зависимость от PageRank других узлов, которые на него указывают. Нормализованная матрица смежности $N\; \{\backslash \; displaystyle\; N\}$определяется как:

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

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

Самое раннее использование центральности собственного вектора было Эдмундом Ландау в Статья 1895 года о подсчете очков в шахматных турнирах.

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

• Центральность собственного вектора - это уникальная мера, удовлетворяющая определенному естественному аксиомы для системы ранжирования.
• В нейробиологии центральность собственного вектора нейрона в модельной нейронной сети коррелирует с его относительная скорость увольнения.
• В стандартном классе моделей обновления мнений или обучения (иногда называемых моделями обучения ДеГрута ) социальное влияние узла на возможные мнения равно центральности его собственного вектора.
• Определение центральности собственного вектора расширено на несколько x или многослойные сети.
• В исследовании с использованием данных из Филиппин авторы показали, что семьи политических кандидатов имели непропорционально высокую центральность собственных векторов в местных сетях смешанных браков.
• В экономической общественные блага центральность собственного вектора человека может быть интерпретирована как то, насколько предпочтения этого человека влияют на эффективный социальный результат (формально, вес Парето в Паретоэффективном социальном результате).

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