GROUP 2
PAGE RANKING
ALGORITHMS
2025
WHY PAGE RANKING ALGORITHMS?
Page ranking algorithms help put forward
most relevant and trusted pages to give us
best exploring experience
WHAT ARE PAGE RANKING ALGORITHMS
Page ranking algorithms see the connections
between nodes/pages and assign scores to
them. These scores help understand
relevance and popularity in pages and gives
them rankings based on these scores.
PageRank
PageRank (PR) is an algorithm used by Google Search to
rank websites in their search engine results. PageRank
works by counting the number and quality of links to a
page to determine a rough estimate of how important the
website is. The underlying assumption is that more
important websites are likely to receive more links from
other websites.
One way to think about PageRank is to
imagine a random surfer on the web, following
links from page to page. The page rank of any
page is roughly the probability that the
random surfer will land on a particular page.
Since more links go to the important pages,
the surfer is more likely to end up there.
The behavior of the random surfer is an
example of a Markov process, which is any
random evolutionary process that depends
only of the current state of a system and not
on its history
The PageRank
Algorithm
in Theory
01 Start with a set of pages
02 Crawl the web to determine the link structure
03 Assign each page an initial rank of 1 / N.
04 Successively update the rank of each page by adding up the weight of
every page that links to it divided by the number of links emanating
from the referring page.
In the current example, page E has two
incoming links, one from page C and one from
page D.
Page C contributes 1/3 of its current page rank
to page E because E is one of three links from
page C. Similarly, page D offers 1/2 of its rank to
E.
The new page rank for E is PR(E) = PR(C)/3 +
PR(D)/2 = 0.2/3 + 0.2/2 = 0.17
05 If a page (such as E in the current example) has no outward links,
redistribute its rank equally among the other pages in the graph.
In this graph, 1/4 of E’s page rank is distributed
to pages A, B, C, and D.
The idea behind this model is that users will
keep searching if they reach a dead end.
06 Apply this redistribution to every page in the graph.
Repeat this process until the page ranks stabilize.
Hyperlink Induced Topic
Search (HITS) Algorithm
HITS algorithm uses the link structure of the web in order to discover
and rank pages relevant for a particular topic.
It operates on the principle that certain web pages serve as "hubs" and
others as "authorities."
Authorities: Pages that provide valuable and authoritative information
on a specific topic. They are often linked to by many "hub" pages.
Hubs: Pages that act as directories or compilations of links, pointing to
multiple authoritative pages on a given topic.
How does it work?
01
Start with a root set.
Root set consists of
pages returned by a
basic keyword search.
How does it work?
02
Expand the root set by
including all pages that
the root set pages link to
and all the pages that link
to the root set pages.
This forms the base set.
How does it work?
03
Initialize authority and
hub scores.
Authority Score = 1
Hub Score = 1
How does it work?
04
Now, the algorithm runs iteratively
updating scores based on the
following rules:
Authority update:
A page’s new authority score =
sum of the hub scores of all
pages that link to it.
Hub update:
A page’s new hub score = sum
of the authority scores of all
pages it links to.
How does it work?
05
After updating, scale the scores so
that:
The sum of the squares of all
authority scores = 1.
The sum of the squares of all
hub scores = 1.
This prevents scores from growing
infinitely.
Repeat the update and
normalization steps until the
authority and hub scores stabilize.
The SALSA Algorithm
SALSA: Stochastic Approach for Link-Structure Analysis
Goal: To achieve the same goal as HITS (finding Hubs and Authorities)
but using a different, more robust mathematical method.
Problem with HITS: The algebraic method could sometimes be
manipulated or led astray by dense link structures (link spam).
SALSA's Solution: Replace the deterministic algebra with probability
and random walks (a Markov Process), making it more resilient.
SALSA's Core Concept: The Two Researchers
Forget math for a moment. Imagine a search engine has gathered a few
hundred pages on "vintage cars." SALSA sends in two "researchers" to
wander this collection.
Anna, the Authority Finder: Her goal is to find the most authoritative,
expert pages.
Henry, the Hub Finder: His goal is to find the best resource lists and
directories.
The pages that Anna and Henry visit most often are the winners
How SALSA Works, Step 1: Building the
Neighborhood
SALSA doesn't analyze the whole web. It creates a small, focused
"neighborhood" for each query.
[Link] Set: A standard search returns the top ~200 results for a query
(e.g., "vintage cars").
[Link] Set: This set is expanded by adding:
All pages the Root Set pages link to.
All pages that link to the Root Set pages.
This Base Set is the only thing SALSA analyzes.
The Authority Walk (Anna's Method)
To find the best Authorities, SALSA simulates a specific two-step random
walk:
[Link] at a random page in the neighborhood.
[Link] 1 (Go Backward): Follow a random backlink to a page that
recommended the current one.
[Link] 2 (Go Forward): From there, follow a random forward link.
The pages most frequently landed on after this two-step journey are the
Authorities.
Page A <-- (Backlink) -- Page B -- (Forward Link) --> Page C (Authority!)
The Hub Walk (Henry's Method)
To find the best Hubs, SALSA simulates the opposite two-step random
walk:
[Link] at a random page in the neighborhood.
[Link] 1 (Go Forward): Follow a random forward link to a page the
current one recommends.
[Link] 2 (Go Backward): From there, follow a random backlink.
The pages most frequently landed on after this journey are the Hubs.
A simple diagram: Page X -- (Forward Link) --> Page Y <-- (Backlink) --
Page Z (Hub!)
The Math Behind SALSA (Simplified)
SALSA's math uses the principles of Markov Processes, just like PageRank.
The Map: The neighborhood is represented by an Adjacency Matrix
(A).
The Authority Walk: This is modeled by a single Transition Matrix
M_auth, which mathematically represents the "backward-then-
forward" probability.
The Hub Walk: This is modeled by a different Transition Matrix M_hub,
representing the "forward-then-backward" probability.
The Authority Scores are the final, stable probabilities (the stationary
distribution) of the Authority Walk. The Hub Scores are the final, stable
probabilities of the Hub Walk.
The Authority Scores are the final, stable probabilities (the stationary
distribution) of the Authority Walk. The Hub Scores are the final, stable
probabilities of the Hub Walk.
Why SALSA? A More Robust Approach
Feature HITS SALSA
Linear Algebra
Method Probability (Markov Chains)
(Eigenvectors)
Can be manipulated
The random walk nature is more resistant to being
Robustness by dense, artificial
"trapped" by link spam.
link structures.
Can sometimes drift
Tends to stay more tightly focused on the original
Topic Drift to related but
query's topic.
irrelevant topics.
Conclusion
Link analysis algorithms revolutionized web search by treating links as
endorsements.
PageRank introduced a robust model for measuring global, query-
independent importance.
HITS pioneered the query-dependent model of finding topical Hubs
and Authorities.
SALSA refined this model, using the mathematics of Markov Chains to
provide a more robust and stable method for identifying these topic-
specific experts.
Understanding these different philosophies is key to understanding
the evolution of information retrieval on the web.
THANK YOU!