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

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

Использование матрицы смежности для нахождения степени влиятельности

Для заданного графа ${\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 }$ , для которых существует ненулевой собственный вектор. Однако, из дополнительного требования, чтобы все элементы собственного вектора были неотрицательны, следует (по теореме Фробениуса — Перрона ), что только наибольшее собственное значение приводит к желательной мере центральности . Компонента, соответствующая v -му элементу связанного собственного вектора, даёт относительный показатель центральности вершины ${\displaystyle v}$ в сети. Собственный вектор определён с точностью до множителя, так что вполне определено только отношение центральностей вершин. Чтобы определить абсолютное значение показателя, необходимо нормализовать собственный вектор, например, так, что сумма по всем вершинам равна 1 или нормализовать общим числом вершин n . Поскольку в задаче возникают большие разреженные матрицы , то для нахождения доминирующего собственного вектора среди многих алгоритмов получения собственных значений обычно выбирают эффективный для разреженных матриц степенной метод . Для задачи также существует обобщение, в котором элементы матрицы A являются вещественными числами , представляющими силу связи по аналогии со стохастической матрицей .

Приложения

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

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

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

См. также

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

Примечания

Литература