PageRank算法的阻尼因子值

邵晶晶

（云南大学 滇池学院 计算机科学技术与电子信息工程系，昆明 650228）

PageRank算法的阻尼因子值

邵晶晶＊

（云南大学 滇池学院 计算机科学技术与电子信息工程系，昆明 650228）

针对传统PageRank算法平均分配PageRank值给每个超链接网页这一缺陷，提出了改进的PageRank算法，并证明如果Web网的邻接矩阵P包含至少2个不可约闭子集，则非周期不可约矩阵的次特征值为d且至少2重.为了降低解PageRank近似解的误差和提高幂法的收敛速度，用lingo算得d取0.71，且知若采用改进的PageRank算法用小于0.85的d值可以达到传统PageRank算法的计算结果.

PageRank算法；次特征值；阻尼因子值

1 传统PageRank算法

1.1 算法解析

Google的体系结构类似于传统的搜索引擎，它与传统的搜索引擎最大的不同之处在于对网页进行了基于权威值（PageRank值）的排序处理，使最重要的网页出现在结果的最前面.Google通过PageRank排名算法计算出网页的PageRank值，从而决定网页在结果之中的出现位置，PageRank值越高的网页，在结果中出现的位置越前［1］.计算公式如下：

其中，n为网页总数，d为阻尼因子取值0.85，网页Ti为链接到网页A的页面，C（Ti）为网页Ti的出度，i＝1，2，…，t.

1.2 解PageRank值

Google采用幂法计算网页的PageRank值的近似解，即先给每个网页一个初始值，然后循环进行无限次迭代得到结果.

PageRank算法是先建立Web网的邻接矩阵，然后把该矩阵处理成非周期不可约马氏链的转移概率矩阵，PageRank被定义为该马氏链的平稳分布，或该马氏链的不变测度.详细计算如下：

基于网络结构链接图，定义它的邻接矩阵G＝（gij）n×n，若 Web中有网页i指向网页j的超链接，那么gij＝1，否则gij＝0.目前包括PageRank算法，文献［2－7］在内的大多数链接分析，文献［8］的算法都是基于上面的邻接矩阵.将邻接矩阵G行和归一，得到矩阵M ＝（mij）n×n.矩阵M 必须满足两个条件才能保证迭代过程收敛：一是M必须是不可约的（G强相通）；二是M 必须是非周期的［9］，同时保证M是随机的马尔可夫概率转移矩阵.则首先将M的全0行处理成全1行，然后行和归一得到矩阵P，最后在迭代过程中加一个阻尼因子d即可.即若记

这样得到的矩阵A为列随机阵且非周期不可约，能保证迭代过程收敛.

幂法是计算实方阵的按模最大的特征值及相应特征向量的一种迭代法.实方阵A有n个不同的特征值，最大特征值为1，故A有n个线性无关的特征向量对应特征值有1＝｜λ1｜＞｜λ2｜≥… ≥｜λn｜.任给初始向量x→0≠0→，x→0可由向量组线性表示，由迭代公式＝（k＝0，1，2，…），得到一向量序列（α1，α2，…，αn不全为0的实数，且α1≠0），不妨取α1＝1，即

2 改进的PageRank算法

改进的PageRank计算公式：

其中，INA是网页A的链入网页数，INj是Ti超链接s1，s2，…，sm网页中第j个页面的链入网页数，i＝1，2，…，t，j＝1，2，…，m.

改进思想是若网页Ti超链接有s1，s2，…，sm共m个页面（包含A），它们各自的链入网页数与所有m个网页的链入网页数之和的比值就是网页A获得网页Ti权威值的权重，网页Ti就根据这个权重分配它的权威值，这里网页Ti的所有超链接所占权重之和为1，即保证了邻接矩阵的行和为1.

3 矩阵次特征值

矩阵A是列随机矩阵，若将矩阵A的特征值按从大到小的顺序排列，记其第i个特征值为λi，则1＝｜λ1｜＞｜λ2｜≥ … ≥｜λn｜≥0.

定理1 若矩阵P包含至少两个不可约闭子集，则矩阵AT存在特征值为d，至少2重.

由文献［11］知，矩阵P有特征值为1，至少2重，取矩阵P的对应于特征值1的两个线性无关的特征向量

① 先证矩阵P的任意一个对应于特征值αi的特征向量，若其与向量正交，则是矩阵A的对应于特征值αid的特征向量.

②下证矩阵AT有特征值等于d，且至少2重.

∴矩阵AT存在至少2重特征值等于d.

定理2 d是矩阵A的次特征值.

证明 由文献［12］知，矩阵A的特征值1有且仅有1重，即｜λ1｜＜1.

记矩阵A对应于特征值λ2的右特征向量为，其中1≠λ2.

∵矩阵AT对应于特征值1的右特征向量为，即

将（4）两边同时转置得

4 确定阻尼因子d值

由文献［13］算得，Google矩阵的条件数为cond（A）＝K＝，K是关于d的严增函数.条件数K越小PageRank的近似解越精确，即d的取值需尽量小；收敛速度越小收敛越快.可d不能太小，太小会影响排序的公正性.

要同时保证PageRank的近似解的精确性和排序的公正性，就要求K＝最小值和d的最大值，其中0＜d＜1.即两个目标函数

将（12）和（13）两个目标函数加权处理成一个目标函数，即为

用Lingo求目标函数（14），结果是α＝0，β＝1，d＝1时，最小值为－1，明显不符合条件.再用穷举法得到当α＝0.04，β＝0.96，d＝0.71时，达到最小值－0.44，最符合要求.即阻尼因子d取值为0.71.

显然，d的取值从0.85降到0.71，降幅不是很大，但是解PageRank近似解的条件数K值从12.333 3降到5.896 6，条件数明显减小，即近似解误差大大减小.

5 小结

改进的PageRank算法不仅能弥补平均分配PageRank值这一缺陷，还能用小于0.85的d值达到传统PageRank算法的结果［14］.d值的减小降低了解PageRank近似解的误差，同时提高了幂法的收敛速度.

［1］付怀慧，林共进.阻尼因子对网页排名之敏感度分析［J］.中国统计学，2005（2）：145－164.

［2］黄德才，戚华春.PageRank算法研究［J］.计算机工程，2006（4）：145－162.

［3］姜鑫维，赵岳松.Topic－PageRank——一种基于主题的搜索引擎［J］.计算机技术与发展，2007（5）：238－241.

［4］Fu H H，Dennis K J L，Tsai H T.Damping factor in Google page ranking［J］.Applied Stochastic Models Business And Industry，2006（22）：431－444.

［5］李 凯，赫枫龄，左万利.PageRank－Pro——一种改进的网页排序算法［J］.吉林大学学报：理学版，2003，41（2）：175－179.

［6］张 丽.万维网搜索算法的研究——从PageRank算法到WeightedIndegree算法［D］.北京：北京交通大学，2006.

［7］张 魏.基于PageRank算法的搜索引擎优化策略研究［D］.成都：四川大学，2005.

［8］Xue G R，Yang Q，Zeng H J，et al.Exploiting the hierarchical structure for link analysis［R］.In Proc of the 28thannual international ACM SIGIR conference on Research and development in information retrieval，Salvador，Brazil，2005.

［9］The Google PageRank Algorithm and How It Work［EB／OL］.http：／／www.iprcom.com／papers／pagerank／，2002.

［10］田 甜，倪 林.基于PageRank算法的权威值不均衡分配问题［J］.计算机工程，2007（33）：53－55.

［11］Isaacson D L，Madsen R W.Markov Chains：Theory and Applications［M］.New York：John Wiley and Sons Inc，1976.

［12］Haveliwala T H，Kamvar S D.The second eigenvalue of the Google matrix［D］.Stanford：Stanford University Technical Report，2003.

［13］Sepandar D K，Taher H H.The condition number of the PageRank problem ［R］.Stanford：Stanford University Technical Report，2003.

［14］邵晶晶.基于PageRank排序算法改进的若干研究［D］.武汉：华中师范大学，2009.

The value of damping factor of the PageRank algorithm

SHAO Jingjing
（Department of Computer Science and Technology and Electronic Information Engineering，Dianchi College of Yunnan University，Kunming 650228）

Based on the average distribution of the traditional PageRank algorithm PageRank value to each Web page hyperlink，this paper presents an improved PageRank algorithm，and proves that if the Web hyperlink matrix Pused by Google for computing PageRank contains at least two irreducible closed subsets，the second eigenvalue for matrix is d，and the multiplicity of the eigenvalue dis 2.In order to reduce the error of the approximate PageRank solutions and improve the convergence speed，d with the lingo calculated is to take 0.71.And if using the improved PageRank algorithm，the results of traditional PageRank algorithm can be achieved with the value of dless than 0.85.

PageRank algorithm；second eigenvalue；damping factor value

O211.6

A

1000－1190（2011）04－0534－04

2011－03－22.

云南省教育厅科学研究基金项目（09y0423）.

＊E－mail：jingjing3170＠163.com.