论文部分内容阅读
PageRank 算法是目前被广泛应用的一种度量网页重要性的方法，它根据网页之间的链接结构来给每个网页打分。从数学的角度来解释，PageRank可以被看作是一个马尔可夫随机游走模型，依据网页下一步的链接信息计算网页的转移概率。用马氏链的平稳分布作为最终的Rank值给网页排序。
受计算机象棋对弈算法设计中，一个很成功的策略“多看几步”的启发，我们改进和推广了经典的PageRank算法，提出了N-step PageRank算法，它在计算网页的转移概率时利用了网页N步的链接信息。特别地，我们假定，如果网上冲浪者知道每个网页的N步内的链接情况，那么在选择下一步要浏览的网页时他/她就可做出更好的选择。经典PageRank算法是N-step PageRank算法N=1时的特殊情形。TREC标准数据集上的实验表明，N-step PageRank算法能够有效提高网页搜索的精确度，MAP指标比经典的PageRank的提高超过15％．
经典PageRank算法和N-step PageRank算法都是利用平稳分布来度量网页的重要性。由于计算平稳分布实际上是计算矩阵的特征向量，计算复杂度很高，在万维网搜索时海量数据信息使得计算的时间开销很大。为了降低计算的复杂度，我们提出了一种更为简单有效的链接分析方法——WeightedIndegree算法，与PageRank算法不同，它直接利用加权的入度给网页排序。TREC标准数据集上的实验表明，WeightedIndegree算法能够大大降低算法的复杂性，同时能有效地提高网页搜索的精确度，MAP指标比经典的PageRank的提高超过15％．