Link Analysis and Network Structure
A PageRank score is relative to the other pages in the same network. A higher score means that the page is considered more important according to the link structure stored in the database.
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 producing final rankings in one immediate pass, the program repeatedly examines the link structure and refines each page's score using the scores from the previous iteration.
A PageRank score is relative to the other pages in the same network. A higher score means that the page is considered more important according to the link structure stored in the database.
The Iteration Cycle
- 1Invoke
sprank.pyand provide the number of iterations to perform. - 2The program makes one complete pass through the pages in the database.
- 3It recalculates page scores using the results from the previous iteration.
- 4It reports the iteration number and the average change in PageRank score per page.
- 5It repeats the process for the requested number of iterations.
The average change is the main progress signal. In the source example, a calculation over five pages reports an average change of 0.547 after the first iteration and 0.227 after the second. The decrease means that the scores changed less during the second pass. A continuing decrease toward a very small value indicates that the rankings are stabilizing.
Importance Flow Through Links
The link network creates a feedback loop. A page can gain importance when it receives links from pages that themselves have high scores. During each iteration, this information propagates through the network, so the algorithm repeatedly adjusts the scores instead of relying only on the number of incoming links.
Reading the Output
Comparing PageRank Scores
Interpret a set of PageRank scores produced for pages in one network.
- 1Find the largest score
Page 4 has a score of 2.135, the highest value in the listed results.
- 2Compare the middle values
Pages 2 and 5 are tied at 0.659.
- 3Compare the lower value
Page 1 has a score of 0.559, slightly below the scores for pages 2 and 5.
- 4Interpret the ordering
Within this network, Page 4 is ranked as more important than the other listed pages according to the stored link structure.
The values are relative rankings for pages in the same network, not universal importance values that can be compared directly with scores from a different network.
| Output information | What it tells you |
|---|---|
| Page ID | Which 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 stored in the record |
| Version number | The record's version information, shown in the detailed database record |
PageRank output can appear as simple score tuples or as detailed database records.
Repeated Runs and Refinement
A single run does not have to be the end of the process. You can run sprank.py multiple times on the same database. A later run starts with the scores produced by the earlier run and iterates again, allowing the rankings to converge further when additional refinement is needed.
A second run can refine convergence, but it does not replace the need to inspect the average change. The metric tells you whether additional passes are still making meaningful adjustments.
Crawling Before Ranking
PageRank can be combined with crawling as an ongoing workflow. spider.py crawls new pages and adds them to the database. sprank.py can then recalculate the scores using the expanded collection of pages and links, allowing the rankings to reflect the updated network.
Resetting the Calculation
Use spreset.py when you need to restart PageRank from its initial state without crawling all the pages again. The reset clears the stored PageRank values but preserves the page records and the links between them. You can then run sprank.py from the beginning on the same network structure.
- Continue or repeat ranking when the average change is still large and the scores are still shifting noticeably.
- Treat very small average changes as evidence that the rankings have stabilized.
- Run
sprank.pyagain afterspider.pyadds pages or links. - Use
spreset.pybefore a fresh calculation when you want to test different parameters, verify results, or remove old score values while keeping the crawled network.
Common Diagnostic Errors
Common mistake Treating the first iteration as the final ranking
What it looks likeStopping after a pass that still reports a large average change
Why it failsEarly iterations make significant corrections to the initial estimates.
Do this insteadCompare the average change across iterations and continue until the changes become very small.
Common mistake Reading a score as an absolute measure of importance
What it looks likeAssuming a score from one network can be directly compared with a score from another network
Why it failsPageRank scores are relative to the other pages in the same network.
Do this insteadUse the scores to compare pages within the database that produced them.
Common mistake Ignoring the link structure behind the score
What it looks likeLooking only at a page's number without considering incoming and outgoing links
Why it failsPageRank is calculated from the link structure, and detailed records include outlink counts to provide topology context.
Do this insteadInspect the page's score together with its link-related metadata.
Common mistake Assuming a crawl automatically updates existing rankings
What it looks likeRunning spider.py and then using old rankings without another PageRank calculation
Why it failsNew pages and links change the network being ranked.
Do this insteadRun sprank.py again after the crawl.
Common mistake Resetting the database when only the scores need restarting
What it looks likeDiscarding crawled pages and links to begin PageRank again
Why it failsspreset.pyis designed to clear PageRank values while preserving page records and link structure.Do this insteadUse spreset.py when you need a fresh calculation on the same network.
Check Your Interpretation
A two-iteration run reports an average change of 0.547 after the first iteration and 0.227 after the second. Explain what this decrease suggests, whether the rankings should automatically be called fully converged, and what evidence you would inspect before deciding to stop.
Hints
- The average change measures how much scores shift per page during an iteration.
- A decrease indicates stabilization, but convergence is associated with changes becoming very small.
- Consider whether later iterations would still be useful.
Your crawler adds new pages and links to the database. Describe the next program you would run, what it should recalculate, and when spreset.py would be appropriate instead.
Hints
- New links change the network being ranked.
- A fresh ranking run should account for the expanded network.
- A reset clears scores but keeps pages and links.
Stable Rankings in Practice
- 1
sprank.pyiteratively transforms stored pages and links into PageRank scores. - 2The average change reported after each iteration shows whether the scores are still moving substantially.
- 3A declining average change indicates convergence; very small changes indicate stable, reliable rankings.
- 4Scores are relative to the pages in the same network, and output can include page IDs, scores, outlink counts, URLs, and version information.
- 5Run PageRank again after crawling changes the network, and use
spreset.pyto clear old scores without deleting the stored pages and links.
Key Takeaways
- PageRank uses repeated passes over a database's link structure to calculate relative page importance.
- The average change per iteration is the key signal for recognizing convergence.
- Repeated runs can refine scores, while new crawls require rankings to be recalculated.
spreset.pyrestarts the score calculation without removing the page and link network.