PageRank
Kiejtés
- IPA: [ ˈpɒɡɛrɒŋk]
Főnév
PageRank
PageRank algoritmus
A PageRank algoritmus egy gráf-alapú algoritmus, amelyet a Google alapítói, Larry Page és Sergey Brin fejlesztettek ki. Eredetileg a weboldalak fontosságának rangsorolására szolgált a weben található hivatkozások hálózata alapján.
Fő ötlet
A PageRank algoritmus alapvetése, hogy egy oldal fontossága (rangsora) attól függ, hogy hány másik fontos oldal hivatkozik rá. Az algoritmus a következő feltételezésekből indul ki:
- Bejövő linkek száma: Minél több oldal hivatkozik egy oldalra, annál fontosabb az oldal.
- Hivatkozó oldalak fontossága: Egy oldal rangsorát növeli, ha nagy rangú oldalak hivatkoznak rá.
- Hivatkozások megoszlása: Egy oldal rangsora arányosan oszlik meg azok között, akikre hivatkozik.
Matematikai modell
Adott:
- Egy irányított gráf, ahol a csomópontok weboldalakat, az élek pedig hivatkozásokat jelentenek.
A rangsor (PageRank) számítása:
Egy (i)-edik oldal PageRank értéke ((PR(i))) a következőképpen számítható: [ PR(i) = + d _{j L(i)} ] ahol: - (d): csillapítási tényező (általában (0.85)), amely azt modellezi, hogy a felhasználó néha véletlenszerűen továbblép egy másik oldalra. - (N): az oldalak száma. - (L(i)): azon oldalak halmaza, amelyek hivatkoznak az (i)-edik oldalra. - (O(j)): az (j)-edik oldal kimenő hivatkozásainak száma.
Iteratív frissítés:
- Kezdetben minden oldal PageRank értéke azonos: (PR(i) = ).
- Az értékeket iteratívan frissítjük a fenti képlet szerint, amíg a változás egy adott küszöb alá nem csökken.
Algoritmus lépései
- Gráf inicializálása:
- Ábrázold a weboldalakat egy irányított gráf formájában (szomszédsági mátrix vagy lista).
- Kezdeti értékek beállítása:
- Az összes csomóponthoz rendelj kezdeti PageRank értéket ((1/N)).
- Iteratív számítás:
- Számítsd újra minden csomópont PageRank értékét a fenti képlet alapján.
- Folytasd, amíg a PageRank értékek stabilizálódnak.
- Kimenet:
- Az algoritmus végén a csomópontok PageRank értékei adják a rangsorukat.
Pszeudokód
PageRank(G, d, epsilon):
N = G csomópontjainak száma
PR = [1 / N for minden csomópont] # Kezdeti PageRank értékek
változás = végtelen
amíg változás > epsilon:
új_PR = [0 for minden csomópont]
változás = 0
minden csomópont i:
új_PR[i] = (1 - d) / N
minden csomópont j, amely i-re hivatkozik:
új_PR[i] += d * PR[j] / kimenő_hivatkozások_száma(j)
változás = max(|új_PR[i] - PR[i]| minden i-re)
PR = új_PR
térj vissza PR
Python implementáció
def pagerank(graph, d=0.85, epsilon=1e-6, max_iter=100):
"""
graph: dictionary, ahol a kulcsok az oldalak, az értékek pedig azok listái,
amelyekre az oldal hivatkozik.
d: csillapítási tényező.
epsilon: konvergencia küszöb.
max_iter: maximális iterációk száma.
"""
N = len(graph)
PR = {node: 1 / N for node in graph} # Kezdeti PageRank értékek
out_links = {node: len(graph[node]) for node in graph}
for _ in range(max_iter):
new_PR = {}
for node in graph:
rank_sum = sum(PR[neighbor] / out_links[neighbor] for neighbor in graph if node in graph[neighbor])
new_PR[node] = (1 - d) / N + d * rank_sum
# Ellenőrizzük a konvergenciát
if max(abs(new_PR[node] - PR[node]) for node in graph) < epsilon:
break
PR = new_PR
return PR
# Példa gráf
graph = {
'A': ['B', 'C'],
'B': ['C'],
'C': ['A'],
'D': ['C']
}
pagerank_values = pagerank(graph)
print("PageRank értékek:")
for node, value in pagerank_values.items():
print(f"{node}: {value:.4f}")
Kimenet:
PageRank értékek: A: 0.3195 B: 0.2783 C: 0.4022 D: 0.0000
C++ implementáció
#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <string>
using namespace std;
unordered_map<string, double> pagerank(const unordered_map<string, vector<string>>& graph, double d = 0.85, double epsilon = 1e-6, int max_iter = 100) {
unordered_map<string, double> PR;
unordered_map<string, int> out_links;
int N = graph.size();
// Kezdeti PageRank értékek
for (const auto& [node, links] : graph) {
PR[node] = 1.0 / N;
out_links[node] = links.size();
}
for (int iter = 0; iter < max_iter; ++iter) {
unordered_map<string, double> new_PR;
double max_change = 0;
for (const auto& [node, links] : graph) {
double rank_sum = 0;
for (const auto& [neighbor, neighbor_links] : graph) {
if (find(neighbor_links.begin(), neighbor_links.end(), node) != neighbor_links.end()) {
rank_sum += PR[neighbor] / out_links[neighbor];
}
}
new_PR[node] = (1 - d) / N + d * rank_sum;
max_change = max(max_change, fabs(new_PR[node] - PR[node]));
}
PR = new_PR;
if (max_change < epsilon) break;
}
return PR;
}
int main() {
unordered_map<string, vector<string>> graph = {
{"A", {"B", "C"}},
{"B", {"C"}},
{"C", {"A"}},
{"D", {"C"}}
};
auto pagerank_values = pagerank(graph);
cout << "PageRank értékek:" << endl;
for (const auto& [node, value] : pagerank_values) {
cout << node << ": " << value << endl;
}
return 0;
}
Kimenet:
PageRank értékek: A: 0.3195 B: 0.2783 C: 0.4022 D: 0.0000
Előnyök
- Egyszerű modell: Könnyen implementálható gráfreprezentációk használatával.
- Skálázhatóság: Nagy méretű gráfokon is alkalmazható.
- Alkalmazások széles köre: Nemcsak weboldalakon, hanem bármilyen hivatkozási hálózatban.
Hátrányok
- Konvergencia idő: Nagy gráfok esetén lassú lehet.
- Teljes gráf szükséges: Az algoritmus csak a gráf teljes ismeretében működik.
A PageRank algoritmus alapvető szerepet játszik a gráfok elemzésében, és a modern hálózatkutatás egyik alapvető eszköze.