8. Searching and Ranking

PageRank演算法(文章內容出自維基百科)

PageRank

PageRank網頁排名,又稱網頁級別Google左側排名佩奇排名,是一種由搜索引擎根據網頁之間相互的超連結計算的網頁排名技術,以Google公司創辦人拉里·佩奇(Larry Page)之姓來命名。此技術通常和搜索引擎優化有關,Google用它來體現網頁的相關性和重要性。Google的創始人拉里·佩奇和謝爾蓋·布林於1998年在史丹福大學發明了這項技術。

PageRank通過網路浩瀚的超連結關係來確定一個頁面的等級。Google把從A頁面到B頁面的連結解釋為A頁面給B頁面投票,Google根據投票來源(甚至來源的來源,即連結到A頁面的頁面)和投票目標的等級來決定新的等級。簡單的說,一個高等級的頁面可以使其他低等級頁面的等級提升。

PageRank讓連結來"投票"

一個頁面的「得票數」由所有鏈向它的頁面的重要性來決定,到一個頁面的超連結相當於對該頁投一票。一個頁面的PageRank是由所有鏈向它的頁面「鏈入頁面」的重要性經過遞歸演算法得到的。一個有較多鏈入的頁面會有較高的等級,相反如果一個頁面沒有任何鏈入頁面,那麼它沒有等級。

2005年初,Google為網頁連結推出一項新屬性nofollow,使得網站管理員和網誌作者可以做出一些Google不計票的連結,也就是說這些連結不算作"投票"nofollow 的設置可以抵制評論垃圾。

Google工具列上的PageRank指標從010。它似乎是一個對數標度演算法,細節未知。PageRank Google 的商標,其技術亦已經申請專利。PageRank演算法中的點擊演算法是由Jon Kleinberg提出的。

假設一個由4個頁面組成的小團體:ABCD。如果所有頁面都鏈向A,那麼APR(PageRank)值將是BCD的和。

PR(A) = PR(B) + PR(C) + PR(D)

繼續假設B也有連結到C,並且D也有連結到包括A的3個頁面。一個頁面不能投票2次。所以B給每個頁面半票。以同樣的邏輯D投出的票只有三分之一算到了A的 PageRank 上。

PR(A)= \frac{PR(B)}{2}+ \frac{PR(C)}{1}+ \frac{PR(D)}{3}

換句話說,根據鏈處總數平分一個頁面的PR值。

PR(A)= \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}

最後,所有這些被換算為一個百分比再乘上一個係數q。由於下面的演算法,沒有頁面的PageRank會是0。所以,Google通過數學系統給了每個頁面一個最小值1 − q

PR(A)=\left( \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}+\,\cdots \right) q + 1 - q

所以一個頁面的 PageRank 是由其他頁面的PageRank計算得到。Google 不斷的重複計算每個頁面的 PageRank。如果您給每個頁面一個隨機 PageRank 值(非0),那麼經過不斷的重複計算,這些頁面的 PR 值會趨向于正常和穩定。這就是搜索引擎使用它的原因。

[編輯] 完整的

這個方程式引入了隨機瀏覽的概念,即有人上網無聊隨機打開一些頁面,點一些連結。一個頁面的PageRank值也影響了它被隨機瀏覽的機率。為了便於理解,這裡假設上網者不斷點網頁上的連結,最終到了一個沒有任何鏈出頁面的網頁,這時候上網者會隨機到另外的網頁開始瀏覽。

為了對那些有鏈出的頁面公平,q = 0.15(q的意義見上文)的演算法被用到了所有頁面上, 估算頁面可能被上網者放入書籤的機率。

所以,這個等式如下:

{\rm PageRank}(p_i) = \frac{q}{N} + (1 -q) \sum_{p_j} \frac{{\rm PageRank} (p_j)}{L(p_j)}

p1,p2,...,pN是被研究的頁面,M(pi)是鏈入pi頁面的數量,L(pj)pj鏈出頁面的數量,而N是所有頁面的數量。

PageRank值是一個特殊矩陣中的特徵向量。這個特徵向量為

\mathbf{R} = \begin{bmatrix} {\rm PageRank}(p_1) \\ {\rm PageRank}(p_2) \\ \vdots \\ {\rm PageRank}(p_N) \end{bmatrix}

R是等式的答案

\mathbf{R} = \begin{bmatrix} {q / N} \\ {q / N} \\ \vdots \\ {q / N} \end{bmatrix} + (1-q) \begin{bmatrix} \ell(p_1,p_1) & \ell(p_1,p_2) & \cdots & \ell(p_1,p_N) \\ \ell(p_2,p_1) & \ddots & & \\ \vdots & & \ell(p_i,p_j) & \\ \ell(p_N,p_1) & & & \ell(p_N,p_N) \end{bmatrix} \mathbf{R}

如果pj不鏈向pi, 而且對每個j都成立時,\ell(p_i,p_j)等於 0

\sum_{i = 1}^N \ell(p_i,p_j) = 1,

這項技術的主要缺點是舊的頁面等級會比新頁面高。因為即使是非常好的新頁面也不會有很多上游連結,除非它是某個站點的子站點。

 

HITS演算法詳解(文章內容出自不及格網管)


HITS(Hyper-link-induced topic search)是由kleinberg提出來的基於連接分析的網頁排名演算法,描述2種類型的網頁:“權威性(authority)的網頁”:對於一個特定的的檢索,該網頁提供最好的相關資訊;“目錄型(hub)網頁”:該網頁提供很多指向其他高品質權威型的網頁鏈結。由此,我們可以在每個網頁上定義“目錄型權值”和“權威型權值”2個參數。
1)HITS演算法基本思想:
1、好的hub型網頁指向好的authority型網頁
2、好的authority型網頁是由好的hub型網頁所指向的網頁
2)Hits演算法

HITS(Hyperlink – Induced Topic Search) 演算法是利用HubPAuthority的搜索方法,具體演算法如下:將查詢q提交給基於關鍵字查詢的檢索系統,從返回結果頁面的集合總取前n個網頁(如n=200),作為根集合(root set),記為S,則S滿足:
1.S中的網頁數量較少
2.S中的網頁是與查詢q相關的網頁
3.S中的網頁包含較多的權威(Authority)網頁

通過向S中加入被S引用的網頁和引用S的網頁,將S擴展成一個更大的集合T。以T中的Hub 網頁為頂點集V1,以權威網頁為頂點集V2 。V1中的網頁到V2中的網頁的超鏈結為邊集E,形成一個二分有向圖。對V1中的任一個頂點v ,用h( v)表示網頁v的Hub值,且h(v)收斂,對V2中的頂點u,用a(u) 表示網頁的Authority值。開始時h ( v) = a ( u) = 1,對u 執行I 操作,修改它的a ( u) ,對v執行O操作,修改它的h ( v),然後規範化a ( u)Ph ( v),如此不斷的重複計算下面的I操作和O操作直到a ( u) 。其中I操作:a ( u) = Σh ( v);O 操作:h ( v) = Σa ( u) 。每次迭代對a ( u) 、h ( v) 進行規範化處理:a ( u) = a ( u)PΣ[ a ( q) ]2;h ( v) = h ( v)PΣ[ h ( q) ]2 。

HITS演算法可以獲得比較好的查全率,輸出一組具有較大Hub值的網頁和具有較大權威值的網頁。但在實際應用中HITS演算法有以下幾個問題:

由S 生成T 的時間開銷是很昂貴的,由T 生成有向圖也很耗時,需要分別計算網頁的APH值,計算量大;網頁中廣告等無關鏈結影響A、H值的計算,降低HITS演算法的精度;HITS演算法只計算主特徵向量,處理不好主題漂移問題;進行窄主題查詢時,可能產生主題泛化問題。

相關分析演算法大體可以分為4 類:
基於隨機漫遊模型的演算法,比如PageRank、Repution演算法;基於Hub和Authority 相互加強模型的演算法,如HITS 及其變種;基於概率模型的演算法,如SALSA、PHITS;基於貝葉斯模型的演算法,如貝葉斯演算法。


所有的演算法在實際應用中都結合傳統的內容分析技術進行優化。Allan Borodin 也指出沒有一種演算法是完美的,在某些查詢下,結果可能很好,在另外的查詢下,結果可能很差。
將S擴展為基本集合(base set) T,T包含由S指出或指向S的網頁。可以設定一個上限如 1000—5000個網頁。開始權重傳播。在集合T中計算每個網頁的目錄型權值和權威型權值。Clever的做法是採用目錄型網頁和權威型網頁相互評價的辦法進行遞迴計算。對於一個網頁p,用xp來表示網頁p的權威型權值,用yp來表示它的目錄型權值,並且用如下公式進行計算:
1.計算各節點的Hub和Authority。
2.賦予每個節點的hub值和authority值都為1。
3.運行Authority更新規則。
4.運行Hub更新規則。
5.Normalize數值,即每個節點的Hub值除所有Hub值之和,每個Authority值除所有Authority值之和。
6.必要時從第二步開始重複。


HITS演算法與PageRank演算法比較(文章內容出自不及格網管)

HITS演算法PageRank演算法可以說是搜索引擎鏈結分析的兩個最基礎且最重要的演算法。從以上對兩個演算法的介紹可以看出,兩者無論是在基本概念模型還是計算思路以及技術實現細節都有很大的不同,下面對兩者之間的差異進行逐一說明。

1.HITS演算法是與用戶輸入的查詢請求密切相關的,而PageRank與查詢請求無關。所以,HITS演算法可以單獨作為相似性計算評價標準,而PageRank必須結合內容相似性計算才可以用來對網頁相關性進行評價。

2.HITS演算法因為與用戶查詢密切相關,所以必須在接收到用戶查詢後即時進行計算,計算效率較低;而PageRank則可以在爬蟲抓取完成後離線計算,線上直接使用計算結果,計算效率較高。

3.HITS演算法的計算物件數量較少,只需計算擴展集合內網頁之間的鏈結關係;而PageRank是全局性演算法,對所有互聯網頁面節點進行處理。

4.從兩者的計算效率和處理物件集合大小來比較,PageRank更適合部署在伺服器端,而HITS演算法更適合部署在用戶端。

5.HITS演算法存在主題泛化問題,所以更適合處理具體化的用戶查詢;而PageRank在處理寬泛的用戶查詢時更有優勢。

6.HITS演算法在計算時,對於每個頁面需要計算兩個分值,而PageRank只需計算一個分值即可;在搜索引擎領域,更重視HITS演算法計算出的Authority權值,但是在很多應用HITS演算法的其他領域,Hub分值也有很重要的作用。

7.從鏈結反作弊的角度來說,PageRank從機制上優於HITS演算法,而HITS演算法更易遭受鏈結作弊的影響。

8.HITS演算法結構不穩定,當對“擴充網頁集合”內鏈結關係作出很小改變,則對最終排名有很大影響;而PageRank相對HITS而言表現穩定,其根本原因在於PageRank計算時的“遠端跳轉”。