Database Storage and Querying of Web Pages
PageRank is computed by running sprank.py, which iteratively calculates importance scores based on the link structure in your database.
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.
Start the program: Run sprank.py and specify that the calculation should perform two iterations.
Read the first progress value: The first output line represents one complete pass through all pages. Its average change is 0.547.
Read the second progress value: The second output line represents the next complete pass. Its average change is 0.227.
Compare 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.
Find the largest value: Page 4 has the largest listed score, 2.135.
Identify equal values: Pages 2 and 5 share the same listed score, 0.659.
Compare 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
Treating the first iteration as the final ranking
The first pass is still correcting the initial estimates, and later passes can change the scores.
Fix:
Compare the average-change values across passes and continue until the changes become very small.Assuming a larger PageRank score is an absolute universal measure
PageRank scores are relative to the pages in the same network.
Fix:
Interpret the value by comparing it with the other pages in that database.Resetting when the goal is only to refine the current calculation
Reset returns scores to their initial state instead of preserving the progress of the current calculation.
Fix:
Run sprank.py again when you want further refinement; use spreset.py when you deliberately need a fresh start.Ignoring database changes
The link network has expanded, so the previous scores do not describe the complete current network.
Fix:
Run 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
- sprank.py reads the stored page-link network and iteratively calculates PageRank scores.
- The average change reported after each pass shows how much the scores are still moving.
- Very small, decreasing changes indicate convergence and increasingly stable rankings.
- Detailed output can include page ID, version number, score, outlink count, and URL.
- Run ranking again after crawling changes the database; use spreset.py when a fresh calculation is required without deleting pages or links.
Key Takeaways
- PageRank transforms stored pages and hyperlinks into relative numerical importance scores.
- sprank.py performs 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.py clears PageRank values back to their initial state without removing the stored pages or links.