Skip to content
Back to search results

PageRank Centrality

Introduced by
Page, Brin, Motwani & Winograd
Year
1999
Type
Iterative link-based centrality algorithm
Family
Centrality
Font size

What does it do?

PageRank is a link-based centrality algorithm that assigns an importance score to each node in a directed graph by measuring how many high-quality nodes point to it.

Introduced by Larry Page, Sergey Brin, Rajeev Motwani, and Terry Winograd at Stanford University in 1999, it became the mathematical foundation of the Google search engine and remains one of the most influential algorithms in network science and information retrieval.

The intuition behind the method

Imagine a random web surfer who clicks links at random, occasionally jumping to a completely random page rather than following a link. The fraction of time this surfer spends on each page, after infinitely many clicks, is that page's PageRank. A page visited often — because many popular pages link to it — receives a high score. The damping factor (typically 0.85) models the probability of continuing to click rather than jumping.

History

PageRank was developed at Stanford University by Larry Page and Sergey Brin as the core ranking mechanism of their BackRub search project, which became Google in 1998. The foundational technical report, co-authored with Rajeev Motwani and Terry Winograd, was published in 1999. The algorithm popularized the use of eigenvector-based centrality in large-scale directed networks and directly inspired subsequent link-analysis algorithms including HITS and TrustRank.

When to use it

PageRank is appropriate when you need to rank nodes in a directed graph by global structural importance, especially when edge direction encodes endorsement or influence (hyperlinks, citations, social follows). It assumes the graph can be modeled as a Markov chain and requires a connected or strongly connected component for clean convergence. It is less suitable for undirected networks where HITS or betweenness centrality may be preferred, and it can be sensitive to link spam or artificially inflated in-degree.

Limitations and considerations

  • Requires a directed graph; application to undirected networks needs convention choices
  • Convergence speed depends on the spectral gap of the transition matrix and can be slow for poorly connected graphs
  • Sensitive to the choice of damping factor d; different values can substantially alter rankings
  • Vulnerable to link-farm manipulation and artificially constructed in-links

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Principled probabilistic foundation via the random-surfer Markov chain model
  • Scales to very large graphs through sparse matrix-vector products and power iteration
  • Captures global graph topology, rewarding nodes endorsed by other high-scoring nodes
  • Widely validated across web, citation, biological, and social network domains

Applications

  • Web search engine ranking: ordering search results by the global authority of web pages
  • Academic citation analysis: identifying influential papers or journals in scientific literature networks
  • Social network influence measurement: ranking users by the prestige of their followers
  • Biological network analysis: finding hub proteins or genes in protein-interaction and gene-regulatory networks
  • Recommendation systems: propagating preference signals through user-item bipartite graphs

How it works

How it works

1

Every node in the graph begins with an equal PageRank score of 1/N, where N is the total number of nodes. This uniform initialization ensures no node has an artificial head start and provides a valid probability distribution across the network before the first iteration.

Formula
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}
2

A column-stochastic transition matrix M is built from the graph's adjacency structure. Each entry M_ij equals 1 divided by the out-degree of node j if an edge from j to i exists, and zero otherwise. Dangling nodes (no outgoing edges) are typically handled by redistributing their score uniformly across all nodes.

Formula
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}
3

The PageRank vector is updated iteratively using the random-surfer formula. With damping factor d (default 0.85), each node receives a base teleportation probability (1-d)/N plus d times the weighted sum of scores contributed by all nodes that link to it. This step is repeated until scores stabilize.

Formula
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)}
4

After each iteration, the L1 norm of the change in the score vector is compared against a small tolerance epsilon (e.g., 1e-6). When the change falls below this threshold, the algorithm has converged and the current score vector is returned as the final PageRank distribution.

Formula
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilon

Common pitfalls

  • Ignoring dangling nodes (nodes with no outgoing edges) can break the stochastic property of the transition matrix and cause incorrect scores
  • Using PageRank on undirected graphs without converting to a symmetric transition model may produce misleading centrality estimates
  • Setting tolerance too loosely leads to premature convergence; too tightly increases computation without meaningful score changes
  • Interpreting PageRank as an absolute importance metric rather than a relative ranking within a specific graph context

Frequently asked questions

What does the damping factor d represent and how should it be chosen?

The damping factor d (typically 0.85) is the probability that the random surfer follows a link rather than teleporting to a random node. Values close to 1 make the algorithm more sensitive to graph structure but slower to converge and more prone to rank sinks; values close to 0 approach uniform ranking. The value 0.85 was empirically validated by Page and Brin for the web graph and is the standard default.

How does PageRank differ from degree centrality?

Degree centrality counts only the direct number of incoming links to a node, treating all sources equally. PageRank weights each incoming link by the score of the linking node, so an endorsement from a highly ranked node contributes more than one from a low-ranked node. This recursive definition captures global graph structure rather than just local connectivity.

Can PageRank be applied to undirected graphs?

Yes, but with caveats. An undirected graph must be converted to a directed representation by replacing each undirected edge with two directed edges. The resulting PageRank scores then equal a function of node degree, reducing the algorithm to a weighted degree centrality. For undirected networks, alternative centrality measures such as eigenvector centrality or betweenness centrality are often more informative.

Related methods

Sources

  1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.

    Open publication reference
    Copied.