One PageRank Iteration Stephard

One PageRank Iteration Step

hard RAG & Retrieval 15 min

NumPy allowed · plain Python earns 10 bonus points

A query retrieves context

Embedding similarity ranks the documents before generation.

Open lesson →

01query

02embed

03retrieve

04context

What is RAG?→ embed →top context

retrieval.md44%

rag-systems.md33%

agents.md24%

Cosine-like similarity scores ranked before context assembly

Implement a single real PageRank power-iteration step, the algorithm behind ranking the most 'important' entities in a large knowledge graph by link structure.

Task

Implement pagerank_step(graph, scores, damping). For each node n, its new score is (1-damping)/N + damping * sum(scores[m]/len(graph[m]) for m in graph if n in graph[m]), where N = len(graph). A node with NO outgoing edges (len(graph[m])==0) contributes nothing to any node's new score (avoid dividing by zero). Return the dict of new scores.

Function Signature

pagerank_step(graph: dict[str, list[str]], scores: dict[str, float], damping: float) -> dict[str, float]

Examples

Example 1: simple two-node cycle
Input: graph = {'a': ['b'], 'b': ['a']}
scores = {'a': 0.5, 'b': 0.5}
damping = 0.85
Output: {'a': 0.5, 'b': 0.5}

Example 2: hub node distributes score
Input: graph = {'a': ['b', 'c'], 'b': [], 'c': []}
scores = {'a': 1, 'b': 0, 'c': 0}
damping = 0.85
Output: {'a': 0.05000000000000001, 'b': 0.475, 'c': 0.475}

Example 3: dangling node contributes nothing
Input: graph = {'a': [], 'b': ['a']}
scores = {'a': 0.5, 'b': 0.5}
damping = 0.85
Output: {'a': 0.5, 'b': 0.07500000000000001}

Constraints

graph maps node -> list of outgoing neighbors, every node appears as a key
0 < damping < 1

Python3Saved ✓

def pagerank_step(graph, scores, damping):

# Your implementation here

pass

Case 1: simple two-node cycle

Input: graph = {'a': ['b'], 'b': ['a']}
scores = {'a': 0.5, 'b': 0.5}
damping = 0.85

Expected: {'a': 0.5, 'b': 0.5}

Case 2: hub node distributes score

Input: graph = {'a': ['b', 'c'], 'b': [], 'c': []}
scores = {'a': 1, 'b': 0, 'c': 0}
damping = 0.85

Expected: {'a': 0.05000000000000001, 'b': 0.475, 'c': 0.475}

Case 3: dangling node contributes nothing

Input: graph = {'a': [], 'b': ['a']}
scores = {'a': 0.5, 'b': 0.5}
damping = 0.85

Expected: {'a': 0.5, 'b': 0.07500000000000001}