【正文】 ree(s) 0 } (G’的Authority邊). E= { (sh , ra) |2． 從集合T構(gòu)造無向圖G’＝（Vh，Va，E）Vh = { sh |2．3 SALSA算法 PageRank算法是基于用戶隨機(jī)的向前瀏覽網(wǎng)頁的直覺知識，HITS算法考慮的是Authoritive網(wǎng)頁和Hub網(wǎng)頁之間的加強(qiáng)關(guān)系。2．2．3．4 閾值（Threshhold—Kleinberg）算法Allan Borodin等在[11]中同時提出了3種閾值控制的算法，分別是Hub閾值算法，Authority閾值算法，以及結(jié)合2者的全閾值算法。2．2．3．3 Hub平均（ Hub－Averaging－Kleinberg）算法 Allan Borodin等在[11]指出了一種現(xiàn)象，設(shè)有M＋1個Hub網(wǎng)頁，M＋1個權(quán)威網(wǎng)頁，前M個Hub指向第一個權(quán)威網(wǎng)頁，第M＋1個Hub網(wǎng)頁指向了所有M＋1個權(quán)威網(wǎng)頁。2． HITS算法中，每個鏈接對應(yīng)的矩陣值設(shè)為1，實際上每個鏈接的重要性是不同的，ARC算法考慮了鏈接周圍的文本來確定鏈接的重要性。根據(jù)不同閾值進(jìn)行處理，刪除不滿足條件的文檔，再運行imp算法計算文檔的A/H值，這些算法分別稱為med，startmed，maxby10。I，O操作改為如下I 操作： O操作： 調(diào)整后的算法有效的解決了問題2，稱之為imp算法。泛化的原因是因為網(wǎng)頁中包含不同主題的向外鏈接，而且新主題的鏈接具有更加的重要性。5．HITS算法最大的弱點是處理不好主題漂移問題（topic drift）[7,8]，也就是緊密鏈接TKC（TightlyKnit Community Effect）現(xiàn)象[8]。在制作網(wǎng)頁的時候，有些開發(fā)工具會自動的在網(wǎng)頁上加入一些鏈接，這些鏈接大多是與查詢主題無關(guān)的。需要分別計算網(wǎng)頁的A/H值，計算量比PageRank算法大。和PageRank算法一樣，可以用矩陣形式來描述算法，這里省略不寫。對V1中的任一個頂點v，用h(v)表示網(wǎng)頁v的Hub值，對V2中的頂點u，用a(u)表示網(wǎng)頁的Authority值。這種Hub與Authoritive網(wǎng)頁之間的相互加強(qiáng)關(guān)系，可用于權(quán)威網(wǎng)頁的發(fā)現(xiàn)和WEB結(jié)構(gòu)和資源的自動發(fā)現(xiàn)，這就是Hub/Authority方法的基本思想。比如Google主頁不會明確給出WEB搜索引擎之類的描述信息。2．2 HITS算法及其變種 PageRank算法中對于向外鏈接的權(quán)值貢獻(xiàn)是平均的，也就是不考慮不同鏈接的重要性。在PageRank算法的基礎(chǔ)上，其它的研究者提出了改進(jìn)的PageRank算法。PageRank計算時，把這種鏈接首先除去，等計算完以后再加入，這對原來計算出的網(wǎng)頁的rank值影響是很小的。實際上，只需要求出最大特征根的特征向量，就是網(wǎng)頁集對應(yīng)的最終PageRank值，這可以用迭代方法計算。前提2：假定用戶一開始隨機(jī)的訪問網(wǎng)頁集合中的一個網(wǎng)頁，以后跟隨網(wǎng)頁的向外鏈接向前瀏覽網(wǎng)頁，不回退瀏覽，瀏覽下一個網(wǎng)頁的概率就是被瀏覽網(wǎng)頁的PageRank值。Google的體系結(jié)構(gòu)類似于傳統(tǒng)的搜索引擎，它與傳統(tǒng)的搜索引擎最大的不同處在于對網(wǎng)頁進(jìn)行了基于權(quán)威值的排序處理，使最重要的網(wǎng)頁出現(xiàn)在結(jié)果的最前面。這些算法有的已經(jīng)在實際的系統(tǒng)中實現(xiàn)和使用，并且取得了良好的效果。另外，有些重要的網(wǎng)頁并不包含查詢項。WEB上的文檔和傳統(tǒng)的文檔比較，有很多新的特點，它們是分布的，異構(gòu)的，無結(jié)構(gòu)或者半結(jié)構(gòu)的，這就對傳統(tǒng)信息檢索技術(shù)提出了新的挑戰(zhàn)。[14]，每天增加約1百萬的文檔[6]，不到9個月的時間文檔總數(shù)就會翻一番[14]。有些站點有意提高關(guān)鍵字出現(xiàn)的頻率來提高自身在搜索引擎中的重要性，破壞搜索引擎結(jié)果的客觀性和準(zhǔn)確性?；谶@種超鏈分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法[1] ，同年J. Kleinberg提出了HITS算法[5]，其它一些學(xué)者也相繼提出了另外的鏈接分析算法，如SALSA，PHITS，Bayesian等算法。2. WEB超鏈分析算法2．1 Google和PageRank算法 搜索引擎Google最初是斯坦福大學(xué)的博士研究生Sergey Brin和Lawrence Page實現(xiàn)的一個原型系統(tǒng)[2]，現(xiàn)在已經(jīng)發(fā)展成為WWW上最好的搜索引擎之一。這種重要的網(wǎng)頁稱為權(quán)威（Authoritive）網(wǎng)頁。設(shè)V是對應(yīng)網(wǎng)頁集的一個向量，有V=cAV，V為A的特征根為c的特征向量。另外還有一些特殊的鏈接，指向的網(wǎng)頁沒有向外的鏈接。 同樣的查詢例子也可以說明另外一個問題，Google，Yahoo是WWW上最受歡迎的網(wǎng)頁，如果出現(xiàn)在查詢項car的結(jié)果集中，一定會有很多網(wǎng)頁指向它們，就會得到較高的rank值， 事實上他們與car不太相關(guān)。斯坦福大學(xué)計算機(jī)科學(xué)系A(chǔ)rvind Arasu等經(jīng)過試驗表明，PageRank算法計算效率還可以得到很大的提高[22]。很少有WEB網(wǎng)頁指向其競爭領(lǐng)域的權(quán)威網(wǎng)頁。一般來說，好的Hub網(wǎng)頁指向許多好的權(quán)威網(wǎng)頁；好的權(quán)威網(wǎng)頁是有許多好的Hub網(wǎng)頁指向的WEB網(wǎng)頁。 通過向S中加入被S引用的網(wǎng)頁和引用S的網(wǎng)頁將S擴(kuò)展成一個更大的集合T． 以T中的Hub網(wǎng)頁為頂點集Vl，以權(quán)威網(wǎng)頁為頂點集V2，Vl中的網(wǎng)頁到V2中的網(wǎng)頁的超鏈接為邊集E，形成一個二分有向圖SG＝(V1，V2，E)。式(2)反映了若一個網(wǎng)頁指向許多好的權(quán)威頁，則Hub值也會相應(yīng)增加(即Hub值增加為該網(wǎng)頁鏈接的所有網(wǎng)頁的權(quán)威值之和)。一般T比S大很多，由T生成有向圖也很耗時。3．網(wǎng)頁中一些無關(guān)的鏈接影響A，H值的計算。事實上，其它社區(qū)可能也非常重要。6．用HITS進(jìn)行窄主題查詢時，可能產(chǎn)生主題泛化問題[5,9]，即擴(kuò)展以后引入了比原來主題更重要的新的主題，新的主題可能與原始查詢無關(guān)。類似的，對于Hub值，假定主機(jī)A上某個文檔t指向主機(jī)B上的m個文檔，則B上m個文檔對t的Hub值總共貢獻(xiàn)1，每個文檔貢獻(xiàn)1/m。 在S擴(kuò)展到T后，計算每個文檔的主題相似度，根據(jù)不同的閾值（threshold）進(jìn)行刷選，可以選擇所有文檔相似度的中值，根集文檔相似度的中值，最大文檔相似度的分?jǐn)?shù)，如1/10，作為閾值。 ARC算法與HITS的不同主要有以下3點：1． 由根集S擴(kuò)展為T時，HITS只擴(kuò)展與根集中網(wǎng)頁鏈接路徑長度為1的網(wǎng)頁，也就是只擴(kuò)展直接與S相鄰的網(wǎng)頁，而ARC中把擴(kuò)展的鏈接長度增加到2，擴(kuò)展后的網(wǎng)頁集稱為增集（Augment Set）。構(gòu)造矩陣W，如果有網(wǎng)頁i－j ，Wi,j＝w（i，j），否則Wi,j＝0，H值設(shè)為1，Z為W的轉(zhuǎn)置矩陣，迭代執(zhí)行下面3個的操作：（1）A＝WH （2）H＝ZA （3）規(guī)范化A，H3． ARC算法的目標(biāo)是找到前15個最重要的網(wǎng)頁，只需要A/H的前15個值相對大小保持穩(wěn)定即可，不需要A/H整個收斂，這樣2中迭代次數(shù)很小就能滿足，[10]中指出迭代5次就可以，所以ARC算法有很高的計算效率，開銷主要是在擴(kuò)展根集上。因此，Allan Borodin修改了HITS的O操作：O操作： ，n是(v,u)的個數(shù) 調(diào)整以后，僅指向權(quán)威值高的網(wǎng)頁的Hub值比既指向權(quán)威值高又指向權(quán)威值低的網(wǎng)頁的Hub值高，此算法稱為Hub平均（Hub－Averaging－Kleinberg）算法。 同時使用Authority閾值算法和Hub閾值方法的算法，就是全