《WEB超链分析算法纵览》由会员分享，可在线阅读，更多相关《WEB超链分析算法纵览（16页珍藏版）》请在金锄头文库上搜索。
1、WEB超链分析算法纵览来源:搜索引擎排名研究朱炜王超申俊潘金贵Abstract: The World Wide Web serves as a huge, widely distributed, global information service cen ter, and expa nding in a rapid speed .It is import to find the informatio n the user need precisely and rapidly In recent years, researchers discovery that rich and import
2、 information is contained among hyperlinks, and develop a lot of algorithm using hyperlink to improve the qua ntity and releva nee of the results which search engine returned This paper presents a review and a comparison of such algorithms existing now. Problems of these algorithms and directions to
3、 further research will be discussedKeyword: PageRank, Authority, Hub, HITS. SALSA, Anchor1.引言力维网WWW (World Wide Web)是一个巨大的，分布全球的信息服务中心，正在以飞快的速度扩展。 1998年WWW 拥有约3.5亿个文档【叫 每天增加约1百万的文档,不到9个月的时间文档总数就 会翻一番WEB上的文档和传统的文档比较，有很多新的特点，它们是分布的，异构的，无结构或者 半结构的，这就对传统信息检索技术提出了新的挑战。传统的WEB搜索引擎大多数是基于关键字匹配的，返冋的结呆是包含查询项的文
4、档，也有基于目录分 类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提高关键字出现的频率來提高自身在搜 索引擎中的垂要性，破坏搜索引擎结果的客观性和准确性。另外，有些重要的网页并不包含査询项。搜索 引擎的分类H录也不可能把所有的分类考虑全面，并且日录大多靠人丁维护，主观性强，费用高，更新速 度慢。最近儿年，许多研究者发现，WWW上超链结构是个非常丰空和垂要的资源，如果能够充分利用的话， 可以极大的提高检索结果的质最。基于这种超链分析的思想，Sergey Brin和Lawrence Page在1998 年提HIT PageRank算法,同年J. Kleinberg提出了 HITS算法,
5、其它一些学者也相继提岀了另外 的链接分析算法，如SALSA, PHITS, Bayesian等算法。这些算法有的己经在实际的系统中实现和使用， 并且取得了良好的效果。文章的第2部分按照时间顺序详细剖析了各种链接分析算法，对不同的算法进行了比较。第3部分对这 些算法做了评价和总结，指出了存在的问题和改进方向。2. WEB超链分析算法2 . 1 Google 和 PageRank 算法搜索引擎Google最初是斯坦福大学的陳士硏究生Sergey Brin和Lawrence Page实现的-个原型系 统，现在已经发展成为WWW上故好的捜索引擎之一。Google的体系结构类似于传统的搜索引華，它 与传
6、统的搜索引擎最大的不同处在于对网页进行了基于权威值的排序处理，使最朿要的网页出现在结果的 最前面。Google通过PageRank元算法计算出网页的PageRank值，从而决定网页在结果集中的出现位 置，PageRank值越高的网页，在结杲中出现的位置越前。Page Rank 算法PageRank算法基于下面2个前提:前提仁一个网页被多次引用，则它可能是很重要的：一个网页虽然没有被多次引用，但是被重要的网 页引用，则它也可能是很霓要的：一个网页的重要性被平均的传递到它所引用的网页。这种重要的网页称 为权威（Authoritive）网页。前提2：假定用户一开始随机的访问网页集合中的一个网页，以后
7、跟随网页的向外链接向前浏览网页, 不回退浏览，浏览下一个网页的概率就是被浏览网页的PageRank值。简单PageRank算法描述如下：u是一个网页，是u指向的网页集合，是指向u的网页集合，是u指向外的链接数，显然=| , c是一个用于规范化的因子（Google通常取0.85）,（这种表示法也适用于以后介绍的算法）则u的Rank值计算如下：这就是算法的形式化描述,也可以用矩阵來描述此算法,设A为一个方阵，行和列对应网页集的网页。如 果网页i有指向网页j的一个链接，则，否则 =0。设V是对应网页集的一个向量，有V=cAV, V为A的特征根为c的特征向最。实际上，只需:要求出最大特征根的特征向量，
8、就是网页集对应 的最终PageRank值，这可以用迭代方法计算。如果有2个相互指向的网页a, b,他们不指向其它任何网页，另外有某个网页c,指向a, b中的某一个,比如a,那么在迭代计算中,a, b的rank值不分布出去而不断的累计。如下图：为了解决这个问题，Sergey Brin和Lawrence Page改进了算法，引入了衰退因子E(u), E(U)是对 应网页集的某一向量，对应rank的初始值，算法改进如下：其中，=1,对应的矩阵形式为V =c(AV, +E)。另外还有一些特殊的链接，指向的网页没有向外的链接。PageRank计算时，把这种链接冇先除去，等 计算完以后再加入，这对原來计算
9、出的网页的rank值影响是很小的。Pagerank算法除了对搜索结果进行排序外，还可以应用到其它方面，如估算网络流量，向后链接的预 测器，为用户导航等。2.1.2算法的一些问题Google是结合文木的方法來实现Page Rank算法的，所以只返冋包含查询项的网页，然后根据网页 的rank值对搜索到的结果进行排序，耙rank值最高的网页放置到最前面，但是如果最匝要的网页不在结 果网页集中，PageRank算法就无能为力了，比如在Google中查询search engines.像Google,Yahoo, Altivisa等都是很垂要的，但是Google返冋的结果中这些网页并没有出现。同样的查询例
10、子也可以说明 另外一个问题，Google, 丫ahoo是WWW上故受欢迎的网页，如果出现在查询项car的结果集中，一定 会有很多网页指向它们，就会得到较高的rank值，事实上他们与car不太相关。在PageRank算法的基础上，其它的研究者提出了改进的PageRank算法。华盛顿大学计算机科学与 工程系的Matthew Richardson和Pedro Dominggos提出了结合链接和内容信息的PageRank算法， 去除了 Page Rank算法需要的前提2,増加考虑了用户从一个网页直接跳转到非直接相邻的但是内容相关 的另外一个网页的情况。斯坦福大学计算机科学系Taher Haveliwa
11、la提出了主题做感(Topic-sensitive) Page Rank斯坦福大学计算机科学系Arvind Arasu等经过试验表明，Page Rank算法计算效率还可以得到很大的提高血】。2.2HITS算法及其变种PageRank算法中对于向外链接的权值贡献是平均的，也就是不考虑不同链接的巫要性。而WEB的链 接具有以下特征：1 .有些链接具有注释性，也有些链接是起导航或广告作用。有注释性的链接才用于权威判断。2. 基于商业或竞争因素考虑，很少有WEB网页指向其竞争领域的权威网页。3. 权威网页很少具有显式的描述，比如Google主页不会明确给出WEB搜索引擎Z类的描述信息。可见平均的分布权
12、值不符合链接的实际情况【切。丄Kleinberg提出的HITS算法中引入了另外一种网 页，称为Hub网页，Hub网页是提供指向权威网页链接集合的WEB网页，它本身可能并不匝要，或者说 没有几个网页指向它，但是Hub网页确提供了指向就某个主题而言最为贡要的站点的链接集合，比一个课 程主页上的推荐参考文献列表。-般來说，好的Hub网页指向许多好的权威网页；好的权威网页是有许多 好的Hub网页指向的WEB网页。这种Hub与Authoritive网页之间的相互加强关系,可用于权威网页 的发现和WEB结构和资源的自动发现，这就是Hub/Authority方法的基木思想。2.2.1 HITS 算法HITS
13、 (Hyperlink Induced Topic Search)算法是利用 Hub/Authority 方法的搜索方法,算法如 下：将查询q提交给传统的基于关键字匹配的搜索引擎.搜索引擎返冋很多网页，从中取前n个网页作为 根集(root set)，用S表示。S满足如下3个条件：1. S中网页数量相对较小2. S中网页大多数是与查询q相关的网页3. S中网页包含较多的权威网页。通过向S中加入被S引用的网页和引用S的网页将S扩展成一个更大的集合T.以T中的Hub网页为顶点集VI,以权威网页为顶点集V2, VI中的网页到V2中的网页的超链接为边集 E,形成一个二分有向图SG = (V1, V2,
14、E)。对V1中的任一个顶点v,用h(v)表示网页v的Hub值， 对V2中的顶点u,用a(u)表示网页的Authority值。开始时h(v)=a(u)=1,对u执行I操作修改它的 a(u),对v执行0操作修改它的h(v),然后规范化a (u) , h (v),如此不断的重复计算下面的操作I,0,直到a (u) , h(V)收敛。(证明此算法收敛可见)I操作：(1) 0操作:每次迭代后需要对a(u),h(v)进行规范化处理：式(1)反映了若一个网页山很多好的Hub指向，则其权威值会相应増加(即权威值增加为所有指向它的 网页的现有Hub值之和)。式(2)反映了若一个网页指向许多好的权威页，则Hub值
15、也会相应増加(即Hub 值増加为该网页链接的所有网页的权威值之和)。和Page Rank算法一样，可以用矩阵形式來描述算法，这里省略不写。HITS算法输出一组具有较人Hub值的网页和具有较人权威值的网页。2. 2. 2 HITS的问题HITS算法有以下几个问题：1. 实际应用中，山S生成T的时间开销是很昂贵的，需要下载和分析S中每个网页包含的所有链接， 并排除垂复的链接。一般T比S大很多，山T生成有向图也很耗时。需要分别计算网页的A/H值，计 算量比Page Rank算法大。2. 有些时候,一主机A上的很多文档可能指向另外一台主机B上的某个文档,这就增加了 A上文档的 Hub值和B上文档的Au
16、thority,相反的情况也如此。HITS是假定某一文档的权威值是山不同的单个组 织或者个人决定的，上述情况影响了 A和B上文档的Hub和Authority值。3网页中一些无关的链接影响A, H值的计算。在制作网页的时候，有些开发工具会自动的在网页上加 入一些链接,这些链接大多是与查询主题无关的。同一个站点内的链接冃的是为用户提供导航帮助，也与 查询主题不甚无关，还有一些商业广告，赞助商和用于友情交换的链接，也会降低HITS算法的楕度。4. HITS算法只计算主特征向最，也就是只能发现T集合中的主社区(Community)，忽略了其它垂 要的社区。事实上，其它社区可能也非常重要。5. HITS算法最大的弱点是处理不好主题漂移问题(topic drift)【7 8】，也就
