【信息检索】链接分析

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

预先设定一些程序参数：

根据题目中给定的图创建邻接矩阵：


对于此题，邻接矩阵如下所示：
linkMatrix[i][j]=1说明有一条从节点i指向节点j的有向边。

然后开始计算转移概率矩阵：
一共三步：

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

进行幂迭代法：
初始化概率分布向量：

然后根据如下公式进行迭代，直到概率分布向量收敛：


最终计算结果如下所示：迭代一次后即可收敛

即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的定义式：

于是：

其中M为转移概率矩阵（无随机跳转），1为[1*N]的全一矩阵，I为单位矩阵

由此可以得到，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值。

预先设定一些程序参数：

然后对图中的节点进行标号，并生成对应的邻接矩阵，如下所示：

邻接矩阵：

初始化hub以及authority向量：

根据如下公式开始迭代，同时每一次迭代过后需要对于向量进行归一化处理，直到hub与authority向量收敛：

最终运行结果如下所示：


最终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值最高十分合理。

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