Graph Mining – 1 | 04. HITS and PageRank — Part 1 (Q&A)

AI Generated Answers. The original questions generally came from this blog and are attributed to Sayed Ahmed. New AI-generated answers and examples are offered for reuse without copyright restrictions asserted by this site; linked third-party content retains its own terms. Validate results before applying them.

Course index · Original questions: HITS questions and related repost · This part answers 04.01–04.25.

Important convention: A[i,j] indicates an edge from page i to page j. Consequently, HITS updates hub scores with A and authority scores with Aᵀ. A PageRank transition matrix is row-stochastic and is a different object.

Q04.01. What is HITS algorithm in Graph Mining esp. for Web?

Answer. HITS is a link-analysis algorithm introduced by Jon Kleinberg that ranks pages in a hyperlink graph using mutually reinforcing hub and authority scores. A good hub links to good authorities; a good authority receives links from good hubs.

Q04.02. What does HITS stand for?

Answer. HITS means Hyperlink-Induced Topic Search.

Q04.03. What is another similar Algorithm?

Answer. PageRank is a well-known related link-ranking algorithm. SALSA is another algorithm combining ideas from hyperlink ranking and random walks.

Q04.04. What are different between the PageRank algorithm and HITS?

Answer. HITS computes two coupled scores per node (hub and authority), usually on a topic-relevant subgraph; PageRank computes one importance score via a random-walk/teleportation model, often on a much larger link graph. They use hyperlinks differently, so their rankings need not match.

Q04.05. What is the PageRank algorithm? What is the purpose?

Answer. PageRank estimates a node’s importance using links from other nodes and their own importance. It models a random surfer who follows links most of the time and teleports occasionally; nodes visited more often have higher stationary probability.

Q04.06. Where and how PageRank is used?

Answer. PageRank historically helped rank web pages. It is also useful for citation graphs, recommendation and trust/reputation-like analysis, influence proxies, and node prioritization. It is one signal, not a complete measure of source quality.

Q04.07. Where and how HITS is used?

Answer. HITS is useful for finding curated link directories (hubs) and highly endorsed topical sources (authorities), such as pages about universities or technical documentation. It is sensitive to graph construction and manipulation; the score is not a proof of factual credibility.

Q04.08. Describe HITS?

Answer. Build a directed hyperlink graph. Initialize hub and authority vectors, repeatedly update authorities from incoming hubs and hubs from outgoing authorities, normalize, and stop when changes become small or a fixed iteration limit is reached.

Q04.09. Describe the PageRank algorithm.

Answer. Construct a row-stochastic transition matrix from outgoing hyperlinks, handle dangling nodes, and iteratively update rank using r_next = αPᵀr + (1−α)v. Here v is the teleportation distribution (often uniform), α usually around 0.85, and r sums to one.

Q04.10. What are the two core concepts in HITS algorithm?

Answer. The two concepts are hubs—pages pointing to valuable pages—and authorities—pages pointed to by valuable hubs.

Q04.11. Web-pages that serves as large directories of other pages with useful information – what are they called in HITS algorithm?

Answer. They are hubs. A page curating links to many strong resources can receive a high hub score.

Q04.12. Web-pages that serves to provide information on Specific topics – what are they called in the HITS algorithm?

Answer. They are authorities when useful topic-relevant pages receive strong incoming endorsements. A source can simultaneously function as a hub if it also provides helpful outgoing links.

Q04.13. What are HUBs in HITS algorithm? What purpose do they serve?

Answer. Hub pages guide a user toward strong resources and point to high-authority nodes. Their score depends on the authority scores of their outgoing neighbors, not merely the raw number of links.

Q04.14. What are Authorities in HITS algorithm? What purpose do they serve?

Answer. Authority pages provide content considered prominent in the graph because strong hubs link to them. The model scores endorsement by link structure, not objective truth or safety.

Q04.15. Compare HITS and PageRank.

Answer. Both use directed links. HITS uses mutually reinforcing hub/authority eigenvectors; PageRank uses a damped Markov chain. HITS is often applied to query-focused sets and can show topic drift; PageRank with teleportation gives a stable global stationary distribution for a fixed graph and teleport vector.

Q04.16. A web-page containing links to Top 1000 Universities in the world – is this a HUB or Authority in HITS?

Answer. Typically a hub, since it is primarily a directory of links to university sites. If other hubs link to the directory and it contains substantial information, it can have an authority score too.

Q04.17. What is the Govt. of Canada website that provides information on all Govt. Services? Is this a Hub or an Authority?

Answer. A government service directory or portal can be a hub because it links to many services. The specific agency pages can act as authorities. A real score requires an actual hyperlink graph; the domain alone does not determine it.

Q04.18. How do you measure a Good Hub?

Answer. A good hub links to strong authorities. In HITS, h_i = Σ_{i→j} a_j before normalization. A high outgoing degree can help, but link quality matters.

Q04.19. How do you measure a Good Authority?

Answer. A good authority receives hyperlinks from strong hubs. In HITS, a_j = Σ_{i→j} h_i before normalization. Link count alone does not fully define the score.

Q04.20. Can a web-page be both Hub and Authority? Can you assign both measures to a page irrespective of how good or bad?

Answer. Yes. Each vertex can have both hub and authority coordinates, even if one is zero or weak. For example, a university’s comprehensive resource portal may be both a recognized information source and a directory.

Q04.21. What are the two scores that HITS assign to a web-page?

Answer. Each page receives a hub score and an authority score.

Q04.22. What is authority score for a web-page?

Answer. The authority score measures how strongly a page is endorsed by hub-like pages linking into it. With row-as-source adjacency matrix A, a_next = Aᵀh.

Q04.23. What is the hub score for a web-page?

Answer. The hub score measures how strongly a page points toward authority-like pages. With row-as-source adjacency matrix A, h_next = Aa.

Q04.24. What does hub score measure?

Answer. The quality of a page as an outgoing-link directory into highly authoritative destinations.

Q04.25. What does authority score measure?

Answer. The quality of a page as an incoming-link destination endorsed by strong hubs.

Leave a Reply