【正文】 領(lǐng)域網(wǎng)頁即分類網(wǎng)頁的PR 計(jì)算，因此 在不同領(lǐng)域它們的基數(shù)不一樣， 為了使計(jì)算結(jié)果更加準(zhǔn)確，所以必須要對(duì)PRin 進(jìn)行歸一化以方便跨領(lǐng)域的 PR 值疊加運(yùn)算。 為了避免出現(xiàn)不同領(lǐng)域總的 PR 值不同給下面計(jì)算 非分類 網(wǎng)頁總的 PR 值 帶來 偏差 的情況 ，下面對(duì)計(jì)算所有訪問者對(duì)各個(gè)領(lǐng)域的總的 PR 值的和 。 PRi=n PRin? 設(shè)置歸一化常數(shù) Ci= 1nPRin? 因此最后得出某個(gè)訪問者 n 在 i 領(lǐng)域的 PR 值 PRin(i+1)=Ci j?(Kijn n?Zijn PRin(i) Kijn) () 上式就是結(jié)合訪問者的自身情況得出的 改進(jìn) 算法 算法描述如下 ： PRin(0) = 1N //初始化每個(gè)訪問者的 PageRank while (|PRin(i) PRin(i1)|ε ) //PageRank 收斂前的循環(huán)計(jì)算判斷 {ε = i=1 for each n∈ N 社會(huì)環(huán)境下網(wǎng)頁重要性的研究 21 PRin(i)= j?(Kijn n?Zijn PRin(i1) Kijn) PRi=n PRin? Ci= 1nPRin? //設(shè)置歸一化常數(shù) ,規(guī)范因子的計(jì)算，以保證計(jì)算結(jié)果的正確性 PRin(i)= Ci PRin(i) //進(jìn)行規(guī)范化得出的結(jié)果 i=i+1 } 隨著循環(huán)次數(shù)的增加，計(jì)算結(jié)果越來越收斂，越來越接近真實(shí)的 PR 值，只要循環(huán)次數(shù)足夠多可以得到任何精度的網(wǎng)頁 PR 值。 訪問者 PR 值 算法 的 簡單模型 據(jù)統(tǒng)計(jì)， Web 已經(jīng)擁有 100 億左右的靜態(tài)網(wǎng)頁和 550 億左右的動(dòng)態(tài)網(wǎng)頁 ，網(wǎng)民數(shù)量僅中國就有 億，因此， PageRank 要處理的矩陣是“世界上最大的矩陣”，為了便于討論驗(yàn)證算法的正確性同時(shí)也是為了讓讀者更加容易理解算法的結(jié)構(gòu)邏輯，下面 建立簡單的模型，驗(yàn) 證程序是否可行 。 社會(huì)環(huán)境下網(wǎng)頁重要性的研究 22 圖 PRin(i)= j?(Kijn n?Zijn PRin(i1) Kijn) () 以上圖示為了方便驗(yàn)證下面 的結(jié)果是否正確， 如圖 ， 圓圈表示訪問者 ， 方框表示網(wǎng)頁 ，直線表示訪問相應(yīng)的網(wǎng)頁 。 3 表示訪問次數(shù) 3 次最終的 Kijn 為 ，其他的依次類推。 圖 設(shè)置的數(shù)值都很明顯 ,訪問者 1 的被認(rèn)同度明顯是高于其他三人，訪問者 4 的被認(rèn)同度明顯低于其他三人，而訪問者 2 的被認(rèn)同度又高于訪問者 3， 讀者可以明顯看出 4個(gè)訪問者的 PR 是 PRi(1) PRi(2) PRi(3) PRi(4)。 如果下面的計(jì)算結(jié)果同上，則說明我所改進(jìn) 的算法，不存在邏輯的錯(cuò)誤，計(jì)算結(jié)果沒有錯(cuò)誤。 Visual Basic 作為非計(jì)算機(jī)專業(yè)科學(xué)工作 者的常用編程軟件深得使用者的好評(píng)，用來實(shí)現(xiàn)數(shù)學(xué)運(yùn)算簡單方便，可以將公式的 ()的運(yùn)算關(guān)系表達(dá)的很清楚，但是存在的缺點(diǎn)是對(duì)于多重循環(huán)運(yùn)算，對(duì)編程者的編程水平要求較高。 Matlab 是矩陣實(shí)驗(yàn)室（ Matrix Laboratory）的簡稱 ， 作為數(shù)學(xué)矩陣的專用軟件，由美國新墨西哥大學(xué)教授設(shè)計(jì)，自誕生以來 ，版本從 到 ， 一直受到數(shù)學(xué)工作者的喜愛，對(duì)于數(shù)學(xué)矩陣運(yùn)算編程方法簡單，是數(shù)學(xué)運(yùn)算的常用工具。本文 改進(jìn) 算法可以表示為矩陣的運(yùn)算，采用 matlab 計(jì)算比較合適， 而且 Google 社會(huì)環(huán)境下網(wǎng)頁重要性的研究 23 搜索 引擎就是用矩陣運(yùn)算得出網(wǎng)頁 PR 值的， 但是缺點(diǎn)是不能夠清楚表達(dá)原來的運(yùn)算關(guān)系。比較 兩者的優(yōu)缺點(diǎn)，采用兩種方法同時(shí)編程運(yùn)算，發(fā)揮兩者的優(yōu)點(diǎn)，使讀者比較容易理解本文 改進(jìn) 算法的設(shè)計(jì)思路。同時(shí)也是檢驗(yàn)運(yùn)算結(jié)果是否正確的雙保險(xiǎn)。 [11] Visual Basic 編程驗(yàn)證算法收斂 將上面的算法結(jié)合上圖編寫相應(yīng)的 VB 程序，運(yùn)行循環(huán)結(jié)構(gòu)后得出收斂后的結(jié)果 驗(yàn)證算法的正確性： private Sub Command1_Click() Dim m, n, l, i, j, k, o Dim PRi(1 To 4) Dim Zi(1 To 4, 1 To 4) Dim Ki(0 To 4, 1 To 4) Dim C(0 To 4) Dim T(0 To 4) Dim PR(1 To 4, 1 To 9999) Dim P(1 To 4) Dim G(1 To 4) Zi(1, 1) = 3: Zi(1, 2) = 0: Zi(1, 3) = 1: Zi(1, 4) = 2: Zi(2, 1) = 1: Zi(2, 2) = 4: Zi(2, 3) = 0: Zi(2, 4) = 3 Zi(3, 1) = 0: Zi(3, 2) = 2: Zi(3, 3) = 2: Zi(3, 4) = 0: Zi(4, 1) = 2: Zi(4, 2) = 0: Zi(4, 3) = 0: Zi(4, 4) = 1 PRi(1) = 1 / 4: PRi(2) = 1 / 4: PRi(3) = 1 / 4: PRi(4) = 1 / 4 Ki(1, 1) = : Ki(1, 2) = : Ki(1, 3) = : Ki(1, 4) = : Ki(2, 1) = : Ki(2, 2) = : Ki(2, 3) = : Ki(2, 4) = Ki(3, 1) = : Ki(3, 2) = : Ki(3, 3) = : Ki(3, 4) = : Ki(4, 1) = : Ki(4, 2) = : Ki(4, 3) = : Ki(4, 4) = For m = 1 To 200 P(1) = 0: P(2) = 0: P(3) = 0: P(4) = 0 For j = 1 To 4 o = 0 For n = 1 To 4 C(j) = Zi(j, n) * PRi(n) * Ki(j, n) T(j) = o + C(j) o = T(j) Next n 社會(huì)環(huán)境下網(wǎng)頁重要性的研究 24 For n = 1 To 4 Ki(0, n) = 0 G(n) = Ki(j, n) * T(j) Next n For l = 1 To 4 P(l) = P(l) + G(l) Next l Next j For k = 1 To 4 PR(k, m) = P(k) Next k Print PRi(1)=。 PR(1, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m))。 PRi(2)=。 PR(2, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m))。 PRi(3)=。 PR(3, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m))。 PRi(4)=。 PR(4, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)) Print 第 。 m。 次循環(huán) For n = 1 To 4 PRi(n) = PR(n, m) Next n If m = 100 Then = PR(1, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)) = PR(2, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)) = PR(3, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)) = PR(4, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)) End If Next m End Sub 筆者 在自己電腦上 (電腦配置： 主頻 ，內(nèi)存 512MB)用 Visual Baisc 編制程序?qū)崿F(xiàn)上述算法 ,并進(jìn)行了實(shí)際的計(jì)算。為了方便論述 ,我們將網(wǎng)絡(luò)結(jié)構(gòu)簡單化 ,假設(shè)僅僅有 4 個(gè)網(wǎng)頁 和 4 個(gè)訪問者 ,如 圖 所示通過超鏈接相互聯(lián)系。對(duì) 圖 所示的網(wǎng)頁進(jìn)行 PageRank的計(jì)算 ， 結(jié)果如 圖 所示 (未全部列出 , 圖 中 PRi(n)表示 訪問者 n 在 i 領(lǐng)域 的 PageRank值 ,精確到小數(shù)點(diǎn)后 15 位 ) 社會(huì)環(huán)境下網(wǎng)頁重要性的研究 25 圖 VB 源代碼窗口圖 社會(huì)環(huán)境下網(wǎng)頁重要性的研究 26 圖 VB 運(yùn)行結(jié)果圖 社會(huì)環(huán)境下網(wǎng)頁重要性的研究 27 社會(huì)環(huán)境下網(wǎng)頁重要性的研究 28 圖 PageRank 的計(jì)算結(jié)果 由上式可以看出，每一個(gè) 第 i+1 次的 PageRank 值都是基于上次的 PageRank 值重新計(jì)算的。具體的迭代次數(shù)在實(shí)際中是無 限的。 循環(huán)次數(shù)越多，計(jì)算結(jié)果越收斂于 (越接近 )網(wǎng)社會(huì)環(huán)境下網(wǎng)頁重要性的研究 29 頁的真實(shí) PR 值。 數(shù)據(jù)的精度設(shè)置越高則循環(huán)次數(shù)就越多 [12]，但是實(shí)際上將網(wǎng)頁的 PR 值按大 小排序無需太高的精度，可以區(qū)分出 網(wǎng)頁 PR 值 大小就行，這樣對(duì) PRin的精度要求也無需太高，精確到小數(shù) 點(diǎn) 后十五位 就 足夠。 上面的循環(huán)運(yùn)算的 計(jì)算結(jié)果越來越趨向一個(gè)值 ，根據(jù)計(jì)算結(jié)果 ， 第十六 次的循環(huán)計(jì)算已經(jīng)收斂到小數(shù)點(diǎn)后 14 位，我開始定義的數(shù)組數(shù)據(jù)類型為 雙精度 (Double)占 8 個(gè)字節(jié)， 16 位的最高位數(shù)已經(jīng)被突破，再下去的循環(huán)計(jì)算已經(jīng)沒有意義， 在另一方面也反映了我的算法具有無限的精度，循環(huán)次數(shù)越多則精確位數(shù)越多，所以我的算法在精度方面是完全符合要求無可挑剔的。 但是 循環(huán) 次數(shù)少 就 達(dá)到收斂效果不是說明我的循環(huán)次數(shù)設(shè)置那么高是 多此一舉 ，因?yàn)樯厦媸菍儆谧詈唵蔚哪Ｐ?，達(dá)到收斂所需的次數(shù)當(dāng)然是最少的，同樣的算法對(duì)于互聯(lián)網(wǎng)數(shù)以億計(jì)的網(wǎng)頁和訪問者 ，運(yùn)算量是巨大的，循環(huán)次數(shù)更 是非常巨大，上面只是簡單的模型，目的是使讀者更加理解我設(shè)計(jì)的算法，同時(shí)也驗(yàn)證了我的算法的正確性。 matlab 編程驗(yàn)證算法收斂 上述過程本質(zhì)上可以表達(dá)為特征向量的計(jì)算，首先每個(gè)訪問者在 i 領(lǐng)域的 PR 值可以表示一個(gè)矩陣 ，即一個(gè) N 行 N 列的矩陣 (N 為 整個(gè)網(wǎng)絡(luò) 訪問者的總數(shù) ， j 為 i 領(lǐng)域所有的網(wǎng)頁數(shù) )為了方便計(jì)算，開始時(shí)可以給每個(gè)元素的值都設(shè)為 1N 。 PRin=? ?1?? n n= 1 1 1 1 1, , , , .. .. ,1 1 1 1 1, , , , .. .. ,1 1 1 1 1, , , , .. ..................................1 1 1 1 1, , , .. .. ,N N N N NN N N N NN N N N NN N N N N???????????????? 設(shè) Zijn 為一個(gè)隨機(jī)矩陣它的橫向表示同一個(gè)網(wǎng)頁被不同訪問者訪問的次數(shù)， 縱向表示同一訪問者對(duì)同一領(lǐng)域不同網(wǎng)頁的訪問次數(shù) Zijn= 11 , 12 , 13....., 121 , 22 , 23....., 231 , 32 , 33....., 3......., ........., ......., ......, ......1 , 2 , 3.....,Z i Z i Z i Z i nZ i Z i Z i Z i nZ i Z i Z i Z i nZ ij Z ij Z ij Z ij n???????? 同理設(shè) Kijn 為一個(gè)隨機(jī)矩陣它的橫向表示同一個(gè)訪問者不同網(wǎng)頁的 Kijn 。縱向表示不同社會(huì)環(huán)境下網(wǎng)頁重要性的研究 30 訪問者對(duì)同一個(gè)網(wǎng)頁的 Kijn Kijn=11 , 12 , 13 , ...... 121 , 22 , 23 , ...... 231 , 32 , 33 , ...... 3........, ........, ........., ....., .....,1 , 2 , 3 , ......K i K i K i K i nK i K i K i K i nK i K i K i K i nK ij K ij K ij K ij n???????? PRin= j?(Kijn n?Zijn PRin Kijn) () 因此n?Zijn PRin Kijn 可以用矩陣運(yùn)算 表示為 ((Kijn.*(PRin.*Zijn))*L) (在 matlab 數(shù)學(xué)矩陣運(yùn)算中 ， 對(duì)于行列數(shù)相同的矩 陣 A 和