文档介绍：:..1•引言万维网,分布全球的信息服务中心,止在以飞快的速度扩展01998年,每天增加约1百万的文档⑹,不到9个月的时间文档总数就会翻一番“勺。WEB±的文档和传统的文档比较,有很多新的特点,它们是分布的,界构的,无结构或者半结构的,这就对传统信息检索技术提岀了新的挑战。传统的WEB搜索引擎大多数是基于关键字匹配的,返回的结果是包含查询项的文档,也冇基于H录分类的搜索引擎。这些搜索引擎的结果并不令人满意。冇些站点冇意提高关键字出现的频率来提鬲自身在搜索引擎中的重要性,破坏搜索引擎结果的客观性和准确性。另外,有些重要的网页并不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全而,并fLH录大多靠人工维护,主观性强,费用高,更新速度慢【2】。最近几年,许多研究者发现,用的话,町以极大的提高检索结果的质量。基于这种超链分析的思想,SergeyBrin和LawrencePage在1998年提IIITPageRank算法⑴,⑸,其它一些学者也相继提岀了另外的链接分析算法,女IISALSA,PHITS,Bayesian等算法。这些算法有的己经在实际的系统中实现和使用,并且取得了良好的效果。文章的第2部分按照时间顺序详细剖析了各种链接分析算法,对不同的算法进行了比较。笫3部分对这些算法做了评价和总结,指岀了存在的问题和改进方向。⑵,现在己经发展成为体系结构类似于传统的搜索引擎,它与传统的搜索引擎最大的不同处在于对网页进行了基于权威值的排序处理,使最重耍的网页出现在结果的最前面。Google通过PageRank元算法计算出网页的PageRank值,从而决定网页在结來集中的出现位置,PageRank值越尚的网页,在结果中出现的位置越前。:前提1:一个网页被多次引用,则它对能是很重要的:一个网页虽然没有被多次引用,但是被重要的网页引用,则它也可能是很重要的;一个网页的重耍性被平均的传递到它所引用的网页。这种重要的网页称为权威(Authoritive)网页。前提2:假定用户一开始随机的访问网页集合中的一个网页,以后跟随网页的向外链接向前浏览网贝,不回退浏览,浏览下一个网页的概率就是被浏览网页的PageRank值。简单PageRank算法描述如下:u是一个网页,月似)是u指向的网页集合,月仗)是指向u的网页集合,"的是u指向外的链接数,显然"似)=|月(")|,c是一•个用于规范化的因子(),(这种表示法也适川于以后介绍的算法)则u的Rank值计算如F:=c工论玄町这就是算法的形式化描述,也可以用矩阵来描述此算法,设A为一个方阵,行和列对应网页集的网页。如果网页i有指向网页j的一个链接,则化='心,否则%=0。设V是对应网页集的一个向量,有V=cAV,V为A的特征根为c的特征向量。实际上,只需要求出最大特征根的特征向量,就是网页集对应的最终PageRank值,这可以用迭代方法计算。如果有2个相互指向的网页a,b,他们不指向其它任何网页,另外有某个网页c,扌舸a,b中的某一个,比如a,那么在迭代计算中,a,b的rank值不分布出去而不断的累计。如下图:为了解决这个问题,SergeyBrin和LawrencePage改进了算法,引入了衰退因子E(u),E(U)是对应网页集的某一向量,对应rank的初始值,算法改进如下:R(以)=c工RW)/N®)+cE(u) ("2) 其中,11绚11=1,对应的矩阵形式为V=c(AV+E)o另外还有一些特殊的链接,指向的网页没有向外的链接。PageRank计算时,把这种链接首先除去,等计算完以后再加入,这对原來计算出的网页的rank值影响是很小的。Pagerank算法除了对搜索结果进行排序外,还可以应用到其它方面,如估算网络流屋,向后链接的预测器,为用户导航等⑵。⑵,所以只返回包含查询项的网页,然后根据网页的rank值対搜索到的结果进行排序,把rank值最高的网页放置到最前血,但是如果最重耍的网页不在结果网页集PageRank算法就无能为力了,比如在Google中查询searchengines,像Google,Yahoo,Altivisa等都是很重要的,但是Google返回的结果中这些网页并没有出现。同样的查询例子也町以说明另外一个问