中国科技论文在线 http://www.paper.edu.cn 基于链接聚类的 PageRank 算法 武汉理工大学计算机科学与技术学院，湖北省武汉市 (430070) E-mail：whutgy@126.com 龚勇 摘 要 ：本文提出了一种基于链接聚类的 PageRank 改进算法。该算法考虑同一页面内分属 不同类的出链接有着不同的重要性，故在对页面中的链接进行聚类预处理后，对分属不同类 的出链接赋予相应的权重，从而能够更合理、有效地计算页面的 PageRank 值。 关键词：搜索引擎，PageRank 算法，链接聚类，主题漂移 中图分类号：TP391 1．引言 近年来，随着Internet的不断发展，互联网已经成为人们获取信息的重要来源，为人们 提供了丰富的信息资源。面对海量的网络资源，搜索引擎成为帮助人们获取所需信息的重要 工具。对于特定的查询请求，用户总是希望优先获得与查询最贴切的网页，如何将这样的网 页排在搜索结果的前列就是网页排序算法所要解决的问题。 PageRank算法是由Google公司首先使用，并被广泛研究的一种网页排序算法。本文对 PageRank算法进行了改进，在借鉴现有一些PageRank改进算法[5]的基础上，结合链接聚类的 方法，提出了一种按照链接所属不同类别分配权值的改进算法，能够弥补单个链接的锚文本 可能存在主题描述不清的问题。通过实验表明，改进算法具有更好的排序质量。 2．PageRank算法 PageRank 算 法 的 主 要 思 想 是 把 网 页 中 的 链 接 分 为 前 向 链 接(in-links) 和 反 向 链 接 (back-links)，也称为引用链接和被引用链接。反向链接表示该网页被其他网页引用，反向链 接数目越多，说明该网页被引用越多，它就有越可能是比较重要的网页，因此，可以凭借反 向链接的数量来推断该网页的重要程度。依据该思想，得到 PageRank 计算公式如下[4]： uPR )( = 1( − d ) + d ∑ uBi )( ∈ vPR )( vN )1( 其中，B(u)表示直接指向网页 u 的网页集(u 的反向链接的集合)；Nv 表示网页 v 前向链 接的数量；PR(v)/Nv 是指网页 v 把自己的权威值平均分配给从自己网页中指出的链接；d 为 阻尼系数，d∈(0,1)，通常情况下取 0.85。 PageRank 算法的优点在于避免了单纯依靠文本匹配来评价页面的重要性，充分利用了 Web 模型的超链接结构来评估页面的权威性，从而提供了一种能够对 Web 资源进行客观评 价的有效手段；但另一方面从该算法的简介可以看出 PageRank 算法是一种与查询关键词无 关的静态的页面质量计算方法，算法未区分网页中的链接是否和主题相关、未判断引用与被 引用网页内容上的相关性，这就有可能导致搜索结果中得分高的网页与搜索的主题相关性并 不大，即出现“主题漂移”，进而影响搜索引擎的查准率。 针对 PageRank 算法存在的问题，Bharat 和 Henzinger 提出了一种对出链赋予不同权值 的启发式方法[1]；Haveliwala 提出了主题敏感的 PageRank[2]，对一些不同主题采用不同的主 题向量，在进行信息查找时，首先计算待搜索的主题与这些主题向量的相似度，作为权值， -1- 

中国科技论文在线 http://www.paper.edu.cn 然后计算出网页关于各个主题的重要性，将它们加权求和得到综合的 PageRank 值；另外国 内的一些学者对该算法也提出了一些改进[5] [6]。这些方法都在 PageRank 中引入了主题信息， 对解决主题漂移问题起到了一定的作用，但只是单纯地利用单个链接的锚文本对链接与主题 的相关性进行判断，当遇到某些链接的锚文本描述信息质量不高时将会影响判断的效果。本 文的改进算法基于链接聚类，可以更清晰地给分属不同重要性类别的出链接以合适的权值， 使得 PageRank 值的分配策略比传统算法更加准确、合理。 3．链接聚类算法 针对 PageRank 算法的局限性，本文首先对网页中所有的链接进行聚类，进而计算各个 类别中所有链接的锚文本与主题的相关度，用类别整体的相关度代替单一链接锚文本的相关 度作为影响 PageRank 计算公式中权值的因素。 由于网页具有半结构化的特点，故可以利用文档对象模型(DOM，Document Object Model) [3]将网页解析成 DOM 树。通过对网页结构的分析发现：在网页同一区域出现的链接 在 DOM 树上具有从根结点到链接结点的相同路径。而这些相邻的链接之所以被安排到一 起，往往因为它们表达了相同或者相近的一个主题，如果这个主题与本页面的内容相关，则 表明本页面的作者可能希望引用这些链接作为本页面的参考和补充，所以这部分链接的价值 应该较高；反之，如果这个主题与本页面内容不相关，比如广告，则应该降低这部分链接的 重要性。因此，我们可以利用 DOM 树对网页中的链接进行聚类，并对分属不同类别的链接 的重要性加以区分。 图 1 网页对应的 DOM 树 Fig1 Corresponding DOM tree of web page 利用这个特点，本文使用的链接聚类算法的基本思想为：按出现的先后顺序将网页中的 链接依次放入队列，在 DOM 树上找出满足任意两个结点间的路径相同且长度大于 2 的最大 -2- 

中国科技论文在线 http://www.paper.edu.cn 连续子串，从队列中将该子串中的所有元素取出，归入新类。迭代进行，直到队列为空或者 找不到满足条件的子串为止。算法描述如下： Set L={link1,link2,…linkn}; Set C1,C2,…Cm=Φ; set category_num=1; set flag = 1 While (L≠Φ) and (flag = 1) End While 其中 L 表示由该页面中所有链接组成的集合，Ci 表示属于类别 i 的链接集合， If max neighbor count with same common path >1: Set flag=0 For Each link in L End For Put link and all the neighbors Ccategory_num Set category_num=category_num+1 Set flag = 1 category_num 表示当前类别编号。 4．基于链接聚类的改进PageRank算法 本文改进算法的基本思想是改变传统 PageRank 算法的平均分配权值策略，对页面中的 链接进行聚类，给分属不同类别的出链接以相应的权重，使同一页面中链接具有更强的区分 度，以得到更加准确合理的 PageRank 值。 4.1 基于链接聚类的 PageRank 计算 假设某个页面的链接聚类后可得到 C1，C2，…，Cn 等 N 个类，C1 类链接的权重为β1k， C2 类链接的权重为β2k，依次类推。另外对聚类结果进行统计可得：页面有 t1 个 C1 类链接， t2 个 C2 类链接，…tn 个 Cn 类链接，而一个页面内所有的链接被点击的概率的和应该为 1， 即： CtCt + 1 2 1 t t k β + 1 1 + 2 k β 2 2 ...... + + ...... Ct n t + = n β n n 1 k = 1 )3( 文本块和链接类锚文本的文本信息可以采用经典的向量空间模型(Vector Space Model， VSM)来描述。深度遍历 DOM 树后计算出页面 A 内的主题词来代表页面 A 的主题内容，记 为：A_topic={w1, w2, ……,wn}。假设页面 A 内所有的链接为集合 L，对于第 i 个链接类 Ci L， 提取链接类 Ci 中所有链接的锚文本内容记为：C_anchori={w1, w2, ……,wn}。我们定义 C_anchori 和 d_topic 的余弦距离为链接类 Ci 和页面 A 的相关度。记为 r(Ci,A)，计算方法如 ⊂ -3- 

中国科技论文在线 下： http://www.paper.edu.cn r ,C( i A ) = _Ccos( anchor i A _, topic ) = ∑ w m i i anchor i • × w n i i A _ _C topic )4( iTL 设 为页面 Ti 内指向页面 A 的链接，它属于类别 Cj，设它的权重为 Lf ( T i ) = Cf ( ) = j tACr ( × ) , j j n ∑ k 1 = tACr ([ × ) , k ] k iTLf ( ) ，则： )5( 式(5)中，t1，t2…tn 在对页面中的链接聚类后统计可以获知，表示聚类所得的 n 个类中 各自含有的链接数目。 从以上步骤可以得到各链接及所属链接类对应的权值，接下来修改 PageRank 公式如下： APR ) ( = 1( − d ) + d n ∑ i 1 = iLfTPR ( ) ( T i ) )6( 式(6)中， iTLf ( ) 函数为链接类别权重函数，由式(5)计算得出。 4.2 实验及结果分析 为了测试改进的 PageRank 算法对搜索结果的影响，我们设计了如下的试验来进行验证： 首先使用开源搜索引擎 Nutch 对 http://edu.sina.com.cn/域名下的页面进行抓取分析，获取有 效网页 12,655 个。接下来分别使用标准的 PageRank 算法和改进的 PageRank 算法计算标准 的 PageRank 值和改进后的 PageRank 值，然后使用教育领域的十个关键词进行查询，对于 查询结果分别按照标准的 PageRank 值和改进后的 PageRank 值排序，计算返回结果的查准 率。结果如下表： 表 1 算法查准率对比表 Tab.1 Contrast of algorithms on precision ratio 算法 查询词 四六级 研究生考试 招聘 高考 就业 留学 计算机 雅思 大学生 自主招生 传统 PageRank 算法 改进的 PageRank 算法 0.87 0.82 0.77 0.86 0.81 0.82 0.79 0.91 0.75 0.88 0.91 0.85 0.83 0.93 0.88 0.86 0.91 0.95 0.85 0.93 由实验结果可得，改进的 PageRank 算法可以在一定程度上提高搜索引擎返回结果的查 准率，减少查询结果的主题漂移。 引入链接聚类的方法，使用聚类中所有链接的锚文本的相关度代替单一链接的锚文本相 关度的策略使得当类别中的一个链接与主题相关时，该组的所有链接也会从类别权值中获得 部分得分，得分的多少取决于该类别与主题相关度的大小。由于网页中同一个类别中的链接 -4- 

中国科技论文在线 http://www.paper.edu.cn 在内容上往往具有较强的相关性，这种方法有助于在个别链接锚文本描述信息质量不高的情 况下对它的主题和所属类别做出正确的判断。 5．总结 “主题漂移”问题根源在于传统的 PageRank 算法同等对待同一页面上所有的出链接。 本文介绍的基于链接聚类的改进算法合理地调整了同一页面的 PageRank 值的分配策略，从 链接聚类入手，再利用向量空间模型计算相关度，对消除因个别链接的锚文本描述质量不高 造成的主题相关性判断不准确的问题，具有良好的效果。实验结果表明本算法可以提高搜索 引擎的检索精度和质量。 参考文献 [1] M.Richardson,P.Domingos． The intelligent surfer:probabilistic combination of link and content information in PageRank[C]． MIT Press， 2001，1441-1448． [2] Haveliwala, Taher H ． Topic-sensitive PageRank. IEEE Transaetions on Knowledge and Data Englneering[C]．2003, 784-796． [3] Gupta S,Kaiser G,Neistadt D et al． DOM based Content Extraction of HTMLDocuments． the proceedings of the 12th World Wide Web conference(WWW 2003) [C]， 2003-05． [4] Taher H. Haveliwala．Efficient Computation of PageRank．Stanford University Technical Report， 1999． [5] 黄德才,戚华春,钱能．基于主题相似度模型的 TS-PageRank 算法［J］．小型微型计算机系统， 2007， [6] 宋聚平,王永成,尹中航,等．对网页 PageRank 算法的改进［J］．上海交通大学学报， 2003， 37(3)： 28(3)： 510-514． 397-400． The PageRank algorithm based on clustering links Department of Computer Science and Technology, Wuhan University of Technology, Wuhan， Gong Yong Hubei, PRC, (430070) This paper proposes a clustering links for web pages based on PageRank algorithm. Considering the different importance of out-links from different categorys within a web page, the algorithm provides corresponding weight factors for these links after cluster those links. Keywords: search engine; PageRank algorithm; link clustering; topic drift Abstract -5-