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

超链接诱导主题搜索
(HITS)算法是一种由Jon Kleinberg开发的对网页进行评分的链接分析算法。该算法用于Web链接结构, 以发现和排名与特定搜索相关的网页。
HITS使用中心和权限来定义网页之间的递归关系。在了解HITS算法之前, 我们首先需要了解中心和授权机构。

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

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

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

现在, 让我们看看如何使用Networxx模块实现此算法。
让我们考虑下图：

文章图片
在运行HITS算法时

文章图片
(没有规范化),

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

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

# importing modules import networkx as nx import matplotlib.pyplot as pltG = 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}