Formula

PR(v) = (1-d)/N + d * sum_{u->v} PR(u)/L(u)
// d = damping factor (~0.85)
// L(u) = out-degree of u
// N = number of pages
Advertisement

Power iteration

Initialize PR = 1/N. Iterate formula until convergence (typically 30-50 iterations for web-scale).

Advertisement

Handling dangling nodes

Pages with no out-edges: distribute their PR uniformly. Otherwise probability 'leaks'.

Complexity

Per iteration: O(V + E). Iterations to converge: O(log(1/ε) / log(1/d)) ≈ 30-50.