Centralność PageRank
- Autor metody
- Page, Brin, Motwani & Winograd
- Rok
- 1999
- Typ
- Iterative link-based centrality algorithm
- Rodzina
- Centrality
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
PageRank to algorytm centralności oparty na linkach, który przypisuje wynik ważności każdemu węzłowi w grafie skierowanym, mierząc, ile wysokiej jakości węzłów do niego wskazuje.
Wprowadzony przez Larry'ego Page'a, Sergeya Brina, Rajeeva Motwaniego i Terry'ego Winograda na Uniwersytecie Stanforda w 1999 roku, stał się matematyczną podstawą wyszukiwarki Google i pozostaje jednym z najbardziej wpływowych algorytmów w nauce o sieciach i wyszukiwaniu informacji.
Intuicja stojąca za metodą
Wyobraźmy sobie losowego internautę, który klika linki losowo, od czasu do czasu przeskakując do zupełnie losowej strony zamiast podążać za linkiem. Ułamek czasu, jaki ten internauta spędza na każdej stronie, po nieskończonej liczbie kliknięć, to właśnie PageRank tej strony. Strona często odwiedzana — ponieważ wiele popularnych stron do niej linkuje — otrzymuje wysoki wynik. Współczynnik tłumienia (zazwyczaj 0,85) modeluje prawdopodobieństwo kontynuowania klikania zamiast przeskakiwania.
Historia
PageRank został opracowany na Uniwersytecie Stanforda przez Larry'ego Page'a i Sergeya Brina jako podstawowy mechanizm rankingowy ich projektu wyszukiwania BackRub, który stał się Google w 1998 roku. Podstawowy raport techniczny, współautorstwa Rajeeva Motwaniego i Terry'ego Winograda, został opublikowany w 1999 roku. Algorytm spopularyzował użycie centralności opartej na wektorach własnych w dużych sieciach skierowanych i bezpośrednio zainspirował kolejne algorytmy analizy linków, w tym HITS i TrustRank.
Kiedy stosować
PageRank jest odpowiedni, gdy potrzebujesz uszeregować węzły w grafie skierowanym według globalnego znaczenia strukturalnego, zwłaszcza gdy kierunek krawędzi koduje poparcie lub wpływ (hiperłącza, cytowania, obserwacje w sieciach społecznościowych). Zakłada, że graf można modelować jako łańcuch Markowa i wymaga spójnego lub silnie spójnego komponentu dla czystej zbieżności. Jest mniej odpowiedni dla grafów nieskierowanych, gdzie preferowane mogą być centralności HITS lub międzywęzłowa, i może być wrażliwy na spam linków lub sztucznie zawyżony stopień wejściowy.
Ograniczenia i uwagi
- Wymaga grafu skierowanego; zastosowanie do grafów nieskierowanych wymaga wyboru konwencji
- Szybkość zbieżności zależy od luki spektralnej macierzy przejściowej i może być powolna dla słabo połączonych grafów
- Wrażliwy na wybór współczynnika tłumienia d; różne wartości mogą znacząco zmienić rankingi
- Podatny na manipulacje farmami linków i sztucznie skonstruowane linki przychodzące
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Ugruntowana probabilistyczna podstawa poprzez model łańcucha Markowa losowego internauty
- Skaluje się do bardzo dużych grafów dzięki produktom macierzy rzadkich i iteracji potęgowej
- Uchwyca globalną topologię grafu, nagradzając węzły poparte przez inne węzły o wysokim wyniku
- Szeroko walidowany w domenach sieci WWW, cytowań, biologicznych i społecznościowych
Zastosowania
- Ranking wyszukiwarek internetowych: porządkowanie wyników wyszukiwania według globalnego autorytetu stron internetowych
- Analiza cytowań naukowych: identyfikacja wpływowych artykułów lub czasopism w sieciach literatury naukowej
- Pomiar wpływu w sieciach społecznościowych: szeregowanie użytkowników według prestiżu ich obserwujących
- Analiza sieci biologicznych: znajdowanie białek lub genów centralnych w sieciach interakcji białek i regulacji genów
- Systemy rekomendacji: propagacja sygnałów preferencji przez dwudzielne grafy użytkownik-przedmiot
Jak to działa
Jak to działa
Każdy węzeł w grafie zaczyna z równym wynikiem PageRank wynoszącym 1/N, gdzie N to całkowita liczba węzłów. Ta jednolita inicjalizacja zapewnia, że żaden węzeł nie ma sztucznego początkowego przyspieszenia i stanowi prawidłowy rozkład prawdopodobieństwa w sieci przed pierwszą iteracją.
Wzór
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}Macierz przejściowa stochastyczna kolumnowo M jest budowana na podstawie struktury incydencji grafu. Każdy element M_ij jest równy 1 podzielone przez stopień zewnętrzny węzła j, jeśli istnieje krawędź od j do i, i zero w przeciwnym razie. Węzły wiszące (bez krawędzi wychodzących) są zazwyczaj obsługiwane przez redystrybucję ich wyniku równomiernie między wszystkie węzły.
Wzór
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}Wektor PageRank jest aktualizowany iteracyjnie przy użyciu formuły losowego internauty. Ze współczynnikiem tłumienia d (domyślnie 0,85), każdy węzeł otrzymuje bazowe prawdopodobieństwo teleportacji (1-d)/N plus d razy ważona suma wyników wniesionych przez wszystkie węzły, które do niego linkują. Ten krok jest powtarzany, aż wyniki się ustabilizują.
Wzór
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}Po każdej iteracji norma L1 zmiany wektora wyników jest porównywana z małą tolerancją epsilon (np. 1e-6). Gdy zmiana spadnie poniżej tego progu, algorytm zbiegł, a bieżący wektor wyników jest zwracany jako ostateczny rozkład PageRank.
Wzór
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilonCzęste pułapki
- Ignorowanie węzłów wiszących (węzłów bez krawędzi wychodzących) może naruszyć własność stochastyczną macierzy przejściowej i spowodować nieprawidłowe wyniki
- Użycie PageRank na grafach nieskierowanych bez konwersji do symetrycznego modelu przejściowego może prowadzić do wprowadzających w błąd oszacowań centralności
- Ustawienie tolerancji zbyt luźno prowadzi do przedwczesnej zbieżności; zbyt ciasno zwiększa obliczenia bez znaczących zmian wyników
- Interpretowanie PageRank jako absolutnej miary ważności, a nie jako względnego rankingu w kontekście konkretnego grafu
Najczęściej zadawane pytania
Co oznacza współczynnik tłumienia d i jak należy go wybrać?
Współczynnik tłumienia d (zazwyczaj 0,85) to prawdopodobieństwo, że losowy internauta podąża za linkiem, zamiast teleportować się do losowego węzła. Wartości bliskie 1 sprawiają, że algorytm jest bardziej wrażliwy na strukturę grafu, ale wolniej zbiega i jest bardziej podatny na „zapadnie rankingu” (rank sinks); wartości bliskie 0 zbliżają się do równomiernego rankingu. Wartość 0,85 została empirycznie potwierdzona przez Page'a i Brina dla grafu sieci WWW i jest standardową wartością domyślną.
Czym PageRank różni się od centralności stopnia?
Centralność stopnia liczy tylko bezpośrednią liczbę linków przychodzących do węzła, traktując wszystkie źródła równo. PageRank waży każdy link przychodzący przez wynik linkującego węzła, więc poparcie od węzła o wysokim rankingu wnosi więcej niż od węzła o niskim rankingu. Ta rekurencyjna definicja uchwyca globalną strukturę grafu, a nie tylko lokalną łączność.
Czy PageRank można zastosować do grafów nieskierowanych?
Tak, ale z zastrzeżeniami. Graf nieskierowany musi zostać przekształcony w reprezentację skierowaną poprzez zastąpienie każdej nieskierowanej krawędzi dwiema skierowanymi krawędziami. Uzyskane wyniki PageRank stają się wtedy funkcją stopnia węzła, redukując algorytm do ważonej centralności stopnia. Dla sieci nieskierowanych alternatywne miary centralności, takie jak centralność wektorowa lub międzywęzłowa, są często bardziej informatywne.
Pokrewne metody
Źródła
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.
Otwórz odnośnik do publikacjiSkopiowano.