PageRank算法的阻尼因子值

邵晶晶

（云南大學(xué) 滇池學(xué)院 計(jì)算機(jī)科學(xué)技術(shù)與電子信息工程系，昆明 650228）

PageRank算法的阻尼因子值

邵晶晶＊

（云南大學(xué) 滇池學(xué)院 計(jì)算機(jī)科學(xué)技術(shù)與電子信息工程系，昆明 650228）

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

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

1 傳統(tǒng)PageRank算法

1.1 算法解析

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

其中，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采用冪法計(jì)算網(wǎng)頁的PageRank值的近似解，即先給每個(gè)網(wǎng)頁一個(gè)初始值，然后循環(huán)進(jìn)行無限次迭代得到結(jié)果.

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

基于網(wǎng)絡(luò)結(jié)構(gòu)鏈接圖，定義它的鄰接矩陣G＝（gij）n×n，若 Web中有網(wǎng)頁i指向網(wǎng)頁j的超鏈接，那么gij＝1，否則gij＝0.目前包括PageRank算法，文獻(xiàn)［2－7］在內(nèi)的大多數(shù)鏈接分析，文獻(xiàn)［8］的算法都是基于上面的鄰接矩陣.將鄰接矩陣G行和歸一，得到矩陣M ＝（mij）n×n.矩陣M 必須滿足兩個(gè)條件才能保證迭代過程收斂：一是M必須是不可約的（G強(qiáng)相通）；二是M 必須是非周期的［9］，同時(shí)保證M是隨機(jī)的馬爾可夫概率轉(zhuǎn)移矩陣.則首先將M的全0行處理成全1行，然后行和歸一得到矩陣P，最后在迭代過程中加一個(gè)阻尼因子d即可.即若記

這樣得到的矩陣A為列隨機(jī)陣且非周期不可約，能保證迭代過程收斂.

冪法是計(jì)算實(shí)方陣的按模最大的特征值及相應(yīng)特征向量的一種迭代法.實(shí)方陣A有n個(gè)不同的特征值，最大特征值為1，故A有n個(gè)線性無關(guān)的特征向量對(duì)應(yīng)特征值有1＝｜λ1｜＞｜λ2｜≥… ≥｜λn｜.任給初始向量x→0≠0→，x→0可由向量組線性表示，由迭代公式＝（k＝0，1，2，…），得到一向量序列（α1，α2，…，αn不全為0的實(shí)數(shù)，且α1≠0），不妨取α1＝1，即

2 改進(jìn)的PageRank算法

改進(jìn)的PageRank計(jì)算公式：

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

改進(jìn)思想是若網(wǎng)頁Ti超鏈接有s1，s2，…，sm共m個(gè)頁面（包含A），它們各自的鏈入網(wǎng)頁數(shù)與所有m個(gè)網(wǎng)頁的鏈入網(wǎng)頁數(shù)之和的比值就是網(wǎng)頁A獲得網(wǎng)頁Ti權(quán)威值的權(quán)重，網(wǎng)頁Ti就根據(jù)這個(gè)權(quán)重分配它的權(quán)威值，這里網(wǎng)頁Ti的所有超鏈接所占權(quán)重之和為1，即保證了鄰接矩陣的行和為1.

3 矩陣次特征值

矩陣A是列隨機(jī)矩陣，若將矩陣A的特征值按從大到小的順序排列，記其第i個(gè)特征值為λi，則1＝｜λ1｜＞｜λ2｜≥ … ≥｜λn｜≥0.

定理1 若矩陣P包含至少兩個(gè)不可約閉子集，則矩陣AT存在特征值為d，至少2重.

由文獻(xiàn)［11］知，矩陣P有特征值為1，至少2重，取矩陣P的對(duì)應(yīng)于特征值1的兩個(gè)線性無關(guān)的特征向量

① 先證矩陣P的任意一個(gè)對(duì)應(yīng)于特征值αi的特征向量，若其與向量正交，則是矩陣A的對(duì)應(yīng)于特征值αid的特征向量.

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

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

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

證明 由文獻(xiàn)［12］知，矩陣A的特征值1有且僅有1重，即｜λ1｜＜1.

記矩陣A對(duì)應(yīng)于特征值λ2的右特征向量為，其中1≠λ2.

∵矩陣AT對(duì)應(yīng)于特征值1的右特征向量為，即

將（4）兩邊同時(shí)轉(zhuǎn)置得

4 確定阻尼因子d值

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

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

將（12）和（13）兩個(gè)目標(biāo)函數(shù)加權(quán)處理成一個(gè)目標(biāo)函數(shù)，即為

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

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

5 小結(jié)

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

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

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

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

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

［7］張 魏.基于PageRank算法的搜索引擎優(yōu)化策略研究［D］.成都：四川大學(xué)，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算法的權(quán)威值不均衡分配問題［J］.計(jì)算機(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排序算法改進(jìn)的若干研究［D］.武漢：華中師范大學(xué)，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.

云南省教育廳科學(xué)研究基金項(xiàng)目（09y0423）.

＊E－mail：jingjing3170＠163.com.