【文章內(nèi)容簡介】 要度降低 ， 則它對它的鏈出 網(wǎng)頁重要度的影響也相應(yīng)降低 。 綜上而言 ， 一個網(wǎng)頁的重要性決定著同時也依賴于其他網(wǎng)頁的重要性。 PageRank 絕對是個很科學(xué)的小創(chuàng)意。 說他科學(xué)，你會在我以后的文章中看到 Google是如何將數(shù)學(xué) (具體來說多數(shù)是統(tǒng)計學(xué) )理論淋漓盡致地發(fā)揮在搜索技術(shù)之中。 說他 “小 ”，因?yàn)檫@些理論對于搞數(shù)學(xué)的人來說實(shí)在太微不足道了，甚至稍微有些科學(xué)高數(shù)知識的人都能理解。 他所用到的統(tǒng)計學(xué)就是循環(huán)迭代計算收斂值的方法 ！ [6] 傳統(tǒng) PageRank 算法代數(shù)表達(dá)形式 按照 上面 思路 ， Page 給出了 PageRank 的簡單定義 [7]： ? ? ? ?? ? ? ?v B uR u C R v N v???? () 此處的 u 表示一個網(wǎng)頁 ， R ( u) 表示網(wǎng)頁 u 的 PageRank 值 ， B ( u)表示鏈接到網(wǎng)頁 u的網(wǎng)頁集合 ， 即網(wǎng)頁 u 的鏈入網(wǎng)頁集合 ， N ( v ) 表示從網(wǎng)頁 v 向外的鏈接數(shù)量 ， 即網(wǎng)頁v 的鏈出網(wǎng)頁數(shù) ， C 為規(guī)范化因子 ， 用于保證所有網(wǎng)頁的 PageRank 總和為常量 (如為 1)。 這就是算法的形式化描述，也可以用矩陣來描述此算法，設(shè) A 為一個方陣，行和列對應(yīng)網(wǎng)頁集的網(wǎng)頁。如果網(wǎng)頁 i 有指向網(wǎng)頁 j 的一個鏈接，則 Aij=1/Ni，否則 Aij=0。設(shè) V是對應(yīng)網(wǎng)頁集的一個向量，有 V=cAV， V為 A 的特征根為 c 的特征向量。實(shí)際上只需要求出最大特征根的特征向量，就是網(wǎng)頁集對應(yīng)的最 終 PageRank 值，這可以用迭代方法計算。 具體計算時 ， 可以給每個網(wǎng)頁一個初始的 PageRank 值 ， 然后反復(fù)迭代運(yùn)算 ， 即 ： R(i+1)(v)=??uBv??R(i)(u)/Nu () 此處的 v 代表所有的網(wǎng)頁集合 ,每一個第 i+1次的 PageRank 值都是基于上次的PageRank值重新計算的。具體的迭代次數(shù)在實(shí)際運(yùn)算中是有限的。 Lawrence Page 和 Sergey Brin 在 個別場合描述了 PageRank 最初的算法。這就是 PR(A) = (1d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 式中： PR(A) :網(wǎng)頁 A 頁的 PageRank 值； PR(Ti) :鏈接到 A 頁的網(wǎng)頁 Ti 的 PageRank 值； 社會環(huán)境下網(wǎng)頁重要性的研究 11 C(Ti) :網(wǎng)頁 Ti 的出站鏈接數(shù)量； d :阻尼系數(shù)， 0d1。 上式最初算法只是表達(dá)了 PageRank 的基本計算原理，并不具有普遍性，因?yàn)闆]有迭代收斂的步驟 。 所有 PR(Ti)之和 還要 乘以一個阻尼系數(shù) d，它的值在 0到 1之間。 阻尼系數(shù)的使用，減少了其它頁面對當(dāng)前頁面 A的排序貢獻(xiàn)。 一個頁面通過隨機(jī)沖浪到達(dá)的概率就是鏈入它的別的頁面上的鏈接的被點(diǎn)擊概率的和。并且，阻尼系數(shù) d減低了這個概率。阻尼系數(shù) d的引入，是因?yàn)橛脩舨豢赡軣o限的點(diǎn)擊鏈接，常常因無聊而隨機(jī)跳入另一個頁面。 PageRank的特性可以通過以下范例用插圖表示。 圖 假設(shè)一個小網(wǎng)站由三個頁面 A、 B、 C 組成， A 連接到 B 和 C， B 連接到 C， C 連接 到A。雖然 Page 和 Brin 實(shí)際上將阻尼系數(shù) d 設(shè)為 ，但這里我們?yōu)榱撕啽阌嬎憔蛯⑵湓O(shè)為。盡管阻尼系數(shù) d 的精確值無疑是影響到 PageRank 值的，可是它并不影響 PageRank計算的原理。因此，我們得到以下計算 PageRank 值的方程： PR(A) = + PR(C) PR(B) = + (PR(A) / 2) PR(C)=+(PR(A)/2+PR(B)) 這些方程很容易求解，以下得到每個頁面的 PageRank 值： PR(A)= 14/13 = PR(B)=10/13 = PR(B)=15/13 = 很明顯所有頁面 PageRank 之和為 3，等于網(wǎng)頁的總數(shù)。就像以上所提的，此結(jié)果對于這個簡單的范例來說并不特殊。 對于這個只有三個頁面的簡單范例來說，通過方程組很容易求得 PageRank 值。但實(shí)際上，互聯(lián)網(wǎng)包含數(shù)以億計的文檔，是不可能解方程組的 。下面闡述迭代過程。 由于實(shí)際的互聯(lián)網(wǎng)網(wǎng)頁數(shù)量， Google 搜索引擎使用了一個近似的、迭代的計算方法計算 PageRank 值。就是說先給每個網(wǎng)頁一個初始值，然 后利用上面的公式，循環(huán)進(jìn)行有限次運(yùn)算得到近似的 PageRank 值。 我們再次使用 “三頁面 ”的范例來說明迭代計算，這里設(shè)每個頁面的初始值為 1。 迭代次數(shù) PR(A) PR(B) PR(C) 0 1 1 1 1 1 2 社會環(huán)境下網(wǎng)頁重要性的研究 12 3 4 5 6 7 8 9 10 11 12 重 復(fù)幾次后，我們的到一個良好的接近 PageRank 理想值的近似值。根據(jù) Lawrence Page和 Sergey Brin 共開發(fā)表的文章，他們實(shí)際需要進(jìn)行 100 次迭代才能得到整個互聯(lián)網(wǎng)的滿意的網(wǎng)頁級別值。 同樣，用迭代計算的方式，每個網(wǎng)頁的 PageRank 值之和仍然收斂于整個網(wǎng)絡(luò)的頁面數(shù)的。因此，每個頁面的平均的 PageRank 值為 1。實(shí)際上的值在 (1－ d)和 (dN+(1d))之間，這里的 N 是互聯(lián)網(wǎng)網(wǎng)頁總數(shù)。如果所有頁面都連接到一個頁面，并且此頁單獨(dú)地連接自身，那么將出現(xiàn)理論上的最大值。 傳統(tǒng) PageRank 算法向量表達(dá)形式 上述過程在本質(zhì)上可以表達(dá)為特征向量 ○ 2 的計算 ,首先每個網(wǎng)頁文檔的 PageRank 值可以表示一個向量 ,即一個 N 行 1 列的向量 (N 為所有的網(wǎng)文檔數(shù) )， 為了便于計算 ， 開始時可以給每個元素的值設(shè)為 1/ N。 Rank = ［ 1/ N ］ n 1 設(shè) M為一個隨機(jī)矩陣 ， 它的橫縱行列數(shù)分別為整個網(wǎng)頁集合的文檔數(shù) ， 每個矩陣元素值表示兩兩網(wǎng)頁之間的鏈接關(guān)系 ,即如果網(wǎng)頁 Di指向 Dj， 則矩陣元素 Mij 對應(yīng)的值為 1/ Ni ( Ni表示 Di的鏈出網(wǎng)頁數(shù) )； 如果網(wǎng)頁 Di不指向 Dj， 則 M ij值為 0。 M=11 , 12 , .. .. .. .. .. , 121 , 22 , .. .. .. .. ., 2..................................1 , 2 , .. .. .. .. ..nnn n nnm m mm m mm m m???????? 所以 , PageRank 值的計算就可以表示為 ： Rank = MT Rank () 而且這個過程是個反復(fù)迭代的過程 ,直至 Rank值最終收斂 。 但是 ， 實(shí)際的網(wǎng)頁結(jié)構(gòu)并社會環(huán)境下網(wǎng)頁重要性的研究 13 非表現(xiàn)為一個完全牢固的鏈接圖 ， 不是所有的網(wǎng)頁都可以從其他網(wǎng)頁 通過超鏈來達(dá)到 ，而 PageRank值的計算正依賴于此 ， 所以 Page等人就提出了改進(jìn)方案 ， 對存在的等級沉沒(Rank Sink)和等級泄漏 (Rank Leak)[8]等問題進(jìn)行了有效的解決 。 整個網(wǎng)頁圖中的一組緊密鏈接的網(wǎng)頁如果沒有外出的鏈接就產(chǎn)生等級沉沒 ， 一個獨(dú)立的網(wǎng)頁如果沒有外出的鏈接就產(chǎn)生等級泄漏 。 所以 ， Page改進(jìn)措施為 ： 一是剔除產(chǎn)生等級泄漏的獨(dú)立網(wǎng)頁以消除其不利影響 ； 二是給產(chǎn)生等級沉沒的網(wǎng)頁添加一個指向鏈入網(wǎng)頁的返回鏈接 ， 此時使得所有網(wǎng)頁 PageRank 值的計算就不完全依賴現(xiàn)有鏈接了 ， 所以修正的 PageRank計算公式為 ： ? ? () ( ) / ( ) ( )v B uR u C R v N v C E u???? () 其中 ，‖ R′‖ 1=1， 對應(yīng)的矩陣形式為 V’=c(AV’+E)。 E(u)是個常量 ， 它可以抑制 PageRank 值的傳播 ， 使得所有網(wǎng)頁的 PageRank 值至少會為 E ( u) ， 而不會為 0。 具體的 E ( u)值可以有多種取法 ， 簡單的做法可以設(shè)為 p， 如取 1/ N ( N為網(wǎng) 頁文檔總數(shù) )。 從特征向量的角度來考察 ， 可以設(shè)置 P列向量以代表每個網(wǎng)頁文檔都有的、相同的 E ( u) ? ?1/PN? n? 1 PageRank迭代運(yùn)算都利用了特征向量作為理論基礎(chǔ)和收斂性依據(jù) [9]，這是超鏈接環(huán)境下此類算法的一個共同特征 。 設(shè)置 D 向量以代表網(wǎng)頁文檔的鏈出網(wǎng)頁數(shù)是否為 0 , 即 1 如果網(wǎng)頁 Di的鏈出網(wǎng)頁數(shù)為 0 Di= 0 如果網(wǎng)頁 Di的鏈出網(wǎng)頁數(shù)非 0 則上述 PageRank 的計算可以進(jìn)一步表達(dá)為 : Rank = C ( M + P D T ) Rank + C P 傳統(tǒng) Google PageRank 的缺陷和改進(jìn)方法 基于鏈接分析的算法 ,目前的研究都還很不成熟，無論是 Page Rank算法，還是 HITS算法等，有一些共同的問題影響著算 法的精度。 ( 1) 根集的質(zhì)量。根集質(zhì)量應(yīng)該是很高的 , 否則 , 擴(kuò)展后的網(wǎng)頁集會增加很多無關(guān)的網(wǎng)頁 , 產(chǎn)生主題漂移 、 主題泛化等一系列的問題 ,計算量也增加很多。 算法再好 ,也無法在低質(zhì)量網(wǎng)頁集找出很多高質(zhì)量的 網(wǎng)頁。 (2) 錨文本的利用。錨文本有很高的精度 ,對鏈接 和目標(biāo)網(wǎng)頁的描述比較精確。上述算法在具體的 實(shí)現(xiàn)中利用了錨文本來 改進(jìn) 算法。如何準(zhǔn)確充分地利用錨文本 ,對算法的精度影響很大。 社會環(huán)境下網(wǎng)頁重要性的研究 14 (3) 噪音鏈接。 Web 上不是每個鏈接都包含了有用的信息 ， 比如廣告 、 站點(diǎn)導(dǎo)航 、 贊助商 、 用于友情交換的鏈接 ， 對于鏈接分析不僅沒有幫助 ， 而且還影 響結(jié)果。如何有效去除這些無關(guān)鏈接 ， 也是算法的一個關(guān)鍵點(diǎn)。 (4) 查詢的分類。每種算法都有自身的適用情況 , 對于不同的查詢 ,應(yīng)該采用不同的算法 ,以求獲得最好的結(jié)果。因此 ,對于查詢的分類也顯得非常重要。 文中對 Google PageRank算法進(jìn)行了深入探討和比較 ,但在這幾個方面需要繼續(xù)做深入的研究 ,相信在不久的將來會有更多的有價值的成果出現(xiàn)。本文正是針對 Google PageRank存在的問題進(jìn)行算法的 改進(jìn) ，將 改進(jìn) 的算法和 Google PageRank的 傳統(tǒng) 算法 完美結(jié)合 ，不僅解決的 Google PageRank完全不考慮訪問者自身知識水平的 缺陷 ，還預(yù)示了將不同算法結(jié)合是未來搜索引擎的發(fā)展趨勢。 社會環(huán)境下網(wǎng)頁重要性的研究 15 3． Google PageRank 算法 改進(jìn) 知識水平及其投票 的情況決定網(wǎng)頁排名的 PageRank 算法 算法中 PR 值的含義 在 Google PageRank 傳統(tǒng) 算法中， PageRank 就是一個概率 (它反映了一個人在網(wǎng)絡(luò)中不同的頁面上隨機(jī)點(diǎn)擊鏈接會到達(dá)某個特定網(wǎng)站的概率 )。只不過因?yàn)槿藗儾惶矚g看小數(shù)，Google 才更改了度量。 轉(zhuǎn)化為 0~10 度 量 。因此可以認(rèn)為 傳統(tǒng) 算法的網(wǎng)頁 PR 值，反映了網(wǎng)頁的熱度 (訪問人數(shù) )， PR 值越大，則表示網(wǎng)頁越熱，越多人訪問。 在改進(jìn)算法中，訪問者的 PR 值表示為 PRin， PRin越大則表示訪問者的專業(yè)知識水平越高。網(wǎng)頁的 PR 值表示為 Pij， Pij 越大表示網(wǎng)頁的權(quán)威性、正確性越大。 從投票角度分析算法的本質(zhì) 從投票的角度來分析兩種算法的本質(zhì)： Google PageRank 傳統(tǒng) 算法中，從網(wǎng)頁 A 指向網(wǎng)頁 B 的鏈接解釋為由網(wǎng)頁 A 對網(wǎng)頁 B 所投的一票，由其他網(wǎng)頁對網(wǎng)頁本身的投票來計算網(wǎng)頁的 PR 值。在改進(jìn)算法 中，訪問者對網(wǎng)頁的投票的被認(rèn)同度就是其他訪問者對他的投票，由其他訪問者對他的投票來計算訪問者的 PR 值。在計算網(wǎng)頁 PR 值時，網(wǎng)頁由訪問者對它的投票來決定網(wǎng)頁的 PR 值。 不是每個訪問者和網(wǎng)頁的投票都是對訪問者或者網(wǎng)頁的 PR 值貢獻(xiàn)一樣的，因?yàn)槊總€訪問者和網(wǎng)頁的權(quán)重不一樣，兩者的權(quán)重分別與它們的知識水平和網(wǎng)頁權(quán)威性有關(guān)。因此計算兩者 PR 值之前要計算兩者的權(quán)重。 權(quán)重是一個相對的概念，是針對某一指標(biāo)而言。某一指標(biāo)的權(quán)重是指該指標(biāo)在整體評價中的相對重要程度。 權(quán)重表示在評價過程中，是被評價對象的不同側(cè)面的重要程度的定 量分配，對各評價因子在總體評價中的作用進(jìn)行區(qū)別對待。事實(shí)上，沒有重點(diǎn)的評價就不算是客觀的評價。 打個比方說 , 一件事情 , 你給它打 100 分 , 你的老板給它打 60 分 , 如果平均 , 則是(100+60)