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.