Степень влиятельности

Степень влиятельности — это мера влияния узла в сети. Относительные величины показателя назначаются всем узлам на основе концепции, что связь с узлом высокой степени влиятельности вкладывает больше в показатель рассматриваемого узла, чем аналогичная связь с узлом низкой степени влиятельности. Высокая степень влиятельности означает, что узел связан со многими узлами, имеющими высокие степени влиятельности^[1][2].

Показатель PageRank компании Google и центральность по Кацу являются вариантами степени влиятельности^[3].

Для заданного графа ${\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_{t}={\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} }$

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

Степень влиятельности является мерой влияния, которое узел оказывает на сеть. Если узел связан со многими узлами, которые также имеют высокие показатели влиятельности, то узел будет иметь высокую степень влиятельности^[5].

В нейронауках было обнаружено, что степень влиятельности нейрона в модели нейронной сети коррелирует с относительной частотой возбуждения^[5].

Наиболее раннее использование степени влиятельности можно найти в статье 1895 года Эдмунда Ландау по определению результатов шахматного турнира^[6][7].

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