Networxx模块的超链接诱导主题搜索(HITS)算法|Python

超链接诱导主题搜索

(HITS)算法是一种由Jon Kleinberg开发的对网页进行评分的链接分析算法。该算法用于Web链接结构, 以发现和排名与特定搜索相关的网页。

HITS使用中心和权限来定义网页之间的递归关系。在了解HITS算法之前, 我们首先需要了解中心和授权机构。

• 给定对搜索引擎的查询, 将高度相关的网页集称为根源。他们有潜力当局.
• 不太相关但指向根中页面的页面称为集线器。因此, "授权机构"是许多集线器链接到的页面, 而"集线器"是链接到许多权限的页面。

算法–

->让迭代次数为k。 ->为每个节点分配一个Hub得分= 1, 一个Authority得分=1。->重复k次：Hub更新：每个节点的Hub得分=(它指向的每个节点的Authority得分)。权限更新：每个节点的权限得分=(指向每个节点的节点得分)。通过将每个Hub得分除以所有Hub得分的平方和的平方根, 再将每个Authority得分除以所有Authority得分的平方和的平方根, 对得分进行归一化。 (可选的)

现在, 让我们看看如何使用Networxx模块实现此算法。

让我们考虑下图：

在运行HITS算法时

(没有规范化),

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

Python软件包Networkx具有用于运行HITS算法的内置函数。参考上面的图表可以看到。

# importing modules
import networkx as nx
import matplotlib.pyplot as plt
  
G = nx.DiGarph()
  
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)

输出如下：

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}

首先, 你的面试准备可通过以下方式增强你的数据结构概念：Python DS课程。

---