CoreSource checked

PageRank

PageRank scores graph nodes by repeatedly propagating rank through directed links.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Intermediate
Family: Graph Algorithm
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

PageRank is a graph algorithm that extracts graph structure such as components, rankings, closures, flows, or matchings. It helps expose graph structure that is hard to see from local edges alone.

Core Concepts

link graphrandom surfer modelpower iterationstationary distribution

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V + E)

Average

O(V + E)

Worst

O(V + E)

Space

O(V)

When to Use

Use PageRank when the graph question matches its traversal, ranking, flow, or matching model.
Use it when exact graph structure is more valuable than an approximate summary.

When Not to Use

Avoid when graph direction, weights, or capacities do not match the method.
Avoid when approximate graph summaries are enough and exact traversal is too expensive.

What It Does

Explores graph relationships
Maintains frontier, component, or residual state
Returns structural information about the graph

Use Cases

Network analysis
Dependency analysis
Graph optimization

Inputs

Graph
Start nodes or selected subgraph
Weights or capacities if needed

Outputs

Visited order
Graph structure
Flow, component, ranking, or matching result

Key Formulas (1)

PageRank update

rank(v) = (1 − d) / N + d · ∑(rank(u) / out_degree(u))

rank(v) = (1 - d) / N + d * sum(rank(u) / out_degree(u))

Updates a page score from scores contributed by incoming links.

Pseudocode

1.Initialize graph state, scores, components, or residual capacity
2.Visit or update eligible nodes and edges
3.Apply the method's traversal, ranking, matching, or flow rule
4.Repeat until no useful updates remain
5.Return the graph structure or score result

Canonical Example

Input: graph = small directed graph
Output: visited order, component, ranking, flow, or matching result
Explanation: PageRank updates graph state until the requested structural result is available.

Implementation Notes

Represent edge direction, weights, and capacities explicitly.
Keep traversal state local so repeated runs do not leak state.

Common Pitfalls

Treating directed and undirected edges the same changes the result.
Not resetting visited, residual, or component state corrupts later traversals.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show graph nodes and edges changing color as the traversal, ranking, or flow state evolves.

Step 1 of 5: Initialize graph state, scores, components, or residual capacity

graph

Notes

PageRank operates in O(V + E) time and O(V) space within the Graph Algorithm family. Key governing relation: rank(v) = (1 - d) / N + d * sum(rank(u) / out_degree(u)). Often compared with HITS Algorithm and Power Iteration.