---
title: "Page ranking algorithm"
subject: "Data Mining"
chapter: 7
key: "semester_7/data_mining:page-ranking"
source: https://www.bctengineer.com/q/semester_7/data_mining/page-ranking
site: BCT Engineering
---

# Page ranking algorithm

Data Mining · Chapter 7: Advanced Applications

- Asked in: year not given
- Video: [#1. Page Rank Algorithm Solved Example Page Rank Data Mining Machine Learning by Vidya Mahesh Huddar](https://www.youtube.com/watch?v=C4ESsZWWmKU) — Vidya Mahesh Huddar and Mahesh Huddar
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/page-ranking
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-7

## Question

Briefly explain the page ranking algorithm.

## Short answer

PageRank ranks pages by importance using the hyperlink graph: a page is important if many important pages link to it. It is computed iteratively as PR(P) = (1-d) + d times the sum of PR(Ti)/C(Ti), with damping factor usually 0.85. It represents random-surfer probability and is query-independent.

## Answer

**PageRank** is a link analysis algorithm (Brin and Page, Google) that ranks web pages by their importance, computed from the hyperlink structure of the web. The idea: a page is important if many important pages link to it. A link from page A to page B is like a "vote" by A for B; votes of important pages count more, and a page's vote is shared among all its outgoing links.

#### Formula
PR(P) = (1 − d) + d × Σ [ PR(Tᵢ) / C(Tᵢ) ]

- Tᵢ = the pages linking to P (in-links)
- C(Tᵢ) = number of outgoing links of Tᵢ
- d = damping factor (usually 0.85): the probability that a random surfer follows a link; 1 − d is the chance of jumping to a random page.

PageRank is the probability of a random surfer being on the page; it is computed **iteratively** until the values converge.

#### Example
Pages A, B, C with links A → B, A → C, B → C, C → A. Start with PR = 1 for all; d = 0.85.
- PR(A) = 0.15 + 0.85·PR(C)/1
- PR(B) = 0.15 + 0.85·PR(A)/2
- PR(C) = 0.15 + 0.85·(PR(A)/2 + PR(B)/1)

| Iteration | PR(A) | PR(B) | PR(C) |
| --- | --- | --- | --- |
| 0 | 1.000 | 1.000 | 1.000 |
| 1 | 1.000 | 0.575 | 1.425 |
| 2 | 1.361 | 0.575 | 1.064 |
| 3 | 1.054 | 0.729 | 1.217 |
| converged | 1.163 | 0.644 | 1.192 |

(Each iteration uses the values from the previous one; the sum is always 3, the number of pages.) C and A are the more important pages.

#### Notes
Rank sinks (groups of pages that link only to each other) are handled by the damping factor, i.e. the random jump; dangling pages (no out-links) are usually treated as linking to all pages, so their rank is spread evenly. PageRank is query-independent and is combined with content relevance in a search engine. It is a web structure mining technique; HITS (hubs and authorities) is another.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In PageRank, how is a page's vote distributed?
   A. Shared among all its outgoing links
   B. Fully given to every linked page
   C. Given only to the first link
   D. Kept by the page
   Answer: A. A page's vote is divided by its number of outgoing links C(T). (Key point: Idea)

2. In PR(P) = (1 - d) + d x sum PR(Ti)/C(Ti), what is d?
   A. The number of in-links
   B. The damping factor (usually 0.85), the probability of following a link
   C. The number of pages
   D. The convergence threshold
   Answer: B. d is the chance a random surfer follows a link; 1 - d is a random jump. (Key point: Formula)

3. How is PageRank computed?
   A. In one pass with no iteration
   B. Iteratively until the values converge
   C. By counting words
   D. By counting visitors
   Answer: B. It is iterated until values stop changing. (Key point: Computation)

4. In the example with links A->B, A->C, B->C, C->A, what is PR(A) after iteration 1 starting from all 1?
   A. 0.575
   B. 1.425
   C. 1.000
   D. 0.150
   Answer: C. PR(A) = 0.15 + 0.85 x PR(C)/1 = 0.15 + 0.85 = 1.0. (Key point: Example)

## Related in other subjects

- [LRU algorithm; page faults on string](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Alru-page-faults-ref-string) — Operating System, chapter 4
- [Race condition; optimal page replacement limits](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-condition-optimal-limitation) — Operating System, chapter 3
- [Page faults: LRU, FIFO, Optimum](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-faults-lru-fifo-optimum) — Operating System, chapter 4