（概率论与数理统计专业论文）基于pagerank排序算法改进的若干研究.pdf

硕士擘位论文 m a s t e r st i t e s i $ 摘要 全球资讯量最大，查询次数最多，知名度最高的搜索引擎是g o o g l e ，而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 算法利用了w e b 的结构信息来判断网页的重要性，而且计算排 名过程中将同一页面的所有链出页面看成同等重要，即对每个链出页面平均分配其 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 算法的思想；通过m a t l a b 实验迭代结果，比较传统 p a g e r a n k 算法和改进算法的计算结果，证明改进算法提升重要网页的p a g e r a n k 值， 降低不重要网页的p a g e r a n k 值，而且能用d 0 ，则称自状态i 出发可达状态， 记为i 一。如果i 专j 且歹ji ，则称i ，j 相通，记为f 付，。若一马氏链的任意两 个状态都相通，则称为不可约链。 定义5 ：首达时间 毛= i n f n ：n l ，x 。= ，x 。= i ) 若右边为空集，则令毛= 。 瓦表示从i 出发首次到达j 的时间；瓦表示从i 出发首次回到f 的时间。 定义6 ：首达概率 一”) = p 圾= n x 。= f ) = p x 。= 歹，以j ，l 七n - 1 x 。= f ) ：马氏链从状态f 5 硕士擘位论文 m a s t e r st h e s i s 出发经 步后首次到达状态，的概率。 厶= 乃“) ：马氏链从状态f 出发经有限步首次到达状态j 的概率。 ，l = l 厶= ) = p 纯 o o 凰= m k = l 定义7 ：若工= 1 ，称f 为常返态，即马氏链从i 出发经过有限步再回到i 的概率 为l ；若厶 l ，称i 为周期的；若c ，o ) = 1 ，称i 为非周期的。 定义l o ：若状态f 为正常返的且非周期的，称i 为遍历状态。 2 3 状态空间的分解 定义l l ：设ccs ，称c 为( 随机) 闭集，如对任意i c 及诺c ，都有p 打= 0 。 闭集c 称为不可约的，若c 的状态相通。 闭集c 的直观意义是自c 内部不能到达c 的外部，这意味着系统一旦进入闭集 c 内，它就永远在c 中运动。 定理2 ：设c ，则它可分为若干个相互不相交的闭集扛。 ，使 c = c 。uc ，u ，且有 1 c 。中任意两状态相通： 2 c 。nq = ，办z ，即c 。中任一状态与q 中任一状态互不相通。 定理3 ：状态空间s 可分解为 s = t u c = t u c lu c 2u 其中， e j 为不可约常返闭集，t 不一定是闭集。 定理4 ：若s 为有限集，则丁一定是非闭集，亦即不管系统自什么状态出发， 最终都进入常返闭集。 推论l ：有限不可约马氏链的状态都是常返的。 6 硕士学位论炙 m a $ t e r st h e s i s 2 4p “的极限性态与平稳分布 定义1 2 ：一个定义在s 上的概率分布石= p 。，石：，石。) 称为马氏链的平稳分布， 如有 石= x p 。 即s ， t 氕j2l 死t p q o 平稳分布也称马氏链的不变概率测度。对于一个平稳分布万，显然有 7 = 舻= 护2 = = 才”。 定理5 ：设口。，z 0 ) 为马氏链，则 。，刀0 ) 为平稳过程的充要条件是 刀( 0 ) = ( j i r i ( 0 ) ，f s ) 是平稳分布，即 万( 0 ) = 万( 0 ) p 。 定理6 ( 遍历定理) ：不可约遍历链恒有唯一的平稳分布乃= ( 万。，万：，7 。) ， 即 乃= 去 是方程组 x = j c j p 9 满足条件x ，o ，歹s ，x ，= l 的唯一解。 ，t 定理7 ：若- ，非常返或零常返，则对任意状态空间中的任一状态f s ，有 l i mp 9 ) = 0 。 定理8 ：若是遍历状态，则对任意的i s ，有 1 i r n p ) = 鱼。 h p j 定义1 3 ：若舰石g ) = 石；( ，s ) 存在，则称刀+ = 仁i ，万；，一万；，) 为马氏链的极 限分布。 定理9 ：非周期不可约链是正常返的充要条件是它存在平稳分布，且此时平稳 分布就是极限分布。 推论2 ：有限状态马氏链的平稳分布总存在；有限不可约非周期马氏链存在唯 一的平稳分布。 7 硕士学位论之 m a s t e r s 丁h e s i $ 第三章传统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 算法，并对其进行一些分析和讨论。 搜索引擎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 实现的一个原型系统，现在已经发展成为w w w 上最好的搜索引擎之一。g o o g l e 的体系结构类似于传统的搜索引擎，它与传统的搜索引擎最大的不同之处在于对网 页进行了基于权威值( 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 值越高的网页，在结果中出现的位置越前【7 】。 简单的说，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 值也是一定的，它是文件固有的评分量。 3 1 算法解析 算法基于“从许多优质的网页链接过来的网页，必定还是优质网页”的回归关 系，来判定所有网页的重要性。g o o g l e 认为当某个网页有链接到另一个网页时，它 就对该网页“投了一票”。一个网页的得票越多，则认为它的重要性也就越高，投 票网页的重要性也决定着票本身的重要程度。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 值。 为方便书写，下记网页a 的p a g e r a n k 值为v r ( a ) 。 举个简单的例子，四个页面的链接关系如下图： 8 硕士学位论交 m a s t e r st h e s l s 1 5 图3 一l l 设图3 一1 1 中网页么的p a g e r a n k 值为0 9 ，有三个超链接分别是网页b 、网页c 和网页d ，故这三个超链接页面分别分得网页a 的p a g e r a n k 值为o 3 。依此思想， 最终p q 个网页的p a g e r a n k 值的分别：网页a = 网页c 、网页召= 网页a 、网页c wi | 网页a + 1 网页b + 网页d 、网页d = 1 网页彳+ 三网页b ，则由上述算法列方程组可 得：p r ( a ) - - 0 9 ，朋( 日) = o 3 ，艘( c ) = o 9 ，朋( d ) = o 4 5 。 下面给出p a g e r a n k 排序算法的计算公式。 p a g e r a n k 的基本思想是一个网页的重要性在于，或者有超链接指向它的网页 多，或者有超链接到它的网页重要，或者二者兼而有之。其初始定义如下： e r ( a ) = 窆i = l 帮 ( 3 ) 其中网页i 为超链接到网页a 的页面，c 亿) 为网页z 的出度，扛1 , 2 ，挖 显然p a g e r a n k 计算公式满足：1 ) 网页彳的链接源页面数越多，即玎越大，则 网页彳越重要，艘0 ) 值就越高；2 ) 网页a 的链接源页面的级别越高，即p r 亿) 值 越高，则网页a 越重要，袱0 ) 值就越高；3 ) 网页z 的超链接数越多，即c 亿) 值 越高，则网页彳能分得z 的p a g e r a n k 值越低，朋0 ) 值越低。 用公式( 3 1 1 ) 定义的直观意义是，假设浏览者当前在浏览某一网页z ，下一 步他将从当前页面的超链接页面中均匀地选择任一页面浏览。可并不是所有用户都 会顺着超链接进行浏览，g o o g l e 统计出用户会顺着超链接浏览页面的概率为0 8 5 ， 故给出阻尼因子d ( 取为o 8 5 ) ，从而计算p a g e r a n k 值的公式定义为： 瑚陆( 1 - a ) “喜器 ( 3 他) 9 硕士学位论之 m a s t e r st h e s i s 用公式( 3 1 2 ) 定义的直观意义是，假设浏览者当前在浏览某一网页正，下一 步他要么以概率d 笔男从当前页面粤超链接页面中均匀地选择任一页面浏览，要 么以概率i d 在w e b 中均匀地选择任一页面进行浏览。 w e b 中存在的大量独立网页，用公式( 3 1 1 ) 计算的独立网页p a g e r a n k 值为0 ， 公式( 3 1 2 ) 计算的p a g e r a n k 值为0 1 5 ，显然都不合理，前者过低，后者过高。 于是g o o g l e 又给出公式： p r ( a ) = 导“喜搿 ， 其中n 为w 曲中网页总数。 用公式( 3 1 3 ) 计算的独立网页p a g e r a n l ( 值为0 ，1 _ _ 2 ，5 ，公式定义的直观意义是， 假设浏览者当前在浏览某一网页正，下一步他要么以同样的概率d ! 苫署从当前页 面的超链接页面中均匀地选择任一页面浏览，要么以概率善在w e b 中均匀地选 一 择任一页面进行浏览。 3 2 解p a g e r a n k 值 在网页数比较少的情况下，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 算法是先建立w e b 网的邻接矩阵，然后把该矩阵处理成马氏链的转 移概率矩阵，p a g e r a n k 被定义为该马氏链的平稳分布，或该马氏链的不变测度。详 细计算如下： 通常把w e b 网的网页看成节点，超链接看成有向边，这样形成有向图 g = ( y ，e ) ， 其中v 是节点( 网页) 集，e 是边( 当且仅当存在从页面i 到页面的链接时存在 从节点i 到节点，的边) 集。基于网络结构链接图，定义它的邻接矩阵： l l ，f e g # 1o , o l p 刑妇 l o 硕士举位论文 m a s t e r st h e s i s 即若w e b 中有网页f 指向网页_ ，的超链接，那么g ，= l ，否则g = 0 。目前包括 p a g e r a n k 算法 8 3 1 9 1 0 1 1 1 1 1 2 1 3 在内的大多数链接分析【1 4 】的算法都是基于上面 的邻接矩阵。将邻接矩阵g 中所有行进行行和归一，得到一马氏链的转移概率矩阵 p = 【p 。，】m 。然后就可以给定任意初值进行迭代计算。 要保证上述迭代过程的收敛，矩阵p 必须满足两个条件：一是p 必须是不可约 的( g 强相通) ：二是p 必须是非周期的【1 5 】。这两者可以通过在迭代过程中加一个 阻尼因子予以保证，即若记p = 【l 】j 。，v = l 吉l ，e = e r v ，则有4 = o - d ) e + 卯。 l j vj l x 这样得到的矩阵a 为非周期不可约，能保证迭代过程收敛，即任给初值x 。，满足 墨= x o a ，五= x 。a ，x 州= 彳t a ，oo * o t i i 则x = x a 。 如上定义的矩阵a 也为马氏链且非周期不可约，则存在唯一平稳分布 x = g ，x ：，x ) ，满足划= x ，由矩阵彳的构造知，彳的最大特征值为l ，x 即 为么的最大特征向量。则由随机过程的遍历定理( 见2 4 的定理6 ) 知： l i me l l 土m k = 0 一瞬) l2 l i mm 三荟口灶t 口j 因此马氏链的平稳分布x = b 。，z ：，h ) 就度量了网页的重要性。 硕士学位论交 m a s 丁e r s1 h e s l s 第四章p a g e r a n k 新算法 4 1 传统p a g e r a n k 算法缺陷 近几年很多学者对传统p a g e r a n k 算法进行不断的改进，主要是因为传统 p a g e r a n k 算法存在以下问题： ( 1 ) 传统p a g e r a n k 算法只利用了w 曲的结构信息来判断网页的重要性，忽视 了内容、用户行为等信息对网页重要性的影响。针对p a g e r a n k 算法主题漂移现象， 【8 】提出二阶相似度改进算法、【9 】提出一种t o p i c p a g e r a n k 算法、【1 6 】提出了主题敏 感的p a g e r a n k ； ( 2 ) 传统p a g e r a n k 算法是给予随机冲浪模型而设计的。从定义公式( 3 1 3 ) 式 的d 窆笔裂部分可以看出，在传统p a g e r a n k 算法的计算过程中，所有网页把自 ，= i o v j ， 己的p a g e r a n k 值p r ( r , ) 平均分给它超链接网页，这样很大程度上影响了网页i 超 链接网页的p a g e r a n k 值。从另一角度讲，假设用户当前浏览的网页为正，该页面 有c 亿) 个链接指向其它网页，传统p a g e r a n k 算法认为用户下一步浏览这c 亿) 个页 面的概率都足相同的筹。而实际情况是：随着用户浏览这c 亿) 个页面次数的 增多，以及浏览这c ( z ) 个页面用户数的增多，大部分用户将会趋向于首先浏览那 些与当前页而内容相关性大的下一个页面，而不是随意浏览。也就是说，实际用户 浏览这c 亿) 个页面的概率是不同的，这正是传统p a g e r a n k 算法的问题所在，也是 本文对其进行改进的切入点。针对p a g e r a n k 算法平均分配权威值( p a g e r a n k 值) 问题，【1 0 】根据网页正向链接所占比重替换阻尼因子d 从而解决平均分配问题、【1 7 】 根据多步链接信息分配权重、【1 8 】根据网页反向链接与正向链接所占比重分配权重。 4 2 算法改进思想 下面介绍本文对传统p a g e r a n k 算法改进的新算法，首先分析下面两个网络简 化图。 1 2 硕士擘位论文 m a s t e r st h e s i s lu 图4 2 一l 首先考虑图4 2 一l 的第1 1 种情况，i i 中四个网页若看成同等重要就不符合实际， 网页应该根据其超链接网页的重要性不同分配不同权重的权威值，那么应该根据什 么标准分配才公正且符合实际呢? 既然网页的每条链入都是给自己“投票”的网页， 一个网页得到的“票数”越多就越重要，所以就由一个网页的超链接网页的各自“票 数”所占权重来分得这个网页的权威值。如图4 2 1 的i i 中，网页a b o u t 超链接到 网页h o m e 和网页p r o d u c t ，由于两网页不是同等重要，网页h o m e 和网页p r o d u c t 不是各自分得网页a b o u t 权威值的二，而是因为网页h o m e 有3 个网页链入，网页 2 p r o d u c t 有1 个网页链入，链入代表了重要性，则网页h o m e 分得网页a b o u t 权威值 的兰，网页p r o d u c t 分得网页a b o u t 权威值的。由此思想得出新算法： 3 + lj + l p r ( a ) ：导+ d 壹善蝴亿) ) 川 扛1y i - _j = i 其中n 一是网页彳的链入网页数，n j 是z 超链接，s ：，s 。网页中第_ ，个页面 的链入网页数，f = 1 ，2 ，门，= 1 , 2 ，m 改进思想是若网页z 顺向链接有s 。，j ：，s 。共m 个页面( 包含a ) ，它们各自 的链入网页数与所有m 个网页的链入网页数之和的比值就是网页么获得网页z 权 威值的权重，网页l 就根据这个权重分配它的权威值，这里网页z 的所有超链接所 占权重之和为l ，即保证了邻接矩阵的行和为l 。 4 3 初步实验结论 进而我们比较一下改进的p a g e r a n k 新算法与传统p a g e r a n k 算法的联系和区 别，由图舢2 1 的第一种链接情况可看出两种算法的联系，第二种链接情况可看出 两种算法的区别，将这两种链接情况的p a g e r a n k 值用两种算法分别计算，结果于 1 3 硕士学位论文 m a s t e r 。st h e s i s 下表中： 表4 - 3 一l 传统算法和新算法计算图i 中网页的p a g e r a n k 值及排名 表4 3 2 传统算法和新算法计算图i i 中网页的p a g e r a n k 值及排名 从表4 。3 1 可以很清楚的看到对于网页同等重要( 链入数相等) 的链接结构， 传统算法和改进的新算法计算的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 值；g o o g l e 给出的传统算法计算 的排名绝对公正正确，改进的新算法没有改变排名证明其算法的可取性。 新算法对传统算法的p a g e r a n k 值有所改变可没有改变排名，下面我们继续分 析当采用新算法计算网页p a g e r a n k 值时，阻尼因子d 取何值可以达到传统p a g e r a n k 算法计算的结果。 1 4 硕士擘位论炙 m a s t e r st 玎e s i $ h a p m d 值 图4 - 3 1 网页同等重要时( 图i ) 网页的p a g e r a n k 值与d 的取值无关 采用新算法计算p a g e r a n k 值时，对于网页同等重要( 链入数相等) 的链接结 构，d 值的变动同样( 与传统算法一致) 对p a g e r a n k 值没有影响。下面看网页不 是同等重要( 链入数不等) 的链接结构情况，表4 3 3 是新算法中d 应取何值结果 会与传统算法一致，图是两种算法随d 取值变动的变化曲线： 表4 - 3 3 新算法中d 的取值做相应的改变计算结果与传统算法一致 1 5 硕士擘位论文 m a s t e r st h e s i s d 值 图4 - 3 2 网页不同等重要时( 图i i ) 网页的p a g e r a n k 值随d 在 0 ，1 间取值而变化，要达 到相等的p a g e r a n k 值，新算法取到的d 值较小 经过初步实验得知，采用新算法计算网页p a g e r a n k 值时，可以取d r = x ( d ) i - - d p r 弦p ) = 0 一咖r ( 5 2 1 ) 对于所有的d 【0 ，1 】，彳p ) 都是马氏链；对于d 1 时，彳p ) 为非周期不可约的 马氏链。因而对于d 0 8 5 ，x p ) 都有稳定的解。 若记( 1 一d p r = ，则( ，一d p 7 弦= y ，由矩阵的条件数的定义，分别求出，一卯r 和( ，一d p r 广1 的一阶范数， 2 0 中给出i i i d p r8 ，= 1 + d ，忖一d p r - 1 | l i = l ( 1 一d ) ， 即矩阵的条件数为： 2 l 硕士学位论炙 m a s t e r st h e s i s k = 卜d p 训卜d p 卅。= 函l + d 2 这个条件数给出了数值求解得到一