1、網(wǎng)頁排序算法PagerankHitsHilltopTrustRank碩0032班 3110082019 1Pagerankpagerank對網(wǎng)頁的重要性進行客觀的測定。PageRank 會將網(wǎng)頁 A 上指向網(wǎng)頁 B 的鏈接解釋為由網(wǎng)頁 A 對網(wǎng)頁 B 所投的一票，而不是計算直接的鏈接數(shù)。PageRank 也會考慮發(fā)出投票的每個網(wǎng)頁的重要性，也就是某些網(wǎng)頁的投票具有的價值較大，為該鏈接的頁面賦予的價值因而也就較大。 重要的網(wǎng)頁會得到較高的 PageRank，并出現(xiàn)在搜索結果的頂部。 Google 的技術是利用網(wǎng)絡中的綜合信息來確定網(wǎng)頁的重要性。 因為沒有人工干涉，也不對結果進行操縱，所以用戶一直

2、信任 Google 是一個不會因付費而影響排名的客觀信息來源。2PageRank的大小取決于三個因素：鏈入網(wǎng)頁數(shù)鏈入網(wǎng)頁的質量鏈入網(wǎng)頁的鏈出網(wǎng)頁數(shù)PageRank3PageRank的大小取決于三個因素：鏈入網(wǎng)頁數(shù)鏈入網(wǎng)頁的質量鏈入網(wǎng)頁的鏈出網(wǎng)頁數(shù)PageRank4矩陣表示頁面的重要性由鏈向它的頁面的重要性決定頁面i的重要性 指向頁面i的頁面集頁面j的出鏈頁面j的重要性5計算PR(A)=(1-d) + d*(PR(T1)/C(T1)+ PR(Tn)/C(Tn)d: 阻尼系數(shù), 通常設置為0.85.一個用戶不用通過鍵入URL地址 ，而是點擊鏈接的概率T1, , Tn: 指向頁面A的頁面集PR(A)

3、: 頁面A的權威值.PR(Ti): 頁面Ti的權威值.C(Ti): 頁面Ti的出鏈.6Example of CalculationPage A 1Page C1Page B1Page D11*0.85/21*0.85/21*0.851*0.851*0.857Example of calculation經(jīng)過20 次迭代：Page A 1.490Page C1.577Page B0.783Page D0.158Pagerank的問題PageRank算法中對于向外鏈接的權值貢獻是平均的，不考慮不同鏈接的重要性。1.有些鏈接具有注釋性，也有些鏈接是起導航或廣告作用。有注釋性的鏈接才用于權威判斷。2.基

4、于商業(yè)或競爭因素考慮，很少有WEB網(wǎng)頁指向其競爭領域的權威網(wǎng)頁。9HitsHITS是英文Hyperlink-Induced Topic Search 的縮寫意譯為超鏈引導主題搜索。HITS 算法由Jon Kleinberg 于1997 年提出，并申請了專利。其基本思想是利用頁面之間的引用鏈來挖掘隱含在其中的有用信息。具有計算簡單且高效的特點。Hits算法認為對每一個頁面應該將其內容權威度（authority)和鏈接權威度（hub）分開考慮，在對網(wǎng)頁內容權威度做出評價的基礎上再對頁面鏈接權威度進行評價，然后給出該頁面的綜合評價。10hub和anthority鏈接權威度（hub）指的是頁面上所有導

5、出鏈接指向頁面的內容權威值之和。內容權威度（authority）指的是所有導入鏈接所在頁面的鏈接權威度之和對于一個給定的查詢，每個頁面都被賦予了一個特定的鏈接權威度（hub）和內容權威度（authority）結果就是高權威度的頁面11Hits算法過程HITS算法的求解過程如下：1、得出根集頁面2、將所有頁面（根集頁面）的A和H賦予初值。3、計算新一輪的H和A的值。4、規(guī)范化結果5、重復3、4, 直到結果收斂。12根集頁面將查詢q提交給傳統(tǒng)的基于關鍵字匹配的搜索引擎搜索引擎返回很多網(wǎng)頁，從中取前n個網(wǎng)頁作為根集(root set)，用S表示。S滿足如下3個條件：1S中網(wǎng)頁數(shù)量相對較小2S中網(wǎng)頁大

6、多數(shù)是與查詢q相關的網(wǎng)頁3S中網(wǎng)頁包含較多的權威網(wǎng)頁。通過向S中加入被S引用的網(wǎng)頁和引用S的網(wǎng)頁將S擴展成一個更大的集合T(base set)13Hub和Authority的計算基集上的迭代算法: 內容權威值（authority weights ）a(p) 鏈接權威值（hub weights） h(p) 所有的網(wǎng)頁初始化a(p) = 1，h(p) = 1重復下面兩步并且規(guī)范化處理直到權威值收斂：。 14規(guī)范化處理15矩陣表示AMHii*1-=HMAiTi*1-=HMMHTii*1-=AMMAiTi*1-=16例子 Iteration 0 1 2 3 XYZX is the best hub i

7、s most authoritative17Hits 的問題HITS 算法的最大缺點是，它是在查詢階段進行計算，而不是在抓取或預處理階段。以犧牲查詢排名響應時間為代價的。不過HITS 算法的思想很可能融入到搜索引擎的索引階段，也就是根據(jù)鏈接關系找出具有hub特征或authority特征的頁面。HITS 算法還存在主題漂移的問題，如果在集合T中有少數(shù)與查詢主題無關的網(wǎng)頁，但是他們是緊密鏈接的，HITS算法的結果可能就偏離了原來的查詢主題網(wǎng)頁中一些無關的鏈接影響A，H值的計算18PageRank v.s. HitsPageRank 查詢之前就計算了所有數(shù)據(jù)庫中網(wǎng)頁的權威值只計算權威值迭代計算量大，

8、計算速度快HITS 每次只檢索跟查詢有關的網(wǎng)頁 計算兩個值，內容權威值（authority）鏈接權威值（hub）計算簡單，在線實時計算耗時多19HILLTOP算法HillTop ，是一項搜索引擎結果排序的專利，是Google的一個工程師Bharat在2001年獲得的專利。Hilltop算法的指導思想和PageRank一致，都是通過網(wǎng)頁被鏈接的數(shù)量和質量來確定搜索結果的排序權。但hilltop認為只計算來自具有相同主題的相關文檔鏈接對于權重計算的貢獻比主題不相關的鏈接價值要更高。Bharat稱這種對主題有影響的文檔為“專家”文檔，從這些專家文檔頁面到目標文檔頁面的鏈接決定被鏈接網(wǎng)頁的權重值20H

9、illtop算法步驟1.根據(jù)查詢尋找“專家網(wǎng)頁”。計算專家頁面得分。2.給頂部專家網(wǎng)頁鏈向的目標網(wǎng)頁打分，這個過程綜合了它與所有相關專家網(wǎng)頁的鏈接關系基于“專家”文檔的Hilltop算法最大的難點是第一次“專家文檔”的篩選。目前Google首先給了.edu,.gov和.org站點很高的優(yōu)先級。211.1專家頁面的條件搜索引擎根據(jù)用戶查詢日志發(fā)現(xiàn)熱門關鍵詞后，開始針對這些熱門關鍵詞尋找專家頁面成為專家頁面的2個必要因素必須存在足夠多而且不存在隸屬關系的出鏈（檢測k個出鏈的URL是否指向k個無從屬關系的獨立主機）至少存在一個短語包含該熱門關鍵詞的所有術語22從屬關系兩臺主機,如果滿足下列條件之一或

10、兩者都滿足,則這兩臺主機是有從屬關系的:他們擁有相同的前3段IP地址主機名最右邊的特殊標記相同.例如:比較和ibm.co.mx,分別忽略它們的類別后綴com”和co.mx,最右邊得到的標記都是”ibm.因此它們被認為有從屬關系.從屬關系是具有傳遞性的:如果A和B有從屬關系并且B和C也有從屬關系,那么即使A和C沒有明顯的直接聯(lián)系,也會被認為有從屬關系231.2專家頁面評分確定專家頁面后，在該頁面上找出所有包含熱門關鍵詞中術語或者差1到2個術語的短語將這些短語分為三個等級分。分別為全部包含S0、差1-S1、差2S2分別計算等級分這三個等級相差很大 依次為232 216和1而短語得分取決于這個短語在

11、頁面中的位置，分數(shù)從高到低-標題 、頭部、 錨文本等等等級分是對各個等級中所有短語得分的和。然后綜合計算這三個等級得分就得到專家分更傾向于完全匹配24專家頁面得分Expert_Score = 232 * S0 + 216 * S1 + S2Si = SUMkey phrases p with k - i query terms LevelScore(p) * FullnessFactor(p, q)LevelScore(p)是定義好的關鍵短語p的類型得分，在HillTop算法 中名稱短語(title)的是16，標題(head)是6，錨文本(anchor)是1完整性因子FullnessFacto

12、r(p,q)是對q中關鍵詞覆蓋了p中關鍵詞的數(shù) 量的度量。 設plen是P的長度，m是在p中而不在q中出現(xiàn)的術語的數(shù)量， FullnessFactor(p,q)的計算公式為：If m2, FullnessFactor(p,q)=1-(m-2)/plen252.1對目標頁評分由排名前N個(至少兩個)非隸屬的專家頁面指向的頁面稱為目標頁面。目標頁面的分數(shù)通過以下三步計算：1. 對每一個專家頁面E指向目標頁面T畫邊Edge(E,T)對每一個查詢關鍵詞w，設occ(w,T)是專家文檔E中包含w且修飾Edge(E,T)的關鍵短語的數(shù)量。 If occ=0 Edgescore=0 else Edgesco

13、re=Expertscore* SUMquery keywords w occ(w，t)2.檢查指向同一頁面的專家頁面的從屬性，若存屬性相同則刪去minedgescore3.targetscore=sumedgescore26重要特征先計算一個與用戶查詢主題最相關的“專家文檔”頁面列表，然后通過專家頁面找到目標頁面，目標頁面按照指向他們的非附屬專家文檔的數(shù)量和相關性進行排名若沒有找到搜索引擎認為足夠的“專家文檔”（要求至少兩個），則該算法失效即結果返回為零對于高度明確化的查詢條件，此算法的結果很可能為027存在問題專家頁面的搜索和確定對算法起關鍵作用；而其質量和公平難以保證Hilltop忽略了

14、大多數(shù)非專家頁面的影響專家頁面只占到整個頁面的1.79%，不能全面反映民意Hilltop也是在線運行的，勢必會影響查詢響應時間，隨著專家頁面集合的增大，算法的可伸縮性存在不足之處28TrustRank算法TrustRank 是近年來比較受關注的基于鏈接關系的排名算法。TrustRank 中文可以翻譯為信任指數(shù)。TrustRank 算法最初來自于2004 年斯坦福大學和雅虎的一項聯(lián)合研究，用來檢測垃圾網(wǎng)站，并且于2006 年申請專利。29TrustRank 算法核心思想網(wǎng)站TrustRank的計算采用人工和機器連接分析相結合的方式。通過Google或其他一些檢索機構的專家，可以先確定一批站點的T

15、R值，在通過機器的連接結構分析來確定互聯(lián)網(wǎng)上其他站點TrustRank值，然后以TR值的高低來做為網(wǎng)頁排名的一個重要依據(jù)。跟PR值原理類似，如果其他站點獲得了來自高Tr值站點的連接也將獲得更高的TR值。Google TrustRank應該是以站點而不是頁面為單位的。 。30排名影響GoogleTrustRank對于網(wǎng)站排名有種非常重要的影響：。站點內的頁面在其他情況參數(shù)接近的情況下。高TR值的站點內頁面將獲得比其他站點頁面更高的排名。高TR值站點的頁面收錄速度加快。因為Google對它認為重要的站點會頻繁訪問。獲得足夠的TR值的站點可以避免Sandbox。如果一個站點的信任指數(shù)太低，googl

16、e將可能會將其進行懲罰，包括進入sandbox等。如果一個站點的信任指數(shù)太低，即使其他參數(shù)非常理想，在較熱門關鍵詞上，也很難獲得好的排名表現(xiàn)。31步驟（1/3）計算TrustRank 值首先要選擇一批種子網(wǎng)站，然后人工查看網(wǎng)站，設定一個初始TrustRank 值。挑選種子網(wǎng)站有兩種方式：選擇導出鏈接最多的網(wǎng)站挑選種子網(wǎng)站的方法是選PR 值高的網(wǎng)站，因為PR 值越高，在搜索結果頁面出現(xiàn)的概率就越大。這些網(wǎng)站才正是TrustRank 算法最關注的、需要調整排名的網(wǎng)站。那些PR 值很低的頁面，在沒有TrustRank 算法時排名也很靠后，計算TrustRank 意義就不大了。根據(jù)測算，挑選出兩百個左

17、右網(wǎng)站作為種子，就可以比較精確地計算出所有網(wǎng)站的TrustRank值。32步驟（2/3）計算TrustRank 隨鏈接關系減少的公式有兩種方式。一是隨鏈接次數(shù)衰減，也就是說第一層頁面TrustRank 指數(shù)是一百的話，第二層頁面衰減為90，第三層衰減為80。按導出鏈接數(shù)目分配TrustRank 值，也就是說一個頁面的TrustRank 值是一百，頁面上有5 個導出鏈接的話，每個鏈接將傳遞20%的TrustRank 值。衰減和分配兩種計算方法通常綜合使用，整體效果都是隨著鏈接層次的增加，TrustRank 值逐步降低。33步驟（3/3）得出網(wǎng)站和頁面的TrustRank 值后，可以通過兩種方式影響排名。一是把傳統(tǒng)排名算法挑選出的多個頁面，根據(jù)TrustRank 值比較，重新做排名調整。設定一個最低TrustRank 值門檻，只有超過這個門檻TrustRank 值的頁面，才被認為有足夠的質量進入排名，低于門檻的頁面將被認為是垃圾頁面，從搜索結果中過濾出去。34TrustRank的弊端由于TrustRank對整體排名的影響，著名和權威