資源描述：
《PAGERANK算法解析》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、PageRank算法解析李永華2004.9.9OutlinePageRank的基本概念PageRank的計算PageRank計算算法的改進Google索引必須對每個網(wǎng)頁的關鍵詞建立索引倒排Term1－>Pi,Pj,…Term2－>Pk,Pl,…排序為每個網(wǎng)頁賦予一個“PageRank”值查詢匹配Q=Term1,Term2,…產(chǎn)生R=Pi,Pj,Pk,Pl…根據(jù)Pi,Pj,Pk,Pl…的“PageRank”值大小進行排序返回給用戶PageRank的基本概念PageRank是基于「從許多優(yōu)質的網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質網(wǎng)頁」的回歸關系，來判定所有網(wǎng)頁的
2、重要性特點完全獨立于查詢，只依賴于網(wǎng)頁鏈接結構可以離線計算每一張網(wǎng)頁P有一個特定的Rank值r(P)r(P)的大小取決于三個因素：鏈入網(wǎng)頁數(shù)鏈入網(wǎng)頁的質量鏈入網(wǎng)頁的鏈出網(wǎng)頁數(shù)PageRank算法(1)定義將一個網(wǎng)頁的所有鏈入網(wǎng)頁的PageRank值除以該鏈入網(wǎng)頁的鏈出網(wǎng)頁數(shù)得到的結果進行累加，即得到該網(wǎng)頁的PageRank值PageRank算法(2)PageRank的計算(1)網(wǎng)頁鏈接關系建模－－矩陣網(wǎng)頁i鏈接到網(wǎng)頁j,則Aij=1,否則Aij=0;若網(wǎng)頁個數(shù)為N，則此矩陣為N階矩陣PageRank的矩陣是將此N階矩陣A進行倒置，并把各個列矢量除以各自的
3、鏈接數(shù)。轉換后的矩陣被稱為[推移概率行列]。PageRank的計算，就是求屬于這個推移概率行列最大特性值的固有矢量。X=AXPageRank的計算(2)采用遞歸的方法來求此特征值遞歸結束標志：
4、Ranki+1-Ranki
5、<閥值PageRank的計算(3)存在一些網(wǎng)頁不鏈接任何網(wǎng)頁，即此網(wǎng)頁的出度（outdegree)為0，這種網(wǎng)頁存為搖擺網(wǎng)頁(danglingweb)。搖擺網(wǎng)頁的存在將使得遞歸過程中Rank值會比實際值小。引入了一個新的矩陣PageRank的計算(3)PageRank的計算(4)需要兩個數(shù)組Source和Dest分別保存上一次遞歸的結果
6、和本次遞歸的結果。經(jīng)驗表明，PageRank的值可用單精度浮點來表示；初值可以任意設置；c＝0.85PageRank計算算法的改進(1)假定網(wǎng)頁的數(shù)量為N，則數(shù)組Source需要4Nbyte內存大小。當N=2.5億(天網(wǎng)目前的網(wǎng)頁數(shù)量），則需內存1G。如果N上升到10億時，數(shù)組Source需要4G的內存，無法完全放在內存中。通過上面的算法可以看出，數(shù)組Source是順序訪問的，而數(shù)組Dest是隨機訪問的，如果不能夠完全放在內存中，則需要通過文件進行內存映射，勢必產(chǎn)生大量的I/O操作。PageRank計算算法的改進(2)分塊的思想將網(wǎng)頁鏈接矩陣進行分塊，是
7、的每塊Dest數(shù)組能夠容納在內存中。按塊來分別計算PageRank值。分塊示例PageRank計算算法的改進(3)PageRank計算算法的改進(4)PageRank計算算法的改進(5)多機并行計算PageRank由上面分塊的思想，由于在一次迭代過程中，每塊的計算是獨立的，可以將這些計算分布到多臺機器上并行計算。PageRank計算算法的改進(6)1>將鏈接分塊，并將塊分發(fā)到多臺機器上2>while(residual>T){所有機器同時計算，結果存入磁盤，并發(fā)送到中心服務器。中心服務器收到所有機器發(fā)來的PageRank結果文件，將結果進行合并，并分發(fā)到所
8、有機器上。Residual=
9、
10、Source–Dest
11、
12、Source=Dest}難點在于多臺機器的并發(fā)控制參考文獻[1]T.H.Haveliwala.Efficientcomputationofpagerank.Technicalreport,StanfordUniversity,October1999[2]S.BrinandL.Page.Theanatomyofalarge-scalehypertextualwebsearchengine.InProc.oftheSeventhWorldWideWebConference,1998.
