Ranking Algorithms and Search Engine Fundamentals
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.
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 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.
- 1First 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.
- 2Second 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.
- 3Interpretation
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.
Page records and link structure are present. PageRank scores contain earlier calculated values.
Existing PageRank values are available for another refining run.
Run spreset.py. Page records and link structure remain. PageRank values return to their initial state.
Scores are cleared without removing the crawled pages or their links.
Common Diagnostic Mistakes
Common mistake Assuming one iteration is enough
What it looks likeStopping after the first reported average change
Why it failsThe initial estimates may still be changing substantially, and PageRank is designed to refine scores over multiple passes.
Do this insteadCompare the average change across successive iterations and continue until the change is very small for the calculation's needs.
Common mistake Treating a large PageRank value as universal
What it looks likeComparing a score from one database directly with a score from an unrelated network
Why it failsPageRank scores in the source example are relative to the pages in the same network.
Do this insteadInterpret scores by comparing pages within the same stored network.
Common mistake Rerunning ranking without noticing changed page data
What it looks likeUsing old scores after spider.py has added pages or links
Why it failsThe scores may no longer describe the current link structure.
Do this insteadRun sprank.py again so the rankings can reconverge on the expanded network.
Common mistake Deleting the database to restart the calculation
What it looks likeRemoving page records when only the PageRank values need to be cleared
Why it failsThe page records and link structure can be preserved while the scores are reset.
Do this insteadUse 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
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
- 1
sprank.pycalculates PageRank by repeatedly processing the page and link structure stored in the database. - 2The average change after each iteration shows whether scores are still shifting substantially or are approaching stability.
- 3PageRank output can include scores as well as page IDs, version information, outgoing-link counts, and URLs.
- 4Repeated runs refine existing scores, while new crawled pages and links require ranking to be recalculated for the expanded network.
- 5
spreset.pyclears PageRank values without removing the stored pages or links, allowing a fresh calculation on the same network.
At a glance
- 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.pyto clear scores while preserving the page and link structure before starting a fresh ranking calculation.