Algoritmo de búsqueda de tema inducido por hipervínculo (HITS) utilizando el módulo Networxx | Python

El algoritmo de búsqueda de temas inducidos por hipervínculos (HITS) es un algoritmo de análisis de enlaces que califica las páginas web, desarrollado por Jon Kleinberg. Este algoritmo se utiliza en las estructuras de enlaces web para descubrir y clasificar las páginas web relevantes para una búsqueda en particular. 
HITS utiliza concentradores y autoridades para definir una relación recursiva entre páginas web. Antes de comprender el Algoritmo HITS, primero debemos conocer los Hubs y las Autoridades.
 

• Dada una consulta a un Motor de Búsqueda, el conjunto de páginas web de gran relevancia se denominan Raíces . Son Autoridades potenciales .
• Las páginas que no son muy relevantes pero apuntan a páginas en la Raíz se llaman Hubs . Por lo tanto, una Autoridad es una página a la que se vinculan muchos centros, mientras que un Centro es una página que se vincula a muchas autoridades.

Algoritmo – 
 

-> Sea k el número de iteraciones . 
-> A cada Node se le asigna una puntuación de Hub = 1 y una puntuación de Autoridad = 1.
-> Repetir k veces: 
 

• Actualización del concentrador: la puntuación del concentrador de cada Node =  (puntuación de autoridad de cada Node al que apunta).
• Actualización de autoridad: puntuación de autoridad de cada Node =  (puntuación de concentrador de cada Node que apunta a él).
• Normalice los puntajes dividiendo cada puntaje de Hub por la raíz cuadrada de la suma de los cuadrados de todos los puntajes de Hub, y dividiendo cada puntaje de Autoridad por la raíz cuadrada de la suma de los cuadrados de todos los puntajes de Autoridad. (opcional)

Ahora, veamos cómo implementar este algoritmo usando el Módulo Networxx. 
Consideremos el siguiente Gráfico: 
 

Al ejecutar el algoritmo HITS con  (sin normalización), 
 

Initially,
Hub Scores:        Authority Scores:
A -> 1             A -> 1
B -> 1             B -> 1
C -> 1             C -> 1
D -> 1             D -> 1
E -> 1             E -> 1
F -> 1             F -> 1
G -> 1             G -> 1
H -> 1             H -> 1

After 1st iteration,
Hub Scores:        Authority Scores:
A -> 1             A -> 3
B -> 2             B -> 2
C -> 1             C -> 4
D -> 2             D -> 2
E -> 4             E -> 1
F -> 1             F -> 1
G -> 2             G -> 0
H -> 1             H -> 1

After 2nd iteration,
Hub Scores:        Authority Scores:
A -> 2             A -> 4
B -> 5             B -> 6
C -> 3             C -> 7
D -> 6             D -> 5
E -> 9             E -> 2
F -> 1             F -> 4
G -> 7             G -> 0
H -> 3             H -> 1

After 3rd iteration,
Hub Scores:        Authority Scores:
A -> 5             A -> 13
B -> 9             B -> 15
C -> 4             C -> 27
D -> 13            D -> 11
E -> 22            E -> 5
F -> 1             F -> 9
G -> 11            G -> 0
H -> 4             H -> 3

El paquete Python Networkx tiene una función incorporada para ejecutar el algoritmo HITS. Esto se visualizaría con referencia al gráfico anterior. 
 

# importing modules
import networkx as nx
import matplotlib.pyplot as plt
 
G = nx.DiGraph()
 
G.add_edges_from([('A', 'D'), ('B', 'C'), ('B', 'E'), ('C', 'A'),
                  ('D', 'C'), ('E', 'D'), ('E', 'B'), ('E', 'F'),
                  ('E', 'C'), ('F', 'C'), ('F', 'H'), ('G', 'A'),
                  ('G', 'C'), ('H', 'A')])
 
plt.figure(figsize =(10, 10))
nx.draw_networkx(G, with_labels = True)
 
hubs, authorities = nx.hits(G, max_iter = 50, normalized = True)
# The in-built hits function returns two dictionaries keyed by nodes
# containing hub scores and authority scores respectively.
 
print("Hub Scores: ", hubs)
print("Authority Scores: ", authorities)

Producción: 
 

Hub Scores:  {'A': 0.04642540386472174, 'D': 0.133660375232863,
              'B': 0.15763599440595596, 'C': 0.037389132480584515, 
              'E': 0.2588144594158868, 'F': 0.15763599440595596,
              'H': 0.037389132480584515, 'G': 0.17104950771344754}

Authority Scores:  {'A': 0.10864044085687284, 'D': 0.13489685393050574, 
                    'B': 0.11437974045401585, 'C': 0.3883728005172019,
                    'E': 0.06966521189369385, 'F': 0.11437974045401585,
                    'H': 0.06966521189369385, 'G': 0.0}