PageRank assigns an importance score to each webpage by treating links as possible moves in a Markov chain. A page ranks highly when the chain visits it frequently in the long run; links from highly ranked pages therefore matter more than links alone. section 7.1.1 section 7.8
Represent n pages as a directed graph. In a row-stochastic convention, Aᵢⱼ is the probability of moving from page i to page j, and each row sums to one. The rank vector π is a stationary distribution: πA = π, with scores summing to one. Equivalently, it is an eigenvector associated with eigenvalue 1, with orientation chosen to match the matrix convention. section 2.1.2 section 7.1.1
Construct each transition row from a random-surfer rule:
- If page i has dᵢ outgoing links, follow one uniformly with probability p, or jump uniformly to any page with probability 1 − p. Thus Aᵢⱼ = pGᵢⱼ/dᵢ + (1 − p)/n, where G records directed links. section 7.1.1
- If page i has no outgoing links, jump uniformly instead: Aᵢⱼ = 1/n. Random jumps make pages mutually reachable and allow self-transitions, yielding the recurrent, aperiodic chain required for the stationary ranking. section 7.1.1
For a large, sparse link graph, compute the ranking by power iteration rather than solving a full eigenvector problem directly. Start with a rank vector, repeatedly apply the transition matrix, and stop when successive vectors differ by less than a chosen tolerance or an iteration limit is reached. Under the row convention, the update is π⁽ᵗ⁺¹⁾ = π⁽ᵗ⁾A. section 7.1.1 section 7.8
What the implementation demonstrates
A NumPy implementation repeatedly multiplies a vector by a matrix, normalizes it with the Euclidean norm, and checks convergence against a tolerance of 10⁻⁵, with a 100-iteration limit. Its runnable example uses a synthetic matrix XᵀX, not a webpage-link matrix. For PageRank, supply the link-derived transition matrix and normalize the resulting scores to sum to one; the listing’s column-vector multiplication also requires the corresponding matrix orientation. section 7.1.1
Listing 7.1 Page rank algorithm
import numpy as np
from numpy.linalg import norm
np.random.seed(42)
class page_rank():
def __init__(self):
self.max_iter = 100
self.tolerance = 1e-5
def power_iteration(self, A):
n = np.shape(A)[0]
v = np.random.rand(n)
converged = False
iter = 0
while (not converged) and (iter < self.max_iter):
old_v = v
v = np.dot(A, v)
v = v / norm(v)
lambd = np.dot(v, np.dot(A, v))
converged = norm(v - old_v) < self.tolerance
iter += 1
#end while
return lambd, v
if __name__ == "__main__":
X = np.random.rand(10,5)
A = np.dot(X.T, X) #1
pr = page_rank()
lambd, v = pr.power_iteration(A)
print(lambd)
print(v)
#compare against np.linalg implementation
eigval, eigvec = np.linalg.eig(A) #2
idx = np.argsort(np.abs(eigval))[::-1] #2
top_lambd = eigval[idx][0] #2
top_v = eigvec[:,idx][0] #2
Inspect the multiplication, normalization, convergence test, and synthetic-matrix test in the power-iteration code. section 7.1.1
