[搜索引擎技术普及 - 4] 搜索引擎系统的网络链接结构分析技术（下）

sowang

内容出自：搜狗实验室


今天，我们来进行链接分析算法的最后一次讲座，今天介绍的PageRank算法是Google公司的Brin等人根据因特网用户浏览模型建立的链接分析算法。


PageRank算法的基本架构和实现思路在实际商用搜索引擎的应用中取得了巨大的成功，并由此得到了研究界的普遍关注，尝试对算法进行性能和效率改进的努力一直到最近也是链接关系分析方面研究的重点之一。


PageRank算法将网络浏览模型作了合乎情理的简化：假设存在这样一名网络浏览者，他从随机挑选的页面开始，按照页面上的链接前进，在每一个页面，浏览者都有可能不再对本页面内部的链接感兴趣，从而随机选择一个新的页面开始新的浏览。


在这种浏览模型下，一个页面被访问到的概率即反映在此页面的Rank值的大小上。如下图所示，页面q1包含指向页面p和m的链接，则它对p和m在Rank值上的贡献各是它自身Rank值的一半。





形式化的说，在PageRank算法中页面P被访问到的概率依下式给出：





其中，sigma是有链接指向页面P的网页的集合，而d是页面P的重要性因子，由先验知识得出，反映用户认为这个页面有用的程度。简而言之，就是用户会不会从抛弃这个页面而开始一个新的随机访问过程。算法中，上述计算过程被重复进行直到运算结果收敛为止。而作为计算结果的Rank(P)则被用作页面质量的评价参数。

PageRank算法被作为Google的主要成功经验之一广为推介，但他在学术研究的层次上并没有获得想象之中的比较大的成功。


Nick Craswell与David Hawking发现，即使在链接分析方法使用较多的主页查找任务中，PageRank算法及其变形也仅仅获得了比纯内容检索略好的结果。根据刘悦等的实验，应用PageRank算法的结果在TREC大规模检索数据上“与基准测试数据基本持平” 。Amento等人也利用实验验证了至少在小规模数据上，包括PageRank/HITS在内的各种链接结构分析算法都无法有效的提高纯文本检索的效果。


我们认为，造成PageRank和HITS在内的大量链接分析算法在网络信息检索研究中失效的原因，来自于一般研究所采用数据集合的不完整性。即使现在较为广泛采用的规模较大的.GOV数据库，其规模也不过覆盖不到20G数据，而其链接关系表只涉及了不足150万个链接。对于这样链接结构大量缺失的数据集，仅仅依靠链接结构分析评价页面质量是不可靠的。这也是尽管研究界不断汇报链接分析算法对于提高信息检索系统性能没有帮助，而链接分析模块却一直成为商用搜索引擎不可或缺部分的原因。


然而面临真实的网络环境时，链接分析算法又要面临新的问题，那就是数据的繁杂和垃圾、作弊链接的存在，从这个角度讲，无论在实验或是应用的层面，链接分析算法都是解决诸如页面质量评估这样的网络信息检索发展面临问题的可行途径之一而并非全部。