邵晶晶

（云南大學 滇池學院 計算機科學技術與電子信息工程系，昆明 650228）

PageRank算法的阻尼因子值

邵晶晶＊

（云南大學 滇池學院 計算機科學技術與電子信息工程系，昆明 650228）

針對傳統(tǒng)PageRank算法平均分配PageRank值給每個超鏈接網(wǎng)頁這一缺陷，提出了改進的PageRank算法，并證明如果Web網(wǎng)的鄰接矩陣P包含至少2個不可約閉子集，則非周期不可約矩陣的次特征值為d且至少2重.為了降低解PageRank近似解的誤差和提高冪法的收斂速度，用lingo算得d取0.71，且知若采用改進的PageRank算法用小于0.85的d值可以達到傳統(tǒng)PageRank算法的計算結(jié)果.

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

1 傳統(tǒng)PageRank算法

1.1 算法解析

Google的體系結(jié)構(gòu)類似于傳統(tǒng)的搜索引擎，它與傳統(tǒng)的搜索引擎最大的不同之處在于對網(wǎng)頁進行了基于權威值（PageRank值）的排序處理，使最重要的網(wǎng)頁出現(xiàn)在結(jié)果的最前面.Google通過PageRank排名算法計算出網(wǎng)頁的PageRank值，從而決定網(wǎng)頁在結(jié)果之中的出現(xiàn)位置，PageRank值越高的網(wǎng)頁，在結(jié)果中出現(xiàn)的位置越前［1］.計算公式如下：

其中，n為網(wǎng)頁總數(shù)，d為阻尼因子取值0.85，網(wǎng)頁Ti為鏈接到網(wǎng)頁A的頁面，C（Ti）為網(wǎng)頁Ti的出度，i＝1，2，…，t.

1.2 解PageRank值

Google采用冪法計算網(wǎng)頁的PageRank值的近似解，即先給每個網(wǎng)頁一個初始值，然后循環(huán)進行無限次迭代得到結(jié)果.

PageRank算法是先建立Web網(wǎng)的鄰接矩陣，然后把該矩陣處理成非周期不可約馬氏鏈的轉(zhuǎn)移概率矩陣，PageRank被定義為該馬氏鏈的平穩(wěn)分布，或該馬氏鏈的不變測度.詳細計算如下：

基于網(wǎng)絡結(jié)構(gòu)鏈接圖，定義它的鄰接矩陣G＝（gij）n×n，若 Web中有網(wǎng)頁i指向網(wǎng)頁j的超鏈接，那么gij＝1，否則gij＝0.目前包括PageRank算法，文獻［2－7］在內(nèi)的大多數(shù)鏈接分析，文獻［8］的算法都是基于上面的鄰接矩陣.將鄰接矩陣G行和歸一，得到矩陣M ＝（mij）n×n.矩陣M 必須滿足兩個條件才能保證迭代過程收斂：一是M必須是不可約的（G強相通）；二是M 必須是非周期的［9］，同時保證M是隨機的馬爾可夫概率轉(zhuǎn)移矩陣.則首先將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的實數(shù)，且α1≠0），不妨取α1＝1，即

2 改進的PageRank算法

改進的PageRank計算公式：

其中，INA是網(wǎng)頁A的鏈入網(wǎng)頁數(shù)，INj是Ti超鏈接s1，s2，…，sm網(wǎng)頁中第j個頁面的鏈入網(wǎng)頁數(shù)，i＝1，2，…，t，j＝1，2，…，m.

改進思想是若網(wǎng)頁Ti超鏈接有s1，s2，…，sm共m個頁面（包含A），它們各自的鏈入網(wǎng)頁數(shù)與所有m個網(wǎng)頁的鏈入網(wǎng)頁數(shù)之和的比值就是網(wǎng)頁A獲得網(wǎng)頁Ti權威值的權重，網(wǎng)頁Ti就根據(jù)這個權重分配它的權威值，這里網(wǎng)頁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）兩邊同時轉(zhuǎn)置得

4 確定阻尼因子d值

由文獻［13］算得，Google矩陣的條件數(shù)為cond（A）＝K＝，K是關于d的嚴增函數(shù).條件數(shù)K越小PageRank的近似解越精確，即d的取值需盡量小；收斂速度越小收斂越快.可d不能太小，太小會影響排序的公正性.

要同時保證PageRank的近似解的精確性和排序的公正性，就要求K＝最小值和d的最大值，其中0＜d＜1.即兩個目標函數(shù)

將（12）和（13）兩個目標函數(shù)加權處理成一個目標函數(shù)，即為

用Lingo求目標函數(shù)（14），結(jié)果是α＝0，β＝1，d＝1時，最小值為－1，明顯不符合條件.再用窮舉法得到當α＝0.04，β＝0.96，d＝0.71時，達到最小值－0.44，最符合要求.即阻尼因子d取值為0.71.

顯然，d的取值從0.85降到0.71，降幅不是很大，但是解PageRank近似解的條件數(shù)K值從12.333 3降到5.896 6，條件數(shù)明顯減小，即近似解誤差大大減小.

5 小結(jié)

改進的PageRank算法不僅能彌補平均分配PageRank值這一缺陷，還能用小于0.85的d值達到傳統(tǒng)PageRank算法的結(jié)果［14］.d值的減小降低了解PageRank近似解的誤差，同時提高了冪法的收斂速度.

［1］付懷慧，林共進.阻尼因子對網(wǎng)頁排名之敏感度分析［J］.中國統(tǒng)計學，2005（2）：145－164.

［2］黃德才，戚華春.PageRank算法研究［J］.計算機工程，2006（4）：145－162.

［3］姜鑫維，趙岳松.Topic－PageRank——一種基于主題的搜索引擎［J］.計算機技術與發(fā)展，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——一種改進的網(wǎng)頁排序算法［J］.吉林大學學報：理學版，2003，41（2）：175－179.

［6］張 麗.萬維網(wǎng)搜索算法的研究——從PageRank算法到WeightedIndegree算法［D］.北京：北京交通大學，2006.

［7］張 魏.基于PageRank算法的搜索引擎優(yōu)化策略研究［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.