Степень влиятельности — это показатель значимости узла в графе или сети, при котором связь с узлом высокой степени влиятельности учитывается выше при расчетах рассматриваемого узла, чем аналогичная связь с узлом низкой степени влиятельности. В отличие от простого подсчета количества связей, данный показатель наделяет узел большей ценностью, если его контрагенты сами являются центрами влияния. Высокая степень влиятельности означает, что узел связан со многими узлами, имеющими высокие степени влиятельности.
Показатель PageRank компании Google и центральность по Кацу являются вариантами степени влиятельности.
Использование матрицы смежности для нахождения степени влиятельности Для заданного графа с вершинами пусть будет матрицей смежности, то есть , если вершина связана с вершиной , и противном случае. Относительный показатель центральности вершины можно определить как
,
где представляет собой множество соседей вершины , а является константой. После небольших преобразований это выражение можно переписать в векторных обозначениях как уравнение для собственного вектора
В общем случае имеется много различных собственных значений , для которых существует ненулевой собственный вектор. Однако, из дополнительного требования, чтобы все элементы собственного вектора были неотрицательны, следует (по теореме Фробениуса — Перрона), что только наибольшее собственное значение приводит к желательной мере центральности. Компонента, соответствующая v-му элементу связанного собственного вектора, даёт относительный показатель центральности вершины в сети. Собственный вектор определён с точностью до множителя, так что вполне определено только отношение центральностей вершин. Чтобы определить абсолютное значение показателя, необходимо нормализовать собственный вектор, например, так, что сумма по всем вершинам равна 1 или нормализовать общим числом вершин n. Поскольку в задаче возникают большие разреженные матрицы, то для нахождения доминирующего собственного вектора среди многих алгоритмов получения собственных значений обычно выбирают эффективный для разреженных матриц степенной метод. Для задачи также существует обобщение, в котором элементы матрицы A являются вещественными числами, представляющими силу связи по аналогии со стохастической матрицей.
Приложения Степень влиятельности является мерой влияния, которое узел оказывает на сеть. Если узел связан со многими узлами, которые также имеют высокие показатели влиятельности, то узел будет иметь высокую степень влиятельности.
В нейронауках было обнаружено, что степень влиятельности нейрона в модели нейронной сети коррелирует с относительной частотой возбуждения.
Наиболее раннее использование степени влиятельности можно найти в статье 1895 года Эдмунда Ландау по определению результатов шахматного турнира.
См. также Центральность
Примечания
Литература
Категория:Теория графов Категория:Анализ сетей