（运筹学与控制论专业论文）万维网搜索算法的研究——从pagerank算法到weightedindegree算法.pdf

中文摘要 p a g e r a l l k 算法是目前被广泛应用的一种度量网页重要性的方法，它根据网页 之间的链接结构来给每个网页打分。从数学的角度来解释，p a g e r a n k 可以被看作 是一个马尔可夫随机游走模型，依据网页下一步的链接信息计算两页的转移概率。 用马氏链的平稳分布作为最终的r a n k 值给网页排序。 受计算机象棋对弈算法设计中，一个很成功的策略“多看几步”的启发，我 们改进和推广了经典的p a g e r a n k 算法，提出了n s 姊p a g c r a n k 算法，它在计算 网页的转移概率时利用了网页n 步的链接信息。特别地，我们假定，如果网上冲 浪者知道每个网页的n 步内的链接情况，那么在选择下一步要浏览的网页时他她 就可做出更好的选择。经典p a g e r a n k 算法是n s t e pp a g e r a n k 算法n = i 时的特殊 情形。t r e c 标准数据集上的实验表明，n s t e pp a g e r a n k 算法能够有效提高网页 搜索的精确度，m a p 指标比经典的p a g e r a n k 的提高超过1 5 经典p a g e r a n k 算法和n - s t e pp a g e r a n k 算法都是利用平稳分布来度量网页的 重要性。由于计算平稳分布实际上是计算矩阵的特征向量，计算复杂度很高，在 万维网搜索时海量数据信息使得计算的时间开销很大。为了降低计算的复杂度， 我们提出了一种更为简单有效的链接分析方法w d 曲t e d i n d e 伊e e 算法，与 p a g e r a n k 算法不同，它直接利用加权的入度给网页排序。t r e c 标准数据集上的 实验表明，w e i g h t e d l n d e g r e e 算法能够大大降低算法的复杂性，同时能有效地提高 网页搜索的精确度，m a p 指标比经典的p a g e r a n k 的提高超过1 5 关键词：万维网搜索：链接分析；p a g e r a n k 算法；n - s t e pp a g e r a n k 算法； w e i g h t e d i n d e g r e e 算法 分类号：0 2 9 ；0 2 1 1 6 2 a b s t r a c t p a g e r a n kh a sb e e nw i d e l yu s e dt om e a s n t et h ei m p o r t a n c eo fw e bp a g e sb a s e do n t h e i ri n t e r c o n n e c t i o n si nt h ew e bg r a p h m a t h e m a t i c a l l ys p e a k i n g , p a g e r a n kc a l lb e e x p l a i n e du s i n gam a r k o vr a n d o mw a l km o d e l ，i nw h i c ht h ed i r e c to u t l i n k so f ap a g e c o n t r i b u l et ot h et r a n s i t i o np r o b a b i l i t yo ft h i sp a g e f i n a l l yw eu s et h es t a t i o n a r y d i s t r i b u t i o na st h em e a s u r e m e n t ip r o p o s ei m p r o v i n gt h ep a g e r a n ka l g o r i t h mb yl o o k i n gn - s t e pf o r w a r dw h e n c o n s t r u c t i n gt h et r a n s i t i o np r o b a b i l i t ym a t r i x ，t h em o t i v a t i o nc o m e sf r o mt h es i m i l a r l o o k i n gn s t e pf o r w a r d ”s t r a t e g yt h a ti ss u c c e s s f u l l yu s e di nc o m p u t e rc h e s s i n p a r t i c u l a r , w ea s s n n l et h a ti ft h er a n d o ms u r f e rk n o w st h en s t e po u t - l i n k so f e a c hw e b p a g e ，h e s h ee a nm a k e ab e t t e rd e c i s i o no nc h o o s i n gw h i c h p a g et on a v i g a t ef o rt h en e x t t i m e i ti sc l e a rt h a tt h ec l a s s i c a lp a g e r a n ka l g o r i t h mi sas p e c i a lc a s eo fo u r p r o p o s e d n - s t e pp a g e r a n km e t h o d 。e x p e r i m e n t a lr e s u l t so nt h ed a t a s e to f t r e cw e b t r a c ks h o w t h a to u rp r o p o s e da l g o r i t h mc a nb o o s tt h es e a r c ha c c u r a c yo fc l a s s i c a lp a g e r a n kb y m o r et h a n1 5 i nt e r m so f m e a na v e r a g ep r e c i s i o n b o t ho ft h ec l a s s i cp a g e r a n ka l g o r i t h ma n dn - s t e pp a g e r a n ka l g o r i t h mn s et h e s t a t i o n a r yd i s t r i b u t i o na st h em e a s u r e m e n to ft h ew e bp a g e s i m p o r t a n c e ，b u ti tc o s t sa 1 0 to ft i m et o c o m p u t et h es t a t i o n a r y d i s t r i b u t i o n i nt h i s p a p e r i p r o p o s e d w e i g h t e d i n d e g r e ea l g o r i t h mw h i c hi sa n o t h e rs i m p l el i n ka n a l y s i sa l g o r i t h m d i f f e r e n t f r o mp a g e r a n ka l g o r i t h m i tr a n k st h ew e bp a g e sw i t ht h e i rw e i g h t e di n d e g r e e sd i r e c t l y e x p e r i m e n t a lr e s u l t so nt h ed a t a s e to f t r e cw e bt r a c ks h o wt h a tt h en e wa l g o r i t h mc a l l b o o s tt h es e a r c ha c c u r a c yo fc l a s s i c a lp a g e r a n kb ym o r et h a n1 5 i nt e r m so fm e a n a v e r a g ep r e c i s i o n , a st h eg a m et i m er e d u c et h ec o m p l e x i t yg r e a t l y k e y w o r d s ：w e bs e a r c h ；l i n ka n a l y s i s ；p a g e r a n ka l g o r i t h m ；n - s t e pp a g e r a n k a l g o r i t h m ；w e i g h t e x l i n d e g r e ea l g o r i t h m c l a s s n 0 ：0 2 9 ；0 2 1 1 6 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京奎通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复e l i 件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 强 南 导师签名： 签字同期：州年眨月2 0f t签字日期：2 0 p 锌2 月2 。曰 致谢 本论文的工作是在我的导师马志明教授的悉心指导下完成的，马老师严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在马老师身上，我不只学 到了如何做学问，更学到了如何做人。老师为人的正直、豁达会成为我一生追随 的榜样。在此衷心感谢三年来马老师对我的关心和指导。 研究生期间，数学系的很多老师都给予了我很大的关心和帮助，尤其要感谢 的是冯国臣老师和修乃华老师，老师们平易近人，处处为学生考虑和着想，无论 是学习还是生活中都给予了无微不至的关怀和帮助。 微软亚洲研究院的同事们为我提供了论文实验的数据集，并对于我的科研工 作和论文提出了许多的宝贵意见，在此表示衷心的感谢。 在论文的撰写期间，秦涛、包莹、封光、尚雁宏等同学对我论文中的研究工 作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的家人和朋友，他们的理解和支持使我能够在学校专心完成我 的学业。 序 近年来，互联网发展十分迅速，网络中有很丰富的信息与资源，如何检索出 需要的信息，现代搜索引擎应运而出。搜索引擎是怎样工作的呢? 当用户以关键 词查找信息时，搜索引擎会在数据库中进行搜寻。如果找到与用户要求内容相符 的网站，便采用特殊的算法一通常根据网页中关键词的匹配程度( r e l e v a n c e ) 和链接质量( q u a l i t y ，也即本文中所说的重要性) 计算出各网页的相关度及 排名等级，然后根据关联度高低，按顺序将这些网页链接返回给用户，即对网页 排序。 网页排序的方法主要有两大类，一种是基于网页内容分析进行排序( 对应于 r e l e v a n c e ) ，一种是基于互联网的超链接结构分析进行排序( 对应于q u a l i t y ) 。基于 内容的排序源于传统的信息检索，万维网搜索以其巨大的数据规模对传统信息检 索技术提出了新的挑战。( 3 0 0 9 l e 搜索引擎2 0 0 5 年9 月统计结果显示，其搜索的网 页规模是2 4 个b i l l i o n ，y a h o o 搜索引擎2 0 0 5 年8 月统计的数据是2 0 个b i l l i o n 。 基于链接分析的排序将互联网搜索与传统的信息检索区分开来，从而引发了 互联网搜索研究的高潮。g o o g l e 创始人s e r g e yb r i n 和l a w r e n c ep a g e 于1 9 9 8 年提 出的p a g e r a n k 算法是目前被认为最为成功的一种链接分析方法。g o o g l e 的成功不 仅证实了p a g e r a n k 算法的有效性，更是引发了人们对p a g e r a n k 算法的巨大的研 究热情，从而提出了一系列的p a g e r a n k 算法的变种。 本文第一章，作为预备知识，对p a g e r a n k 算法进行了介绍。 本文第二章从一个新的角度来看待p a g e r a n k 算法，并对p a g e r a n k 算法进行 了推广，提出了n - s t e pp a g e r a n k 算法。 本文第三章，提出了一个全新的链接分析方法一w b i g h t e d i n d e g r e e 算法，与 p a g e r a n k 和n s t e pp a g e r a n k 不同，它不是利用平稳分布来度量网页的链接质量， 而是利用更为简单直接的加权入度来对网页进行排序。 l 经典p a g e r a n k 算法 鉴于经典p a g e 黜m k 算法在目前的链接分析中占有如此举足轻重的地位，而第 二章提出的n - s t e pp a g e r a n k 算法也是基于经典p a g e r a n k 算法。这一章我们将介 绍经典p a g e r a n k 算法，并对其进行一些分析和讨论。 1 1算法简介 两络链接对应莳有岛国，通常被表示为： g = ( 1 ) 这里，p p ，z ，彬为图的顶点集合，它的元素与网络中所有的网页一一对应： e = t i ，j 矿) 为图的有向边集合，它的元素与网页间的超链接一一对应。 基于上面的网络链接图，我们来进一步定义它的邻接矩阵： 羁。# 婵f ，p e 萄 o 。d t h e r w 泐 p 也就是说，如果网络中有一个由网页j 指向网页的超链接，那么= 1 ，否则 = o 。 目前包括p a g e r a n k 算法【1 】【l z 】 1 3 】【1 8 】【2 0 】在内的大多数链按分析【2 1 】的算法 都是基于上面的邻接矩阵。p a g e r a n k 算法用随机游走模型来模拟冲浪者浏览网页 的行为，从而计算每个网页的重要性。假设冲浪者当前时刻在浏览任一网页。每 一步，髓夕她将以概率口双当前两页所有超链接指向的网页中均匀的选择一个作为 下一步将要浏览的对象，或者以概率1 一口从整个网络中均匀的选择一个网页进行 浏览。对邻接阵彳中所有非零行进行行和归一，我们将得到最初的一个转移矩阵p ， 对p 中全零行处理后( 关于具体的处理方法，我们将在第3 节详细介绍) ， 导到一 个转移概率矩阵。上面的随机游走模型对应的转移概率矩阵则可表示为： ；：口+(1一a)u(3) 这里q 为所有元素都等于1 ，呔这里n 为u 。的维数，也是链接图中钓顶点个数) 的转移概率矩阵。 如果我们用z = “，码，以) 来代表转移概率矩阵声的平稳分布，由遍历定理( 见 $ 3 a 1 定理8 ) 。有； 8 韭 塞 奎 适 太 堂 亟堂焦硷塞 。l i me c 去墓一。删】= 舰去萎z ：玛，4 丘 假定一个网页的点击率越高那么它越重要，那么点击率就可以作为网页重要 性的一个度量。因此平稳分布，r = ( 而，而，以) 就可以认为是网页的重要性得分。网 页越重要，它的链接质量也就越高，这两个是等价妁概念，在以后的谤论串将会 不加区别的引述这两个概念。 在实际计算中，可以用下面的迭代关系来计算平稳分布狐： 霹+ d = 疗( f ) 尹 ( 5 ) 此外，当i 有唯一的主特征值时，平稳分布筇就是的主特征值【2 】。 为了叙述方便，下文中将上面的p a g e r a n k 算法成为经典p a g e r a n k 算法a 1 2 对无出度节点的处理 由于在i n t e r n e t 中存在大量没有超链接的网页。所以在图占中存在大量的无 出度节点，据微软亚洲研究院最新的统计结果，在他们抓取的网页中，无出度网 页的比例大约为5 0 0 , 6 。 无出度节点的存在使得转移矩阵尸不是随机矩阵。因为无出度节点对应行的 行和为0 ，而为了使尸成为随机阵，从而可以利用转移概率矩阵的一些性质，我们 需要对这些无出度节点做一些处理 3 ，以除去这些无出度节点。我们将介绍两种 常用的方法：添边法和加点法。 第一种方法，添边法： 在图占中，给所有无出度节点添加n 条边指向网络中的n 个节点，这也就相当 于在邻接矩阵爿中把所有全0 行替换为全1 行，得到j 。 a = a + r 这里- 岫胁刊维列陋= b 冀为无蝴节点心为n 维 全1 行向量r 气= ( 1 ，1 ，l l 。 对应的有，p = p + v ，其中y = 士震。 第二种方法，加点法： 9 在图g 中，添加一个新节点刀町然后令所有无出度节点指向新加入节点。且 新节点有一条边指向自己，得到新的邻接矩阵j ，它与一的转换关系如下； j = 吾习，其中斤的定义与上相同。 对应的有，户= 言： 。 l 。3转移概率矩阵乒( 或户) 的不可约处理 万维网网络规模庞大，相对于如此大规模的网络来说，每个网页的链接数目 就显得很小了，因此，对应的邻接矩阵a 是规模庞大的稀疏矩阵，转移概率矩阵 为f ( 或户) 的马氏链很可能是可约的，而可约马氏链的平稳分布不唯一，为此， 需要对歹( 或户) 进行不可约处理 4 ，尹= 口声+ ( 卜口) 虬( 或f = 口声+ ( 1 一口) 玑) 。乒 ( 或芦) 为正的随机转移矩阵，所以不可约，又由于在实践中由i n t e r n e t 网络按 照上述办法构造的声( 或芦) 常常满足非周期假设，所以转移概率矩阵为声( 或声) 的马氏链存在唯一的平稳分布。 关于声( 或声) 与乒( 或户) 的谱的关系有如下定理 4 ： 定理1 设随机矩阵乒( 或声) 的谱为【l ，五，五，以l 。那么随机矩阵；= 卵+ ( l a ) u 。 的谱为“口以，毗，吮) 。 证明：见 4 】。 1 4 平稳分布的讨论 根据无出度节点处理方法的不同，我们可得到不同的迭代关系，从而得到不 同的平稳分布 1 9 1 。下面我们分别对上述两种不同的无出度节点处理方法以及直接 利用转移矩阵户进行迭代三种情况分别进行讨论。 在p a g e r a n k 算法的讨论中，经常需要用到g e r s g o r i n 圆盘定理【5 】，为了方便， 我们给出定理的表述： 定理2 ( o e r s g o r i n 圆盘定理) ：设彳= 心k ，又设 足( 彳) ；i 嘞i ，l i n 舞 1 0 表示a 的各去心绝对行和，则a 的所有特征值都位于n 个圆盘的并 u z c ：i z 一吒i 局( 4 ) ) ；g ( 爿) j 埘 中。此外，如果这n 个圆盘中有k 个之并形成一个连通区域，且它与所有余下的( n - k ) 个圆盘都不相交，则在这个区域中恰好有a 的k 个特征值。 由于在迭代中，矩阵的谱起着至关重要的作用，下面引进一个很有用的命题： 命题lz 对于任一个有向图g ，如上定义的转移矩阵p 的谱半径p ( p ) l ，若g 不 包含无出度节点，则尸( p ) = l ，且巳是p 对应于最大特征值1 的左特征向量。 证明：主要应用圆盘定理来证明这个结论，具体证明参见【3 】。 ( 1 ) 按照加边的处理方法。我们可得到最终的转移概率矩阵； p = 口| p + ( 1 一口) 也 对应的平稳分布为矛，由平稳分布的性质，有 蠢：元 代入p 的表达式，可得到 万= 厅( 口p + ( 1 一口) 玑) = 口万p + 士( 1 一c t ) e , ( 6 ) 由上式，可得到石的形式表达： 矛= 音( 1 一口) ( e k a p ) - 1 其中，j k 为n 阶单位阵。 进一步，若瑾 1 ，后= 古( 1 一口) e 。二( a y 由下面的迭代关系，可计算厅 万( 哆= a 万( t - 1 ) p + ( 1 一瑾) 其中，t 为非负整数。 ( 2 ) 按照加点的处理方法，我们可得到最终的随机转移矩阵： 声= 口声+ ( 1 一口) q 对应的平稳分布设为牙，由平稳分布的性质，有 事= i 代入声的表达式，可得到： 孝= g 矛p + ( 1 一口) 牙以“= 口厅尸+ 彘( 1 一a ) 岛“( 7 ) 由上式，可得到的形式表达： 帚= i 百( 1 一口) “( 乓4 h m 。+ 1 ) - a p ) 一。 若口 1 ，牙= 六( 1 一口) + 。= o 局 由下面的迭代关系，可计算牙 矛o ) = 口牙o 一1 ) j p + - j - 、1 一口) “， 为了以下讨论方便，令牙= ( 元，元) 。其中元为原网络图中对应的n 维平稳分 布，元为新加入点的分布值。 ( 3 ) 直接利用转移矩阵，进行迭代： 露o ) = o e l r ( t 一1 ) p + ( 1 一a ) 为迭代的极限，由命题l ，不难证明极限霈的存在。 万= a r g p + ( 1 - a ) l r u = a r r p + 古( 1 一口) 石的形式表达为万= ( 1 一口) ( - z p ) 。 若口 l ，万= ( 1 一口) 巳：= o ( 口尸) 。 需要说明的是，由于p 不一定是随机矩阵，即使初始值设为一个概率分布， 最终迭代算得的石行和也不一定为l 。 下面详细讨论这三个分布之间的关系，我们提出了下面的定理： 定理3 由上面定义的厅，矛，元，把其各维元素和归一后，它们是相同的分布 即 牙：j l ：口_ ， i i 石i li i 元i i 1 2 韭塞銮煎 太堂 亟_ _ j 生j 亟基l 盖 且磊= 告元足+ 去，其中，向量万的l 范数定义为| l 万1 1 2 善l 焉i 证明；将牙= ( 元，元) 代入( 7 ) ，得 t 铂h 编，瞄斗舯瑰， = ( 唬p ，吮r + c 唬) + 肘j - l ( 1 一( r ) + l 故，有元= c e 元p + 击0 一口) 岛 魂= 口元r + a 元+ 古( 1 一口) 由上式整理得，元= t 免r + 六 将乒= p + v ，v = x r e 。代入( 6 ) 式，得 万；口亓p + 古( 1 一口) ；c e 牙( p + l r e ) + 古( 1 一搿k = 口万p + 仃矛r e 。+ 舌( 1 一口) ；口斤尸+ 古( 丽五+ ( 1 一口) ) 比较下面三式 万= c 阢p + 古( 1 一口) 巳 元- - - a 斥o p + - 。t _ 、1 一0 0 e 矛= d 君尹+ ( 簖霞+ ( 1 一口) ) 容易看出，万，矛，元只相差常数倍。又因为芦和户都是随机转移矩阵， 所以有i l 矛i l 爿j 矛j i = l ，所以有 形；j l ：。 肛而2 而。 2 n s t e pp a g c r a n k 算法 经典p a g e r a n k 算法可看作是在网络链接图上( 网页对应节点，超链接对应边) 的一个马尔可夫随机游走模型，用它的转移概率矩阵的平稳分布来度量每个网页 韵重要性。假设一个冲浪者正在浏览网页口，那么这个冲浪者将会在a 的超链接指 向的网页中随机的选择一个作为下一步将要浏览的对象。以图l 为例，网页a 有 三个超链接分别指向b ，c 、d ，那么冲浪者将会以相同的概率l 3 选择这三个网页。 换言之，这个马氏链的转移概率只和当前网页的一步链接信息有关。 就我们所知，上面的马尔可夫模型在很多实际应用中通常并不是最好的选择。 以计算机象棋对弈【6 】为例，“深蓝”能够战胜象棋大师的关键就是在相同的时间内 它可以预测更多步以后的所有棋局形势。也就是说，对弈者知道的信息越多，那 么他她就有更大的概率做出正确的选择。同样的道理，在p a g e r a n k 算法中，如果 冲浪者知道更多的链接信息( 比如，如果冲浪者选择了b ，c ，d 中的一个，他她 在跳转n 步后分别可以到达的网页个数) ，那么f 酊她就会为了尽可能获取更多的 信息丽以完全不弼的概率去选择三个网页。这就是我们提出n - s t e p p a g e r a n k 的初 衷。容易看出，n s t e pp a g e r a n k 是经典p a g e r a n k 的一般形式，经典p a g e r a n k 是 n - s t e pp a g e r a n k 在n = i 时的特例。 图i n - s t e p 的圈不 为叙述方便，我们将在第1 小节中给出n s t e pp a g e r a n k 算法的具体介绍：第 2 小节介绍实验部分，实验结果表明我们的算法在提高搜索的精确度上比经典 p a g e r a n k 有所提高，m a p 指标提高了超过1 5 ；第3 小节用数学的方法对n - s t e p p a g e r a n k 做进一步的分析：最后一节对n - s t e pp a g e r a n k 进行总结并提出未来工作 展望。 2 1算法介绍 在经典p a g e r a n k 算法中，当冲浪者选择下一步要浏览的网页时，他她只知道 当前网页的一步链按信息，以均匀的概率在当前网页的超链接指向的网页中选择 下一个进行浏览。但是事实上，冲浪者通常会用自己的知识去判断哪一个网页更 为重要，然后以较大的概率去选择包含更多信息的网页。受计算机象棋对弈的“多 看几步”策略的启发，我们假定网页连出的超链接数目可表示它的信息含量的多 少，也就是说，冲浪者跳转n 步后到达的网页越多，他她能得到的信息也越多。 我们可以根据n 步的链接信息来写出n s t e pp a g e r a n k 的转移概率矩阵。我们以图 l 为例更清楚地说明这个观点。 设冲浪者正在浏览网页a ，按照经典p a g e r a n k 算法，在选择下一个网页的时 候，只能“看一步”，也就是说，冲浪者所知道的信息仅仅是下一步可以连接到网 页b ，c d ( 图1 中虚线圆圈定的部分) ，而对网页6 ，c ，d 本身的链接情况则一 无所知，那么他她将会以同样的概率选择网页b ，c ，d ，p 旷- p 。- p 。d - 。但在我 们的n - s t e pp a g e r a n k 算法中，冲浪者在选择下一步要测览的网页时，可利用更多 的信息来做选择。以2 - s t e pp a g e r a n k 为例，当冲浪者在选择网页b c 、d 其中之 一作为下一步浏览对象时，他她可以“看两步”，也就是说他她还知道网页b ，c 、 d 一步的链接情况，那么网页b 、c ，d 被选择的概率与它们各自的出度成正比。即 如= 号，儿= 吾，鼬= ； 在3 - s t e p p a g c r a n k 算法中，网页b c ，d 被选择的概 率与它们各自跳转两步后最终到达的网页个数成正比；以此类推，在n s t e p p a g e r a n k 算法中，网页b ，c ，d 被选择的概率与它们跳转( n - 1 ) 步后最终到达的 网页个数成正比。 下面我们给出n s t e pp a g e r a n k 算法的转移概率矩阵的具体表达形式。 n - s t e pp a g e r a n k 算法的转移概率的定义如下：对于图g = 中任意两顶点 f - ， = 互= 羚这里巧册是顶点j 经n 步跳转后到达的网页个数， ，崩g ， d o = ( 1 ，1 ，1 ) ： 命题2n s t e pp a g e r a n k 算法的转移矩阵 p ”；( d ”) 。1 彳“ ( 1 1 其中么为有向图g 的邻接阵，d ( ”为向量d ”中元素做成的对角阵， d ”= a d ”= d ”，d ”中各维元素即为图g 中各点跳转( n 1 ) 步后最终到达的 点数( 注；这里( d ( ”) 。为广义逆，并且若d “中某对角元素为0 ，( d “) 一1 中对应 位置的元素也取为o ) 。 证明4 d ( “) = ( ”) 。1a d “1 = q t 研n ，q 2 趣- “，q 。碟棚 x d ( i n - 1 ) ，a 2 2 x d n - d a 2 。碟“ a n ix d ( n - 1 ) , 2 惩n ，谚胁” 鱼! ! 垡：! ：鱼2 1 垡：鱼。! 篓! ： 研” 研” 研 a 2 l 硝川呸2 暖- 1 呸。穰棚 碰棚 趟州 趔m 鱼s 兰垡：! ! 堡2 兰墨竺! 纽! 垡：兰 穰柳 磁m谚 注意到d 州= a d 州，即研聊= 巧“o j - i 不难看出岛蛳= 曼鼍；孚= ( d 柳) - 1 a d ( “l 由命题2 ，我们可以利用图g 的邻接矩阵a 很容易的计算出n s t e pp a g e r a n k 算法的转移矩阵p c 。因为d 是对角阵，而且其中某些对角元素有可能为o ，所 以n = s t c pp a g e r a n k 的转移矩阵p ”比经典p a g e r a n k 转移矩阵p 更为稀疏，这在 计算平稳分布时可用来加速收敛速度。 2 2实验设计 本小节。我们将利用$ 1 2 和$ 1 3 的方法对n - s t e pp a g e r a n k 算法的转移矩阵 ”处理，得到耳。用乒“计算平稳分布石，用强迭代法，利用下面的关系式 进行迭代： 万”( ，) = ( 只m ) 7 ，r ”一1 ( r ) ( 2 ) 初始值石椰( o ) 可取任意分布值，并不影响最后结果，本实验中，取n = 2 。 为方便n - s t e pp a g e r a n k 算法和经典p a g e r a n k 算法做比较【1 7 】，我们采用 t r e c 2 0 0 3 t 作为本实验的数据集。这个数据集采集自2 0 0 2 年g o v 域，抓取了 1 , 2 4 7 ，7 5 3 个网页，其中1 , 0 5 3 ，1 1 1 个是h t m l 格式的，我们的实验就是利用这些h t m l 1 6 韭塞銮适太堂亟 堂焦 监 塞 网页的链接信息。 实验中的检索词来自t r e c 2 0 0 3w 曲t r a c kt o p i cd i s t i l l a t i o nt a s k 共有5 0 个， 每个检索词都列出了和它相关的网页以及相关的程度，这些都是人为标注好的。 对每个检索词，给出的被认为是“答案”的网页( 由t r e c 会议组给出) 从1 个 到8 6 个不等，平均为每个检索词1 0 3 2 个。 2 2 1 评估方法 对于每个检索词，我们首先利用b m 2 5 1 8 来计算每个网页与检索词的相关度 得分得到向量$ c o y e m ，然后选择相关度排前2 0 0 0 的网页出来，与p a g e r a n k 计 算出来的重要度得分进行组合： 联a 鼍hb = a x 乳研弓h + o 一面，c 搿鼍f - 霄 ( 3 ) 最终返回的网页顺序按s c o 心。值由大到小给出。 本实验中，我们采用目前被广泛使用的评价标准来评估搜索的精确度： p n ( m e a np r e c i s i o na ln ) 【9 】，a n dm a p ( m e a na v e r a g ep r e c i s i o n ) 【9 】。 a ) 坳( m e a np r e c i s i o n a tn ) p 度量了对于一个检索词，返回结果的前n 个网页击中目标网页( r e l e v a n t ) 的比例； pn；#relevantdoc3intopnresults( 4 ) n 举例来说，如果对于一个检索词的搜索结果，前l o 个网页为 目标网页，非 目标网页，非目标网页，目标网页，目标网页，目标网页，非目标网页，非目标 网页，目标网页，目标网页 ，那么对于这个检索词从p l 到p i o 的值分别为 l ，t 2 ，1 3 ，2 4 ，3 5 ，4 6 4 7 ，4 8 ，5 9 , 6 1 0 。 对于一系列检索词，我们通常对所有检索词的e n 取平均得到最后的平均 跑撑值。由于目前大多数的搜索引擎( 例如g o o g l e ，y a h o o ! s e a r c h , 和m s ns e a r t h ) 返回搜索结果时每页显示i o 条结果，冲浪者们大多数时候也只看第一页返回的结 果，所以我们用1 0 1 0 来评估排序算法。 1 v l g p ( m e a na v e r a g ep r e c i s i o n ) 对于单个检索词，平均精确度( a v e r a g ep r e c i s i o n ) 定义如下： 1 7 ( 以一) 硝( 一” 矗p = # t o t a l r e 2 l e l v a n t d o c s f o r t h i s q u e r y 这里，n 为返回网页的总数，以田为a ) 中定义的p n 值，腭定义如下； 叫( 帕：j 1 矿月一脯西”抽t h e h i t l i s f i 3 r e l e v a n t 1 0 ，o t h e r w i s e 与p n 类似，对一系列检索词取平均后，得到m a p 。 2 2 2 实验结果 图2 给出了两种p a g e r a n k 算法的m a p 值和p i o 值比较曲线。可以看出，我们 的2 - s t e pp a g e r a n k 算法几乎一致的超过经典p a g e r a n k 算法。这显示出利用多步链 接信息对于排序算法精确度有所提高。 1 8 拙塞窑适太堂亟土堂焦硷塞 ( b ) 图工搜索精确度对比( a ) m a p ( b ) v i o 为了进一步对比，表l 列出了两种p a g e r a n k 算法的最优值( 对应于国2 中的 最高点) 。从表中可以看出，2 - s t e pp a g e r a n k 算法的最优值比经典p a g e r a n k 算法 的高很多，2 - s t e p p a g e r a n k 算法的m a p 值比经典p a g e r a n k 算法提高了超过1 5 ， p i o 也比经典p a g e r a n k 算法提高了6 。注意到两组p a g e r a n k 值分别和r e l e v a n c e 值做组合后的搜索精确度均比只用r e l e v a n c e 值的精确度高，这说明链接分析对于 提高搜索精确度的有效性。 表1 最优值对比 r a n k i n gm e t h o d s m a p p j o r e l e v a n c eo n l yo 1 2 4 3 o 1 0 4 2 - s t e pp a g e r a n k + r e l e v a n c e o 1 8 9 1 0 1 3 4 p a g e r a n k + r e l e v a n c e o 1 6 3 9o 1 2 6 b e s tr e s u l to nt r e c 2 0 0 3 7 1o 1 5 4 3 0 1 2 8 2 2 3 实验讨论 1 9 丝 廛 銮 适 太 堂 亟土 堂 焦i 幺塞 圈3 网络中的环 在n - s t e pp a g e r a n k 算法中，环和多重路有可能对结果产生影响，而网络图的 结构非常复杂。目煎还没有找烈一个方法去量化它们的影喻。如图3 ，环 b 寸甜寸v 斗b 的存在使得在3 - s t e pp a g e r a n k 的计算时，网页b 多加了自己做为权 重。 我们做了一个小实验，来检验这种影响的大小。在2 - s t e pp a g e r a n k 计算中， 自环和长度为2 的环有可能对结果产生影响，在转移概率计算时，我们把指向自 己的长度为1 或2 的环不计算在内。 实验中我们做了一个统计，在我们的数据集中。自环的比例很小，不到r e - 6 。 有向边总数为1 0 7 5 4 7 3 7 ，平均每个节点大约1 0 条边，长度为2 的环所占比例约为 o 1 2 ，把这些重复计算的点在计算出度时候去掉之后，所得到的2 - s t e pp a g e r a n k 值和原来计算的2 - s t e pp a g e r a n k 值进行比较，我们发现它们的值很接近，几乎没 有竹么变化。 2 3 算法分析 a ) 三种平稳分布表示形式 对应于s t 4 中，经典p a g e r a n k 的三种表示形式。我们可相应的得到n - s t e p p a g e r a n k 算法的三种平稳分布表示形式。具体推导与经典p a g e r a n k 相同，不再重 复。 ( 1 ) 按照加边的处理方法，我们可得到最终的转移概率矩阵： 乒”= 口乒+ ( 1 一口) 以 韭 塞 銮煎太堂亟堂焦诠塞 矛椰= ( 1 一口) ( 巨舢一a p ) 叫 ( 2 )按照加点的处理方法，我们可得到最终的随机转移矩阵： 芦卅= 口j 争帅+ ( 1 一口) 以 牙辨= 杀t ( 1 一口) “( + l h ( + j ，一口产脚) - ( 3 ) 直接利用转移矩阵p 进行迭代： 7 一= 筋州p + ( t - a ) x 讲玑= c 跟州p + 古( 1 一口) 石州= ( 1 一口) ( j e - a p ) 一 又f “= 珥1 a d 一i ，而p = p = d , - a 当口 1 时，经典p a g e r a n k 算法有： 万； ( 1 一口) 二。( 盯p ) 。= 古( 1 一口) 二( 口d f l 爿) 。 相应的，n - s t e pp a g e r a n k 算法有： 万聊= 士( 1 一口) ( c t “町) = 舌( 1 一口) ( 口环4 口0 ，y ”收敛速度分析 与经典p a g e r a n k 相似，我们可由转移矩阵”变换得到不可约随机矩阵芦” ( 或只”，) ，由遍历定理，我们知道对应的马氏链有唯一的平稳分布万“， 万( m = 疗l ”，芦。我们仍用万 作为网页重要性的度量。我们可以像( 5 ) 式那样用强 迭代法计算l “。下面我们将具体讨论对应这种迭代n - s t e pp a g c r a n k 韵收敛速度。 我们用万柳( o ) 来代表迭代的初始分布向量，石”( f ) 代表t 步迭代后的分布。 定理4 对应强迭代法j f 册( f + 1 ) = 帚一) r 口w ( f ) ，n - s t e pp a g e r a n k 的平稳分布可写为 如下形式： 万”= 伽”p 聊+ ( 群，。硝+ 古( 1 一口) ) 这里，d 为对应m 中全零行的顶点的集合： 2 l 韭 毫 窑堡太茎亟里毽监塞 d = 川= 0 , i e v 收敛速度 万”一万”( o i l - a i i x ”一万”( 0 ) i l s 2 a 证明：由平稳分布的定义，有 疗”= 万”歹聊= 口声聊+ 万”( 1 一口) 以( 1 2 ) 并且癣”= 1 矩阵玑与( 3 ) 中定义的相同，所以有 珑孵= 士 这里，仍为全1 行向量。 令州横疳 ：；等删，有 尹；p + 专r e ， 将等式( 9 ) ，( 1 0 ) 代入( 7 ) ，得 万 = ，r 舯( a p + ( 1 一口) 以) = 仰州p + c r 万椰r e + 音( 1 一口) = c r 石”p 一+ 盯( ：，：，巧“) + 古( 1 一口) 巳 = c 院”p 呻+ ( 口( 坨。癣螂) + 吉( 1 一口) ) 由于 万刖( f ) = c 协即( t - i ) p 帅+ ( 盯c e 缸d 硝) + ( 1 一名城 所以，有 ”一万”( t ) i l = l l a 石柳p + ( 口c 刀j ”) + 古( 1 一口) ) 一c ：”( t - d p 蝉一( 口( 。碍”) + 音( 1 一口) ) 气| ； 爿l 筋椰p 一伽。帅( f 1 ) j p 帅i i 爿i 口( 窟”一万”( f 1 ) ) 一”i i 爿l 口( 万“一窟”( o ) ) ( 尸“y 令x = “，x 2 ，矗) ，则 0 0 ) j b塞变亟太堂亟主堂僮盈塞 i ix p 即i i 爿l ( p 五，硝薯，( 1 x , ) l l j 】l - li s l 刮p i + l p 譬l + + i 而i j 。lj _ l加l s 硝+ 硝+ + 群i x , i t - 1l - i，1 = ( 彤) + ( 彤) l 而f + + ( 硝) l 注意到p 罗= o o r1 ，所以 z - i n 聊i i - - ( y , 彤) + ( 彤) i 而| + 十( 甜) i j lj