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

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

Google с PageRank и Кац центральность - варианты центральности собственного вектора.^[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 _{tin M(v)}x_{t}={frac {1}{lambda }}sum _{tin G}a_{v,t}x_{t}}$

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

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

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

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

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

$${displaystyle N(u,v)={egin{cases}{1 over operatorname {od} (u)},&{ ext{if }}(u,v)in E�,&{ ext{if }}(u,v)ot in Eend{cases}}}$$

куда ${displaystyle od(u)}$ это высшая степень узла ${displaystyle u}$.

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

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

Приложения

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

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

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

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

Смотрите также

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

Рекомендации

1. Заки, Мохаммед Дж .; Мейра-младший, Вагнер (2014). Интеллектуальный анализ и анализ данных: основные концепции и алгоритмы. Издательство Кембриджского университета. ISBN  9780521766333.
2. М. Э. Дж. Ньюман. «Математика сетей» (PDF). Получено 2006-11-09.
3. Кристиан Ф. А. Негре, Уриэль Н. Морзан, Хайди П. Хендриксон, Ританкар Пал, Джордж П. Лиси, Дж. Патрик Лориа, Иван Ривальта, Джунмин Хо, Виктор С. Батиста. (2018). «Центральность собственного вектора для характеристики аллостерических путей белков». Труды Национальной академии наук. 115 (52): E12201 – E12208. Дои:10.1073 / pnas.1810452115. ЧВК  6310864. PMID  30530700.
4. Дэвид Остин. "Как Google находит вашу иглу в стоге сена Интернета". AMS.
5. М. Э. Дж. Ньюман. «Математика сетей» (PDF). Получено 2006-11-09.
6. Флетчер, Джек Маккей и Веннекерс, Томас (2017). «От структуры к активности: использование мер центральности для прогнозирования нейронной активности». Международный журнал нейронных систем. 0 (0): 1750013. Дои:10.1142 / S0129065717500137.
7. Эдмунд Ландау (1895). "Zur relativen Wertbemessung der Turnierresultate". Deutsches Wochenschach (11): 366–369. Дои:10.1007/978-1-4615-4819-5_23.
8. Холм, Питер (15 апреля 2019 г.). «Впервые в сетевой науке». Получено 17 апреля 2019.
9. Альтман, Алон; Тенненхольц, Моше (2005). Системы ранжирования. Нью-Йорк, Нью-Йорк, США: ACM Press. Дои:10.1145/1064009.1064010. ISBN  1-59593-049-3.
10. Паласиос-Уэрта, Игнасио; Волий, Оскар (2004). «Измерение интеллектуального влияния» (PDF). Econometrica. Эконометрическое общество. 72 (3): 963–977. Дои:10.1111 / j.1468-0262.2004.00519.x. HDL:10419/80143. ISSN  0012-9682.
11. Сола, Луис; Романс, Мигель; Криадо, Регино; Флорес, Хулио; Гарсиа дель Амо, Алехандро; Боккалетти, Стефано (2013). «Центральность собственных векторов узлов в мультиплексных сетях». Хаос: междисциплинарный журнал нелинейной науки. Издательство AIP. 23 (3): 033131. Дои:10.1063/1.4818544. ISSN  1054-1500. PMID  24089967. S2CID  14556381.
12. Круз, Чези; Лабонн, Жюльен; Querubin, Пабло (2017). "Сети семей политиков и результаты выборов: данные Филиппин". Американский экономический обзор. Издательство Чикагского университета. 107 (10): 3006–37. Дои:10.1257 / aer.20150343.
13. Эллиотт, Мэтью; Голуб, Вениамин (2019). «Сетевой подход к общественным благам». Журнал политической экономии. Издательство Чикагского университета. 127 (2): 730–776. Дои:10.1086/701032. ISSN  0022-3808.