Advantages
1. Topic-specific rankings: HITS generates rankings that are specific to a particular topic, ensuring that the most relevant & authoritative pages for that topic are surfaced.
2. Mutually reinforcing relationship: The hub & authority scores in HITS reinforce each other. Good hubs boost the authority scores of the pages they link to, while good authorities boost the hub scores of the pages that link to them. This helps identify the most important pages.
3. Spam resistance: HITS is relatively resistant to spam because it relies on the structure of the web graph & the relationships between pages, rather than just the content or keywords on a page. This makes it harder for spammers to manipulate rankings.
4. Efficient computation: The iterative nature of HITS allows it to be computed efficiently, even for large sets of web pages. This is important for search engines that need to rank millions or billions of pages.
5. Complementary to other algorithms: HITS can be used in conjunction with other ranking algorithms, such as PageRank, to provide a more comprehensive & robust ranking of web pages.
Algorithm
The HITS algorithm involves the following steps:
1. Start with a set of web pages relevant to a specific topic. This can be obtained through a keyword search or other methods.
2. Construct a directed graph representing the hyperlink structure of the web pages, where each page is a node & each hyperlink is a directed edge.
3. Initialize the hub & authority scores of each page to 1.
4. Iteratively update the scores until convergence:
- For each page, update its authority score to be the sum of the hub scores of the pages that link to it.
- For each page, update its hub score to be the sum of the authority scores of the pages it links to.
- Normalize the scores by dividing each score by the square root of the sum of the squares of all scores of the same type (hub or authority).
5. After convergence, the pages with the highest authority scores are considered the most important & relevant for the topic, while the pages with the highest hub scores are the best hubs for finding relevant content.
Implementation in Python
import numpy as np
def hits(graph, max_iterations=100, tolerance=1e-8):
n = len(graph)
hub = np.ones(n)
authority = np.ones(n)
for _ in range(max_iterations):
prev_hub = hub.copy()
prev_authority = authority.copy()
hub = np.dot(graph, authority)
authority = np.dot(graph.T, hub)
hub /= np.linalg.norm(hub)
authority /= np.linalg.norm(authority)
if np.linalg.norm(hub - prev_hub) < tolerance & np.linalg.norm(authority - prev_authority) < tolerance:
break
return hub, authority
This code takes a graph represented as an adjacency matrix & iteratively updates the hub & authority scores until convergence or a maximum number of iterations is reached.
Frequently Asked Questions
How does the HITS algorithm differ from PageRank?
While both algorithms rank web pages, HITS computes topic-specific scores (hubs & authorities), whereas PageRank calculates a global importance score for each page.
Can the HITS algorithm be used for purposes other than web search?
Yes, HITS can be applied to any network or graph where the importance of nodes needs to be determined based on their relationships, such as social networks or citation networks.
What are some limitations of the HITS algorithm?
HITS can be sensitive to the initial set of pages & may not handle topic drift well. It also does not consider the content or quality of the pages, only their link structure.
Conclusion
In this article, we learned about the HITS algorithm, a link analysis method used to rank web pages based on their importance & relevance to a specific topic. We discussed how HITS assigns hub & authority scores to pages & iteratively updates them based on the hyperlink structure of the web graph. We also talked about the advantages of HITS. Finally, we looked at the code implementation in Python.
You can also check out our other blogs on Code360.
310+ registered 
