木基于链接结构分析的Web页面排序算法

摘要

随着Internet/Web 技术的快速普及和迅猛发展，Web 上信息总量日益膨胀。如何将用户所需信息从这个信息海洋中找到，并按照相关度从大到小排列并返回给用户变得日益迫切，搜索引擎技术应运而生，基于链接分析的Web 页面排序算法是其中最重要的技术之一。基于链接分析的PageRank 算法是目前应用最广泛的页面排序算法。从数学模型上讲，PageRank 算法可以看做是一个马尔可夫随机游走模型，依据当前网页的链接结构计算页面间的转移概率，页面最终的排序值可以由此马尔可夫链的平稳分布唯一给出。
　　 本文首先通过对经典Web结构挖掘算法HITS和PageRank 算法的研究学习，发现经典PageRank 算法容易出现主题漂移现象，而主题漂移现象是由页面链接的均分赋值引起的。在受HITS排序算法枢纽网页思想和PageRank 算法的实验的启发下，本文重新定义了PageRank 算法的排序函数，使得页面链接权值和链入页面的出度和入度均相关，提出了改进的PageRank 算法，这样就避免了页面链接的均分赋值。实验结果表明了算法的查准率有了显著的提高，p@10和p@50 指标均一致性的超过经典PageRank 算法。
　　 在改进的PageRank 算法的基础上，受经典PageRank 算法排序函数公式的启发，可知页面的排序值受三大因素影响。对于页面间的每条链接，我们定义了链接尾端入度影响因子和链接头端出度影响因子，两个影响因子分别用上述三大因素度量，提出了Hybrid Pagerank 算法。实现了可调阀值的页面排序方法，有效的结合了经典PageRank 算法和改进的PageRank 算法的优点，实验结果验证了算法的有效性。