【信息检索】链接分析

Alex_Shen
2022-07-03 / 1 评论 / 0 点赞 / 215 阅读 / 913 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-07-03,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

(1). 阅读教材《Introduction to Information Retrieval》第464-470页21.2节中所描述的PageRank计算方法(通过power iteration方式来实现),用Java语言或其他常用语言实现该算法。要求以下图所示的结构为例计算每个document的PageRank值,其中teleportation rate=0.05。

image-1656839878801

预先设定一些程序参数:
image-1656839944203
根据题目中给定的图创建邻接矩阵:
image-1656839947634
image-1656839959344
对于此题,邻接矩阵如下所示:
linkMatrix[i][j]=1说明有一条从节点i指向节点j的有向边。
image-1656839982105
然后开始计算转移概率矩阵:
一共三步:

  1. 用每行中的1的个数取出每个1
  2. 处理后的结果矩阵乘以1-α
  3. 对上面得到的矩阵中的每个元素都加上alpha/N
    image-1656839993752
    最终可以得到本体对应的转移概率矩阵:
    image-1656840022911

进行幂迭代法:
初始化概率分布向量:
image-1656840032400
然后根据如下公式进行迭代,直到概率分布向量收敛:
image-1656840043644
image-1656840048110
最终计算结果如下所示:迭代一次后即可收敛
image-1656840062073
即Pagerank(d1)=0.017,Pagerank(d2)=0.492,Pagerank(d3)=0.492。简单分析可知,d2与d3是对称的。同时由于没有document指向d1,只有当遇到随机跳转时会跳转到document1,所以Pagerank(d1)会明显小于另外两个值。

(2). 以另一种方式(不是power iteration方式)用笔算(不用程序计算)题(1)中每个document的PageRank值。要求有详细的说明和计算过程。(10分)

可以根据代数算法进行计算:
PageRank的定义式:
image-1656840085890
于是:
image-1656840092960
其中M为转移概率矩阵(无随机跳转),1为[1*N]的全一矩阵,I为单位矩阵
image-1656840103999
由此可以得到image-1656840123245,Pagerank(d1)=0.017,Pagerank(d2)=0.492,Pagerank(d3)=0.492,结果同幂迭代法得到结果。

(3). 阅读教材《Introduction to Information Retrieval》第474-477页21.3节中所描述的HITS计算方法(通过power iteration方式来实现),用Java语言或其他常用语言实现该算法。要求以下图所示的结构为例计算每个document的authority值和hub值。

image-1656840171293

预先设定一些程序参数:
image-1656840184276
然后对图中的节点进行标号,并生成对应的邻接矩阵,如下所示:
image-1656840200100
image-1656840208575

邻接矩阵:
image-1656840217433

初始化hub以及authority向量:
image-1656840226578
根据如下公式开始迭代,同时每一次迭代过后需要对于向量进行归一化处理,直到hub与authority向量收敛:
image-1656840235149
image-1656840241443

最终运行结果如下所示:
image-1656840260324
image-1656840267937
最终hub值最大的是节点8(处于base set) ,节点8指向了节点7和9,同时7和9又被多个节点指向(authority值高),因此节点8的hub值最高十分合理。
authority值最大的是节点7 (处于root set),节点7被节点2,3,8指向,同时节点2,3,8的hub值高,因此节点7的authority值最高十分合理。
image-1656840283834

hub/authority值可以反应一个网页的导航度与权威度。不同的网站目的应该侧重于不同的指标,例如导航网站应该侧重hub值,这样可以指向更精准;而门户网站则应该侧重authority值,让更多导航网站指向它,提高权威度。

0

评论区