PageRank is the seminal graph centrality algorithm originally designed for Google Search that ranks nodes by recursive importance — a node is important if it is pointed to by other important nodes — implementing this circular definition as the stationary distribution of a random walker who follows edges with probability $(1-alpha)$ and teleports to a random node with probability $alpha$, producing a global importance score for every node in the network.

What Is PageRank?

• Definition: PageRank computes the stationary distribution of a modified random walk on the graph. At each step, the walker either follows a random outgoing edge with probability $(1-alpha)$ or teleports to a uniformly random node with probability $alpha$ (the damping factor, typically $alpha = 0.15$). The PageRank score $pi_i$ is the long-run probability of being at node $i$: $pi = alpha cdot frac{1}{N}mathbf{1} + (1 - alpha) cdot P^T pi$, where $P$ is the row-normalized adjacency (transition) matrix.
• Recursive Importance: The PageRank of a node depends on the PageRank of nodes that point to it: $pi_i = frac{alpha}{N} + (1 - alpha) sum_{j o i} frac{pi_j}{ ext{out-degree}(j)}$. A link from an important page (high $pi_j$) with few outgoing links contributes more than a link from an unimportant page with many outgoing links — quality and exclusivity of endorsement both matter.
• Teleportation: Without the teleport factor, the random walker can get trapped in dead-end nodes (no outgoing edges) or sink into cycles. Teleportation guarantees ergodicity — the walker visits every node eventually — and ensures a unique stationary distribution exists. The teleport factor $alpha$ also controls the balance between local structure (following links) and global accessibility (random jumping).

Why PageRank Matters

• Web Search Foundation: PageRank was the original algorithmic innovation behind Google — ranking web pages by the global link structure of the internet rather than just keyword matching. Pages linked by many authoritative sites rank higher, producing search results that reflect collective quality assessment rather than content manipulation.
• Personalized PageRank (PPR): Replacing the uniform teleport distribution with a personalized one (always teleporting back to a specific node $v$) produces the PPR vector, which measures the relevance of every node from $v$'s perspective. PPR has become a fundamental primitive in modern GNNs — APPNP uses PPR propagation to achieve multi-hop aggregation without over-smoothing, and PPR-based neighbor sampling enables efficient training on large graphs.
• GNN Propagation: The connection between PageRank and GNNs is deep — both compute node-level features by aggregating information from the graph structure. PPR propagation $pi_v = alpha sum_{k=0}^{infty} (1-alpha)^k (D^{-1}A)^k e_v$ is an exponentially-weighted infinite-depth aggregation that avoids over-smoothing by down-weighting distant nodes, providing theoretically grounded multi-scale propagation for graph neural networks.
• Network Analysis Beyond the Web: PageRank generalizes to any directed network — ranking academic papers by citation importance, identifying influential genes in regulatory networks, detecting key infrastructure nodes in power grids, and measuring influence in social networks. The algorithm provides a principled, scalable centrality measure for any domain with directed relationships.

PageRank Variants

PageRank is eigenvector centrality with teleportation — computing the global steady-state importance of every node in a directed network through a random walk that balances local link-following with random exploration, providing the theoretical and practical bridge between classical network analysis and modern graph neural network propagation.