#1. Page Rank Algorithm Solved Example Page Rank Data Mining Machine Learning by Vidya Mahesh Huddar

Main ideas, concepts, and lessons

• Purpose of PageRank

  • PageRank is an algorithm (originally developed by Larry Page and Sergey Brin, referenced as “Larry page and brain”).
  • It is used to rank web pages for search engine results.
  • It assigns a score to each page based on:
    • How many links point to it, and
    • How important those linking pages are (links from higher-ranked pages contribute more).

• Problem setup (web graph)

  • The example web graph has 4 pages: A, B, C, D.
  • Link structure described:
    • A → B, C
    • B → C
    • C → A and (unclear wording about C → D)
      • The subtitle suggests: “C links to webpage A” and mentions “web page D links to webpage A,” but the exact presence of C → D is unclear.
    • D → A
  • The algorithm uses:
    • Number of pages (N) = 4
    • Damping factor (d) = 0.85 (probability a user continues clicking links)

• PageRank formula (as stated)

  • For a page P:
    • PR(P) = (1 − d)/N + d × Σ [ PR(Q) / L(Q) ]
  • Where:
    • Q ranges over pages that link to P (set M(P) in the subtitle)
    • L(Q) is the number of outbound links from page Q

• Initial PageRank values

  • Initially, all pages start with:
    • PR(A) = PR(B) = PR(C) = PR(D) = 1/N = 1/4 = 0.25

• Iteration process and convergence

  • Compute iteration 1 using the initial values.
  • Compute iteration 2 using iteration 1 values.
  • Continue until convergence, defined as:
    • When the difference between iterations is below 0.001
  • The subtitle claims convergence occurs after about five iterations.

• Final ranking takeaway

  • By the converged PageRank scores, the relative importance is:
    • C highest, then B, then (D)
  • The subtitle implies D is lowest, and A’s final position is not clearly stated in the final ordering beyond intermediate steps.

Note: Some link-direction details (especially involving C → D) and some numeric/transcription text in the subtitles appear unclear.

---

Methodology / step-by-step instructions (as presented)

• Step 1: Define the graph and constants

  • Identify pages: A, B, C, D
  • Determine link relationships (incoming/outgoing) for each node
  • Set:
    • N = 4
    • d = 0.85

• Step 2: Use the PageRank equation for each page

  • For each target page P, determine:
    • The set of pages Q that link to P (incoming links)
    • For each such Q, compute L(Q) = number of outbound links from Q
  • Substitute into:
    • PR(P) = (1 − d)/N + d × Σ [ PR(Q) / L(Q) ]

• Step 3: Initialize PageRank

  • Set:
    • PR(A)=PR(B)=PR(C)=PR(D)=0.25

• Step 4: Compute iteration 1

  • Plug initial values (0.25) into the page equations.
  • Provided results:
    • PR(A) ≈ 0.4625
    • PR(B) ≈ 0.14375
    • PR(C) ≈ 0.35625
    • PR(D) ≈ 0.0375

• Step 5: Compute iteration 2

  • Plug iteration-1 values into the same equations.
  • Provided results:
    • PR(A) = 0.37219
    • PR(B) = 0.09568
    • PR(C) = 0.39463
    • PR(D) = 0.0375

• Step 6: Repeat until convergence

  • Continue iterations, each time using the latest PageRank values.
  • Stop when iteration-to-iteration change < 0.001.
  • The subtitle states convergence occurs by around the 5th iteration.

• Step 7: Interpret the final ranks

  • The converged PageRank indicates relative importance:
    • C most important, then B, then D
  • A’s final position is not clearly stated in the subtitle.

---

Speakers / sources featured

• Speaker: Not explicitly named in the subtitles (narration by an unspecified presenter).
• Algorithm origin cited: Larry Page and Sergey Brin (referenced as “Larry page and brain”).