Centralność wektora własnego

W teorii grafów centralność wektora własnego (zwana także centralnością własną lub wynikiem prestiżu ) jest miarą wpływu węzła w sieci . Względne oceny są przypisywane wszystkim węzłom w sieci w oparciu o koncepcję, że połączenia z węzłami o wysokiej punktacji mają większy wpływ na ocenę danego węzła niż równe połączenia z węzłami o niskiej punktacji. Wysoki wynik wektora własnego oznacza, że ​​węzeł jest połączony z wieloma węzłami, które same mają wysokie wyniki.

Google 's PageRank i centralność Katza to warianty centralności wektora własnego.

Wykorzystanie macierzy sąsiedztwa do znalezienia centralności wektora własnego

Dla danego wykresu z niech będą sąsiedztwa tj. jeśli wierzchołek jest połączony z wierzchołkiem za w przeciwnym razie Względny wynik centralności wierzchołka można zdefiniować jako:

gdzie sąsiadów _ _ Przy niewielkim przegrupowaniu można to zapisać w notacji wektorowej jako równanie wektora własnego

Ogólnie rzecz biorąc, będzie wiele różnych wartości własnych których istnieje niezerowe rozwiązanie wektora własnego. Jednak dodatkowy wymóg, aby wszystkie wpisy w wektorze własnym były nieujemne, implikuje (z twierdzenia Perrona – Frobeniusa ), że tylko największa wartość własna daje pożądaną miarę centralności. Składowa względną ocenę centralności wierzchołka . Wektor własny jest zdefiniowany tylko do wspólnego czynnika, więc tylko stosunki centralności wierzchołków są dobrze określone. Aby zdefiniować wynik bezwzględny, należy znormalizować wektor własny, np. tak, aby suma wszystkich wierzchołków wynosiła 1 lub całkowita liczba wierzchołków n . Iteracja mocy jest jednym z wielu algorytmów wartości własnych , których można użyć do znalezienia dominującego wektora własnego. Co więcej, można to uogólnić tak, że wpisy w A mogą być liczbami rzeczywistymi reprezentującymi siłę połączenia, jak w macierzy stochastycznej .

Znormalizowana punktacja centralności wektora własnego

Google 's PageRank opiera się na znormalizowanej centralności wektora własnego lub znormalizowanym prestiżu w połączeniu z założeniem losowego skoku. PageRank węzła rekurencyjną zależność od PageRank innych węzłów, które na niego wskazują Znormalizowana macierz sąsiedztwa jest zdefiniowana jako:

gdzie zewnętrznym stopniem węzła lub
,

gdzie jest wektorem jedynek i diagonalną wektora re ja za . -stochastyczną.

Znormalizowana ocena prestiżu wektora własnego jest zdefiniowana jako:

lub w postaci wektorowej,

Aplikacje

Centralność wektora własnego jest miarą wpływu węzła na sieć. Jeśli na węzeł wskazuje wiele węzłów (które również mają wysoką centralność wektora własnego), wówczas ten węzeł będzie miał wysoką centralność wektora własnego.

Najwcześniejsze użycie centralności wektora własnego zostało użyte przez Edmunda Landaua w artykule z 1895 roku na temat punktacji turniejów szachowych.

Niedawno naukowcy z wielu dziedzin przeanalizowali zastosowania, przejawy i rozszerzenia centralności wektorów własnych w różnych domenach:

  • Centralność wektora własnego jest unikalną miarą spełniającą pewne naturalne aksjomaty systemu rankingowego.
  • W neurobiologii stwierdzono , że centralność wektora własnego neuronu w modelowej sieci neuronowej koreluje z jego względną szybkością odpalania.
  • Centralność wektora własnego i powiązane koncepcje zostały wykorzystane do modelowania wpływu opinii w socjologii i ekonomii, jak w modelu uczenia się DeGroota .
  • Definicja centralności wektora własnego została rozszerzona na sieci multipleksowe lub wielowarstwowe.
  • W badaniu wykorzystującym dane z Filipin naukowcy wykazali, że rodziny kandydatów politycznych miały nieproporcjonalnie wysoką centralność wektorów własnych w lokalnych sieciach małżeństw mieszanych.
  • Centralność wektora własnego była szeroko stosowana do badania wyników ekonomicznych, w tym współpracy w sieciach społecznościowych. W ekonomicznych z dobrami publicznymi centralność wektora własnego osoby można interpretować jako stopień, w jakim preferencje tej osoby wpływają na efektywny wynik społeczny.

Zobacz też