Ranking Algorithms and Search Engine Fundamentals
PageRank is computed by running sprank.py, which iteratively calculates importance scores based on the link structure in your database.
From Links to Scores
PageRank turns a database of web pages and their links into numerical importance scores. The calculation is performed by sprank.py. Rather than assigning final values in one pass, the program repeatedly examines the complete link structure and refines the score for every page.
A page's importance depends on the links pointing to it and on the importance of the pages that provide those links. This creates a feedback loop through the network: a page receiving links from high-scoring pages can gain score, and that information then propagates through later calculations. The result is not merely a count of incoming links; it is a score produced from the broader link topology stored in the database.
A Complete Ranking Pass
To begin, run sprank.py and provide the number of iterations requested by the program. One iteration is one complete pass through all pages in the database. During that pass, the algorithm recalculates the scores using the results from the previous iteration and then reports progress.
Reading a Two-Iteration Run
A database contains five pages. You ask sprank.py to perform two iterations. The reported average changes are 0.547 for the first iteration and 0.227 for the second.
First pass: The program processes all five pages and reports an average PageRank change of 0.547. The relatively large change indicates that the current scores are still being substantially corrected.
Second pass: The program processes all five pages again and reports an average change of 0.227. The decrease shows that the scores are moving toward a more stable state.
Interpretation: The second value is smaller than the first, so the run shows progress toward convergence. Two iterations do not automatically prove that the calculation is finished; the change must become sufficiently small for the purpose of the calculation.
The average change decreased from 0.547 to 0.227, showing that successive passes are refining the scores.
The iteration count controls how many complete passes sprank.py performs. The average change reported after each pass is the practical signal to watch: large early changes indicate active correction, while very small later changes indicate that the scores are stabilizing.
Reading the Ranking Output
After sprank.py runs, the PageRank scores are stored in the database and can be queried. Output can appear as simple score tuples or as more detailed database records. A detailed record includes the page ID, a version number, the PageRank score, the number of outgoing links, and the page URL.
| Output field | What it tells you |
|---|---|
| Page ID | Which stored page the record describes |
| Version number | The record's version information |
| PageRank score | The page's relative importance in the network |
| Outgoing-link count | How many links the page points to |
| URL | The address associated with the stored page |
Fields available in a detailed PageRank database record.
One source listing gives scores of 2.135, 0.659, 0.659, and 0.559 for pages in the same network. The value 2.135 is the largest in that listing, so its page has the greatest relative importance there. The two pages with 0.659 are tied in that listing. These values should be compared within the same network; they describe relative importance rather than a universal score shared across unrelated databases.
Crawling and Ranking Pipeline
Ranking is part of a repeating workflow. spider.py can crawl new pages and add them to the database. sprank.py can then recalculate PageRank using the expanded collection of pages and links. The new network may require the scores to reconverge because the underlying data has changed.
Treat crawling and ranking as connected stages. When the page collection or its links expand, rerun PageRank so that the scores describe the current database rather than an earlier version of the network.
Refining and Resetting Scores
You can run sprank.py more than once on the same database. A later run starts with the scores produced by the earlier run and iterates again, allowing further refinement when additional convergence is needed.
Common Diagnostic Mistakes
Assuming one iteration is enough
The initial estimates may still be changing substantially, and PageRank is designed to refine scores over multiple passes.
Fix:
Compare the average change across successive iterations and continue until the change is very small for the calculation's needs.Treating a large PageRank value as universal
PageRank scores in the source example are relative to the pages in the same network.
Fix:
Interpret scores by comparing pages within the same stored network.Rerunning ranking without noticing changed page data
The scores may no longer describe the current link structure.
Fix:
Run sprank.py again so the rankings can reconverge on the expanded network.Deleting the database to restart the calculation
The page records and link structure can be preserved while the scores are reset.
Fix:
Use spreset.py when you need to return PageRank values to their initial state without losing the network.
Practice Diagnosis
A ranking run reports average changes of 0.5, then 0.2, then 0.05, then 0.01. Explain what this pattern suggests. Next, decide whether you would use another ordinary sprank.py run or spreset.py if the page database has not changed but you want to refine the existing scores. Finally, explain what action you would take after spider.py adds new pages and links.
Hints
- Focus on whether the average changes are becoming smaller.
- A repeated run can continue from existing scores.
- A new crawl changes the network that the ranking describes.
What do you think happens?
If PageRank average changes keep decreasing across iterations, what should you expect about the scores?
Reveal answer
Answer: They are moving toward a stable state
The source describes decreasing average change as evidence that PageRank scores are stabilizing. Very small changes indicate convergence, not that every page receives the same score.
Key Takeaways
- sprank.py calculates PageRank by repeatedly processing the page and link structure stored in the database.
- The average change after each iteration shows whether scores are still shifting substantially or are approaching stability.
- PageRank output can include scores as well as page IDs, version information, outgoing-link counts, and URLs.
- Repeated runs refine existing scores, while new crawled pages and links require ranking to be recalculated for the expanded network.
- spreset.py clears PageRank values without removing the stored pages or links, allowing a fresh calculation on the same network.
Key Takeaways
- PageRank transforms a database of pages and links into relative importance scores.
- Each iteration is a complete pass through the pages, and decreasing average changes indicate movement toward convergence.
- Scores should be interpreted within the same network and examined alongside record metadata.
- Repeated ranking runs refine existing values, while new crawling requires recalculation on the changed network.
- Use spreset.py to clear scores while preserving the page and link structure before starting a fresh ranking calculation.