Database Storage and Querying of Web Pages
A PageRank value is relative to the other pages in the same network. It expresses importance within that stored collection rather than an isolated property of the page.
Try it: PageRank
How PageRank repeatedly passes each page's score along its outgoing links until the scores stop changing, so that pages linked from important pages become important.
How it works
- Every page starts with rank 1.0.
- In each iteration a page splits its current rank equally over its outgoing links; each page adds up the shares it receives.
- Rank held by pages with no outgoing links is shared equally by all pages, so the total stays equal to the number of pages.
- With damping d: new rank = (1 - d) + d × (incoming shares + dangling share). d = 1 is exactly py4e's sprank.py.
- Repeat until the average change per page drops below ε (or the iteration limit is reached).
Default run (22 steps): 5 pages, 7 links. Every page starts with rank 1.0 (ranks always sum to 5). d = 0.85; stop when the average change per page is below 0.0001 or after 30 iterations. Page E has no outgoing links (dangling). … Converged after 15 iterations (average change 0.00009 < 0.0001). Ranks are relative to this graph and sum to 5.
Simplified: A toy web of up to 8 pages. Unlike sprank.py, which only ranks pages that have outgoing links in its database, pages without links stay in the graph and their rank is shared out like sprank's 'evaporated' rank.
Loading the simulation…
From Web Pages to Scores
PageRank turns a database of web pages and their links into numerical importance scores. Running sprank.py examines the link structure stored in the database and repeatedly recalculates every page's score. The result is not produced in a single pass: each pass uses the previous scores to refine the next set of estimates.
Pages and Links in the Database
PageRank depends on the link topology of the stored pages. A page can gain importance when other pages point to it, especially when those referring pages themselves have importance. During each iteration, the algorithm recalculates every page using the scores from the preceding iteration, allowing ranking information to propagate through the network.
A PageRank value is relative to the other pages in the same network. It expresses importance within that stored collection rather than an isolated property of the page.
Running the Iterations
A two-iteration run
Trace a small PageRank calculation on a database containing five pages with two requested iterations.
- 1Start the program
Run
sprank.pyand specify that the calculation should perform two iterations. - 2Read the first progress value
The first output line represents one complete pass through all pages. Its average change is 0.547.
- 3Read the second progress value
The second output line represents the next complete pass. Its average change is 0.227.
- 4Compare the passes
The average change decreased from 0.547 to 0.227, so the scores moved less during the second pass than during the first.
The two-pass run shows movement toward stabilization, but two iterations alone do not establish that the calculation has fully converged.
The iteration number identifies the pass, while the average-change value indicates how much the PageRank scores shifted on average during that pass. Large early changes mean the algorithm is correcting rough initial estimates. Decreasing changes indicate that the scores are becoming more stable.
Reading Ranked Output
After sprank.py runs, the scores are stored in the database and can be queried. Output can appear as simple score tuples or as more detailed database records. The detailed records include a page ID, a version number, the PageRank score, the number of outgoing links, and the URL.
| Output information | What it tells you |
|---|---|
| Page ID | Which stored page the record describes |
| PageRank score | The page's relative importance in the network |
| Outlink count | How many outgoing links the page has |
| URL | The page location recorded in the database |
| Version number | The record's displayed version information |
Fields described in the detailed PageRank database output.
Comparing the reported scores
Interpret the source's simple score list: page 4 has 2.135, pages 2 and 5 each have 0.659, and page 1 has 0.559.
- 1Find the largest value
Page 4 has the largest listed score, 2.135.
- 2Identify equal values
Pages 2 and 5 share the same listed score, 0.659.
- 3Compare the lower value
Page 1's score, 0.559, is slightly below the scores for pages 2 and 5.
Within this network, page 4 is the most important among the listed pages, pages 2 and 5 are tied, and page 1 is lower.
Recognizing Convergence
PageRank has converged when the average change in score per iteration becomes very small. This means that another pass would produce only negligible changes and the rankings have become stable enough to rely on. A pattern such as 0.5, then 0.2, then 0.05, then 0.01 illustrates progressively smaller corrections.
Do not judge convergence from the iteration count alone. Inspect the average-change values and look for a sustained decrease toward a very small value. The acceptable threshold depends on how much stability your task requires.
Crawling and Recalculation
A practical workflow connects crawling, storage, and ranking. spider.py can crawl new pages and add them to the database. sprank.py can then recalculate PageRank using the expanded collection and its links. The scores must reconverge because the network being ranked has changed.
Repeated ranking is useful in two situations: allowing an unchanged network to converge further, and recalculating after new pages or links have changed the network.
Resetting Stored Scores
Use spreset.py when you need to restart PageRank calculations without crawling the pages again. It resets the PageRank values to their initial state while preserving the page records and the link structure. You can then run sprank.py again from the beginning on the same stored network.
Common Interpretation Errors
Common mistake Treating the first iteration as the final ranking
What it looks likeThe first pass reports an average change of 0.547.
Why it failsThe first pass is still correcting the initial estimates, and later passes can change the scores.
Do this insteadCompare the average-change values across passes and continue until the changes become very small.
Common mistake Assuming a larger PageRank score is an absolute universal measure
What it looks likePage 4 has a score of 2.135 in the source's network.
Why it failsPageRank scores are relative to the pages in the same network.
Do this insteadInterpret the value by comparing it with the other pages in that database.
Common mistake Resetting when the goal is only to refine the current calculation
What it looks likeUsing spreset.py before another ranking run.
Why it failsReset returns scores to their initial state instead of preserving the progress of the current calculation.
Do this insteadRun sprank.py again when you want further refinement; use spreset.py when you deliberately need a fresh start.
Common mistake Ignoring database changes
What it looks likeKeeping rankings after spider.py adds pages and links.
Why it failsThe link network has expanded, so the previous scores do not describe the complete current network.
Do this insteadRun sprank.py again so the ranking accounts for the new stored structure.
Check Your Understanding
A run reports average changes of 0.547 and then 0.227. Explain what this decrease indicates, and state what additional evidence you would look for before calling the rankings converged.
Hints
- The values describe average score movement per iteration.
- Convergence is associated with very small changes and stable rankings.
- Consider whether the decreasing pattern continues in later iterations.
A crawler adds new pages and links to the database. Decide whether to leave the existing rankings unchanged, run sprank.py again, or use spreset.py first. Explain your choice.
Hints
- The ranking is based on the database's link structure.
- New pages and links change the network being ranked.
- A reset is specifically for returning scores to their initial state while preserving the network.
Operational Takeaways
- 1
sprank.pyreads the stored page-link network and iteratively calculates PageRank scores. - 2The average change reported after each pass shows how much the scores are still moving.
- 3Very small, decreasing changes indicate convergence and increasingly stable rankings.
- 4Detailed output can include page ID, version number, score, outlink count, and URL.
- 5Run ranking again after crawling changes the database; use
spreset.pywhen a fresh calculation is required without deleting pages or links.
At a glance
- PageRank transforms stored pages and hyperlinks into relative numerical importance scores.
sprank.pyperforms repeated passes, and the average change after each pass helps reveal convergence.- A decreasing average change means the scores are stabilizing; very small changes indicate reliable rankings.
- Crawling new pages requires ranking the expanded database again.
spreset.pyclears PageRank values back to their initial state without removing the stored pages or links.