Practical 9
Implementation of HITS Algorithm
Aim:
To implement the HITS (Hyperlink-Induced Topic Search) algorithm and analyze authority
and hub scores for a given web graph.
Theory:
The HITS algorithm, proposed by Jon Kleinberg in 1999, is used to rank web pages based on
the concepts of authority and hub. Unlike PageRank (which gives one importance score per
page), HITS assigns two scores to each page:
• Authority score – Measures the value of the page as a source of information.
• Hub score – Measures the value of the page as a directory that links to authoritative pages.
The mutual reinforcement principle states:
• A good hub points to good authorities.
• A good authority is pointed to by good hubs.
Mathematically:
Authority Update: a = A^T * h
Hub Update: h = A * a
Where A is the adjacency matrix of the web graph. Normalization is applied after each
iteration.
Algorithm / Steps:
1. Represent the web graph using an adjacency matrix A.
2. Initialize all authority and hub scores to 1.
3. Update authority scores: a = A^T * h.
4. Update hub scores: h = A * a.
5. Normalize both authority and hub vectors.
6. Repeat steps 3–5 until convergence (scores stabilize).
7. Identify nodes with highest authority and hub values.
Python Implementation:
import numpy as np
def hits_algorithm(adj_matrix, max_iter=100, tol=1e-6):
n = adj_matrix.shape[0]
auth = [Link](n)
hub = [Link](n)
for _ in range(max_iter):
new_auth = adj_matrix.T @ hub
new_hub = adj_matrix @ new_auth
# Normalize
new_auth = new_auth / [Link](new_auth, 2)
new_hub = new_hub / [Link](new_hub, 2)
# Check convergence
if [Link](auth, new_auth, atol=tol) and [Link](hub, new_hub, atol=tol):
break
auth, hub = new_auth, new_hub
return auth, hub
# Example Graph
A = [Link]([[0,1,1,0],
[0,0,1,0],
[0,1,0,0],
[0,0,1,0]])
authority, hub = hits_algorithm(A)
print("Authority Scores:", authority)
print("Hub Scores:", hub)
Sample Output:
Authority Scores: [0.000, 0.525, 0.851, 0.000]
Hub Scores: [0.724, 0.447, 0.276, 0.447]
Conclusion:
The HITS algorithm successfully computes two types of scores: Authority and Hub. In the
given example, Node 2 emerged as the best authority (strongest content page), while Node
0 emerged as the best hub (strongest connector). This demonstrates the mutual
reinforcement nature of the HITS algorithm.