Differentiate between Page Rank & HITS algorithm.

Question

Doubtly · Accepted Answer

Criteria PageRank HITS (Hyperlink-Induced Topic Search) Purpose Measures the importance of web pages based on link structure. Identifies authority and hub pages in a network. Algorithm Type Link Analysis Link Analysis Developed by Larry Page and Sergey Brin (Google) Jon Kleinberg (Cornell University) Key Idea Pages with more incoming links are more important. Authority pages link to many hub pages, and hub pages link to many authority pages. Computation Method Iterative algorithm that assigns a PageRank score to each page. Iterative algorithm that computes two scores: authority and hub scores. Scoring Metric PageRank score for each page. Authority and hub scores for each page. Output Rank pages by importance. Identify authority and hub pages. Dangling Nodes Handling Typically handled by redistributing their PageRank. Often ignored in HITS. Convergence Usually converges slowly. Can converge faster than PageRank. Query-Dependent PageRank scores are query-independent. HITS can be adapted for query-specific searches. Use in Search Engines Used by Google and many other search engines. Less commonly used in modern search engines. Vulnerability to Manipulation Susceptible to link spam and link manipulation. Less susceptible to manipulation, as it focuses on the structure of the network.

Tutor AI · Answer

PageRank gives every page one query-independent importance score from the whole web's link graph; HITS gives each page two scores (hub and authority) computed on a small query-specific subgraph. PointPageRankHITS Proposed byLarry Page and Sergey Brin (1998, Google)Jon Kleinberg (1998–99) ScoresOne score per page (PageRank)Two scores per page: hub and authority IdeaA page is important if important pages link to it (random surfer model)A good hub points to many good authorities; a good authority is pointed to by many good hubs Query dependenceQuery-independent, computed offline for the whole webQuery-dependent: run at query time on a root set of results plus pages linked to/from them Graph usedEntire web graphSmall focused subgraph Links usedOnly in-links (with damping factor d≈ 0.85 )Both in-links (authority) and out-links (hub) Speed at query timeFast, scores already storedSlower, scores computed per query Spam resistanceMore resistant (needs links from important pages)Easier to manipulate, e.g. by adding out-links to make a page a hub Topic driftNot an issueCan drift to a different topic if the subgraph is dominated by off-topic pages UseGoogle search rankingEarlier used in Teoma/Ask.com Formulas: PageRank PR(P) = 1-d/N + dΣ_(Q→ P)PR(Q)/L(Q) . HITS updates repeatedly: authority a(p)=Σ_(q→ p) h(q) , hub h(p)=Σ_(p→ q) a(q) , normalising after each step.

Differentiate between Page Rank & HITS algorithm.

2 answers

Your answer

Criteria	PageRank	HITS (Hyperlink-Induced Topic Search)
Purpose	Measures the importance of web pages based on link structure.	Identifies authority and hub pages in a network.
Algorithm Type	Link Analysis	Link Analysis
Developed by	Larry Page and Sergey Brin (Google)	Jon Kleinberg (Cornell University)
Key Idea	Pages with more incoming links are more important.	Authority pages link to many hub pages, and hub pages link to many authority pages.
Computation Method	Iterative algorithm that assigns a PageRank score to each page.	Iterative algorithm that computes two scores: authority and hub scores.
Scoring Metric	PageRank score for each page.	Authority and hub scores for each page.
Output	Rank pages by importance.	Identify authority and hub pages.
Dangling Nodes Handling	Typically handled by redistributing their PageRank.	Often ignored in HITS.
Convergence	Usually converges slowly.	Can converge faster than PageRank.
Query-Dependent	PageRank scores are query-independent.	HITS can be adapted for query-specific searches.
Use in Search Engines	Used by Google and many other search engines.	Less commonly used in modern search engines.
Vulnerability to Manipulation	Susceptible to link spam and link manipulation.	Less susceptible to manipulation, as it focuses on the structure of the network.

Point	PageRank	HITS
Proposed by	Larry Page and Sergey Brin (1998, Google)	Jon Kleinberg (1998–99)
Scores	One score per page (PageRank)	Two scores per page: hub and authority
Idea	A page is important if important pages link to it (random surfer model)	A good hub points to many good authorities; a good authority is pointed to by many good hubs
Query dependence	Query-independent, computed offline for the whole web	Query-dependent: run at query time on a root set of results plus pages linked to/from them
Graph used	Entire web graph	Small focused subgraph
Links used	Only in-links (with damping factor \(d\approx 0.85\))	Both in-links (authority) and out-links (hub)
Speed at query time	Fast, scores already stored	Slower, scores computed per query
Spam resistance	More resistant (needs links from important pages)	Easier to manipulate, e.g. by adding out-links to make a page a hub
Topic drift	Not an issue	Can drift to a different topic if the subgraph is dominated by off-topic pages
Use	Google search ranking	Earlier used in Teoma/Ask.com