搜索引擎的算法

1、搜索引擎算法研究引言 萬(wàn)維網(wǎng)WWW（World Wide Web）是一個(gè)巨大的，分布全球的信息服務(wù)中心，正在以飛快的速度擴(kuò)展。1998年WWW上擁有約3.5億個(gè)文檔14，每天增加約1百萬(wàn)的文檔6，不到9個(gè)月的時(shí)間文檔總數(shù)就會(huì)翻一番14。WEB上的文檔和傳統(tǒng)的文檔比較，有很多新的特點(diǎn)，它們是分布的，異構(gòu)的，無(wú)結(jié)構(gòu)或者半結(jié)構(gòu)的，這就對(duì)傳統(tǒng)信息檢索技術(shù)提出了新的挑戰(zhàn)。 傳統(tǒng)的WEB搜索引擎大多數(shù)是基于關(guān)鍵字匹配的，返回的結(jié)果是包含查詢項(xiàng)的文檔，也有基于目錄分類的搜索引擎。這些搜索引擎的結(jié)果并不令人滿意。有些站點(diǎn)有意提高關(guān)鍵字出現(xiàn)的頻率來(lái)提高自身在搜索引擎中的重要性，破壞搜索引擎結(jié)果的客觀性和準(zhǔn)確性。

2、另外，有些重要的網(wǎng)頁(yè)并不包含查詢項(xiàng)。搜索引擎的分類目錄也不可能把所有的分類考慮全面，并且目錄大多靠人工維護(hù)，主觀性強(qiáng)，費(fèi)用高，更新速度慢2。 最近幾年，許多研究者發(fā)現(xiàn)，WWW上超鏈結(jié)構(gòu)是個(gè)非常豐富和重要的資源，如果能夠充分利用的話，可以極大的提高檢索結(jié)果的質(zhì)量?；谶@種超鏈分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法1，同年J. Kleinberg提出了HITS算法5，其它一些學(xué)者也相繼提出了另外的鏈接分析算法，如SALSA，PHITS，Bayesian等算法。這些算法有的已經(jīng)在實(shí)際的系統(tǒng)中實(shí)現(xiàn)和使用，并且取得了良好的效果。 文章的第2部

3、分按照時(shí)間順序詳細(xì)剖析了各種鏈接分析算法，對(duì)不同的算法進(jìn)行了比較。第3部分對(duì)這些算法做了評(píng)價(jià)和總結(jié)，指出了存在的問(wèn)題和改進(jìn)方向。 WEB超鏈分析算法 .Google和PageRank算法 搜索引擎Google最初是斯坦福大學(xué)的博士研究生Sergey Brin和Lawrence Page實(shí)現(xiàn)的一個(gè)原型系統(tǒng)2，現(xiàn)在已經(jīng)發(fā)展成為WWW上最好的搜索引擎之一。Google的體系結(jié)構(gòu)類似于傳統(tǒng)的搜索引擎，它與傳統(tǒng)的搜索引擎最大的不同處在于對(duì)網(wǎng)頁(yè)進(jìn)行了基于權(quán)威值的排序處理，使最重要的網(wǎng)頁(yè)出現(xiàn)在結(jié)果的最前面。Google通過(guò)PageRank元算法計(jì)算出網(wǎng)頁(yè)的PageRank值，從而決定網(wǎng)頁(yè)在結(jié)果集中的出現(xiàn)位置

4、，PageRank值越高的網(wǎng)頁(yè)，在結(jié)果中出現(xiàn)的位置越前。 PageRank算法基于下面2個(gè)前提： 前提1：一個(gè)網(wǎng)頁(yè)被多次引用，則它可能是很重要的；一個(gè)網(wǎng)頁(yè)雖然沒(méi)有被多次引用，但是被重要的網(wǎng)頁(yè)引用，則它也可能是很重要的；一個(gè)網(wǎng)頁(yè)的重要性被平均的傳遞到它所引用的網(wǎng)頁(yè)。這種重要的網(wǎng)頁(yè)稱為權(quán)威（Authoritive）網(wǎng)頁(yè)。 前提2：假定用戶一開(kāi)始隨機(jī)的訪問(wèn)網(wǎng)頁(yè)集合中的一個(gè)網(wǎng)頁(yè)，以后跟隨網(wǎng)頁(yè)的向外鏈接向前瀏覽網(wǎng)頁(yè)，不回退瀏覽，瀏覽下一個(gè)網(wǎng)頁(yè)的概率就是被瀏覽網(wǎng)頁(yè)的PageRank值。 簡(jiǎn)單PageRank算法描述如下：u是一個(gè)網(wǎng)頁(yè)，是u指向的網(wǎng)頁(yè)集合，是指向u的網(wǎng)頁(yè)集合，是u指向外的鏈接數(shù)，顯然=| |

5、 ，c是一個(gè)用于規(guī)范化的因子（Google通常取0.85），（這種表示法也適用于以后介紹的算法）則u的Rank值計(jì)算如下： 這就是算法的形式化描述，也可以用矩陣來(lái)描述此算法，設(shè)A為一個(gè)方陣，行和列對(duì)應(yīng)網(wǎng)頁(yè)集的網(wǎng)頁(yè)。如果網(wǎng)頁(yè)i有指向網(wǎng)頁(yè)j的一個(gè)鏈接，則，否則0。設(shè)V是對(duì)應(yīng)網(wǎng)頁(yè)集的一個(gè)向量，有V=cAV，V為A的特征根為c的特征向量。實(shí)際上，只需要求出最大特征根的特征向量，就是網(wǎng)頁(yè)集對(duì)應(yīng)的最終PageRank值，這可以用迭代方法計(jì)算。 如果有2個(gè)相互指向的網(wǎng)頁(yè)a，b,他們不指向其它任何網(wǎng)頁(yè)，另外有某個(gè)網(wǎng)頁(yè)c，指向a，b中的某一個(gè)，比如a，那么在迭代計(jì)算中，a，b的rank值不分布出去而不斷的累計(jì)。

6、如下圖： 為了解決這個(gè)問(wèn)題，Sergey Brin和Lawrence Page改進(jìn)了算法，引入了衰退因子E(u)，E(U)是對(duì)應(yīng)網(wǎng)頁(yè)集的某一向量，對(duì)應(yīng)rank的初始值，算法改進(jìn)如下： 其中，1，對(duì)應(yīng)的矩陣形式為V=c(AV+E)。 另外還有一些特殊的鏈接，指向的網(wǎng)頁(yè)沒(méi)有向外的鏈接。PageRank計(jì)算時(shí)，把這種鏈接首先除去，等計(jì)算完以后再加入，這對(duì)原來(lái)計(jì)算出的網(wǎng)頁(yè)的rank值影響是很小的。 Pagerank算法除了對(duì)搜索結(jié)果進(jìn)行排序外，還可以應(yīng)用到其它方面，如估算網(wǎng)絡(luò)流量，向后鏈接的預(yù)測(cè)器，為用戶導(dǎo)航等2。 Google是結(jié)合文本的方法來(lái)實(shí)現(xiàn)PageRank算法的2，所以只返回包含查詢項(xiàng)的網(wǎng)頁(yè)

7、，然后根據(jù)網(wǎng)頁(yè)的rank值對(duì)搜索到的結(jié)果進(jìn)行排序，把rank值最高的網(wǎng)頁(yè)放置到最前面，但是如果最重要的網(wǎng)頁(yè)不在結(jié)果網(wǎng)頁(yè)集中，PageRank算法就無(wú)能為力了，比如在 Google中查詢search engines，像Google，Yahoo，Altivisa等都是很重要的，但是Google返回的結(jié)果中這些網(wǎng)頁(yè)并沒(méi)有出現(xiàn)。 同樣的查詢例子也可以說(shuō)明另外一個(gè)問(wèn)題，Google，Yahoo是WWW上最受歡迎的網(wǎng)頁(yè)，如果出現(xiàn)在查詢項(xiàng)car的結(jié)果集中，一定會(huì)有很多網(wǎng)頁(yè)指向它們，就會(huì)得到較高的rank值， 事實(shí)上他們與car不太相關(guān)。 在PageRank算法的基礎(chǔ)上，其它的研究者提出了改進(jìn)的PageRan

8、k算法。華盛頓大學(xué)計(jì)算機(jī)科學(xué)與工程系的Matthew Richardson和Pedro Dominggos提出了結(jié)合鏈接和內(nèi)容信息的PageRank算法，去除了PageRank算法需要的前提2，增加考慮了用戶從一個(gè)網(wǎng)頁(yè)直接跳轉(zhuǎn)到非直接相鄰的但是內(nèi)容相關(guān)的另外一個(gè)網(wǎng)頁(yè)的情況3。斯坦大學(xué)計(jì)算機(jī)科學(xué)系Taher Haveliwala提出了主題敏感（Topic-sensitive）PageRank算法4。斯坦福大學(xué)計(jì)算機(jī)科學(xué)系A(chǔ)rvind Arasu等經(jīng)過(guò)試驗(yàn)表明，PageRank算法計(jì)算效率還可以得到很大的提高22。 .HITS算法及其變種 PageRank算法中對(duì)于向外鏈接的權(quán)值貢獻(xiàn)是平均的，也就

9、是不考慮不同鏈接的重要性。而WEB的鏈接具有以下特征： 1.有些鏈接具有注釋性，也有些鏈接是起導(dǎo)航或廣告作用。有注釋性的鏈接才用于權(quán)威判斷。 2.基于商業(yè)或競(jìng)爭(zhēng)因素考慮，很少有WEB網(wǎng)頁(yè)指向其競(jìng)爭(zhēng)領(lǐng)域的權(quán)威網(wǎng)頁(yè)。 3.權(quán)威網(wǎng)頁(yè)很少具有顯式的描述，比如Google主頁(yè)不會(huì)明確給出WEB搜索引擎之類的描述信息。 可見(jiàn)平均的分布權(quán)值不符合鏈接的實(shí)際情況17。J. Kleinberg5提出的HITS算法中引入了另外一種網(wǎng)頁(yè)，稱為Hub網(wǎng)頁(yè)，Hub網(wǎng)頁(yè)是提供指向權(quán)威網(wǎng)頁(yè)鏈接集合的WEB網(wǎng)頁(yè)，它本身可能并不重要，或者說(shuō)沒(méi)有幾個(gè)網(wǎng)頁(yè)指向它，但是Hub網(wǎng)頁(yè)確提供了指向就某個(gè)主題而言最為重要的站點(diǎn)的鏈接集合，比

10、一個(gè)課程主頁(yè)上的推薦參考文獻(xiàn)列表。一般來(lái)說(shuō)，好的Hub網(wǎng)頁(yè)指向許多好的權(quán)威網(wǎng)頁(yè)；好的權(quán)威網(wǎng)頁(yè)是有許多好的Hub網(wǎng)頁(yè)指向的WEB網(wǎng)頁(yè)。這種Hub與Authoritive網(wǎng)頁(yè)之間的相互加強(qiáng)關(guān)系，可用于權(quán)威網(wǎng)頁(yè)的發(fā)現(xiàn)和WEB結(jié)構(gòu)和資源的自動(dòng)發(fā)現(xiàn)，這就是Hub/Authority方法的基本思想。 HITS（HyperlinkInduced Topic Search）算法是利用Hub/Authority方法的搜索方法，算法如下：將查詢q提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎搜索引擎返回很多網(wǎng)頁(yè)，從中取前n個(gè)網(wǎng)頁(yè)作為根集(root set)，用S表示。S滿足如下3個(gè)條件： 1S中網(wǎng)頁(yè)數(shù)量相對(duì)較小 2S中網(wǎng)頁(yè)

11、大多數(shù)是與查詢q相關(guān)的網(wǎng)頁(yè) 3S中網(wǎng)頁(yè)包含較多的權(quán)威網(wǎng)頁(yè)。 通過(guò)向S中加入被S引用的網(wǎng)頁(yè)和引用S的網(wǎng)頁(yè)將S擴(kuò)展成一個(gè)更大的集合T 以T中的Hub網(wǎng)頁(yè)為頂點(diǎn)集Vl，以權(quán)威網(wǎng)頁(yè)為頂點(diǎn)集V2，Vl中的網(wǎng)頁(yè)到V2中的網(wǎng)頁(yè)的超鏈接為邊集E，形成一個(gè)二分有向圖SG(V1，V2，E)。對(duì)V1中的任一個(gè)頂點(diǎn)v，用h(v)表示網(wǎng)頁(yè)v的Hub值，對(duì)V2中的頂點(diǎn)u，用a(u)表示網(wǎng)頁(yè)的Authority值。開(kāi)始時(shí)h(v)a(u)1，對(duì)u執(zhí)行I操作修改它的a(u)，對(duì)v執(zhí)行O操作修改它的h(v)，然后規(guī)范化a（u），h（v），如此不斷的重復(fù)計(jì)算下面的操作I，O，直到a（u），h（v）收斂。（證明此算法收斂可見(jiàn)）I 操

12、作： （1） O操作： （2） 每次迭代后需要對(duì)a(u),h(v)進(jìn)行規(guī)范化處理： 式(1)反映了若一個(gè)網(wǎng)頁(yè)由很多好的Hub指向，則其權(quán)威值會(huì)相應(yīng)增加(即權(quán)威值增加為所有指向它的網(wǎng)頁(yè)的現(xiàn)有Hub值之和)。式(2)反映了若一個(gè)網(wǎng)頁(yè)指向許多好的權(quán)威頁(yè)，則Hub值也會(huì)相應(yīng)增加(即Hub值增加為該網(wǎng)頁(yè)鏈接的所有網(wǎng)頁(yè)的權(quán)威值之和)。 和PageRank算法一樣，可以用矩陣形式來(lái)描述算法，這里省略不寫(xiě)。 HITS算法輸出一組具有較大Hub值的網(wǎng)頁(yè)和具有較大權(quán)威值的網(wǎng)頁(yè)。 HITS算法有以下幾個(gè)問(wèn)題： 1實(shí)際應(yīng)用中，由S生成T的時(shí)間開(kāi)銷是很昂貴的，需要下載和分析S中每個(gè)網(wǎng)頁(yè)包含的所有鏈接，并且排除重復(fù)的鏈接

13、。一般T比S大很多，由T生成有向圖也很耗時(shí)。需要分別計(jì)算網(wǎng)頁(yè)的A/H值，計(jì)算量比PageRank算法大。 2有些時(shí)候，一主機(jī)A上的很多文檔可能指向另外一臺(tái)主機(jī)B上的某個(gè)文檔，這就增加了A上文檔的Hub值和B上文檔的Authority，相反的情況也如此。HITS是假定某一文檔的權(quán)威值是由不同的單個(gè)組織或者個(gè)人決定的，上述情況影響了A和B上文檔的Hub和Authority值7。 3網(wǎng)頁(yè)中一些無(wú)關(guān)的鏈接影響A，H值的計(jì)算。在制作網(wǎng)頁(yè)的時(shí)候，有些開(kāi)發(fā)工具會(huì)自動(dòng)的在網(wǎng)頁(yè)上加入一些鏈接，這些鏈接大多是與查詢主題無(wú)關(guān)的。同一個(gè)站點(diǎn)內(nèi)的鏈接目的是為用戶提供導(dǎo)航幫助，也與查詢主題不甚無(wú)關(guān)，還有一些商業(yè)廣告，贊助

14、商和用于友情交換的鏈接，也會(huì)降低HITS算法的精度8。 4HITS算法只計(jì)算主特征向量，也就是只能發(fā)現(xiàn)T集合中的主社區(qū)（Community），忽略了其它重要的社區(qū)12。事實(shí)上，其它社區(qū)可能也非常重要。 5HITS算法最大的弱點(diǎn)是處理不好主題漂移問(wèn)題（topic drift）7,8，也就是緊密鏈接TKC（Tightly-Knit Community Effect）現(xiàn)象8。如果在集合T中有少數(shù)與查詢主題無(wú)關(guān)的網(wǎng)頁(yè)，但是他們是緊密鏈接的，HITS算法的結(jié)果可能就是這些網(wǎng)頁(yè)，因?yàn)镠ITS只能發(fā)現(xiàn)主社區(qū)，從而偏離了原來(lái)的查詢主題。下面討論的SALSA算法中解決了TKC問(wèn)題。 6用HITS進(jìn)行窄主題查詢時(shí)

15、，可能產(chǎn)生主題泛化問(wèn)題5,9，即擴(kuò)展以后引入了比原來(lái)主題更重要的新的主題，新的主題可能與原始查詢無(wú)關(guān)。泛化的原因是因?yàn)榫W(wǎng)頁(yè)中包含不同主題的向外鏈接，而且新主題的鏈接具有更加的重要性。 HITS算法遇到的問(wèn)題，大多是因?yàn)镠ITS是純粹的基于鏈接分析的算法，沒(méi)有考慮文本內(nèi)容，繼J. Kleinberg提出HITS算法以后，很多研究者對(duì)HITS進(jìn)行了改進(jìn)，提出了許多HITS的變種算法，主要有： 對(duì)于上述提到的HITS遇到的第2個(gè)問(wèn)題，Monika R. Henzinger和Krishna Bharat在7中進(jìn)行了改進(jìn)。假定主機(jī)A上有k個(gè)網(wǎng)頁(yè)指向主機(jī)B上的某個(gè)文檔d，則A上的k個(gè)文檔對(duì)B的Author

16、ity貢獻(xiàn)值總共為1,每個(gè)文檔貢獻(xiàn)1/k，而不是HITS中的每個(gè)文檔貢獻(xiàn)1，總共貢獻(xiàn)k。類似的，對(duì)于Hub值，假定主機(jī)A上某個(gè)文檔t指向主機(jī)B上的m個(gè)文檔，則B上m個(gè)文檔對(duì)t的Hub值總共貢獻(xiàn)1，每個(gè)文檔貢獻(xiàn)1/m。I，O操作改為如下I 操作： O操作： 調(diào)整后的算法有效的解決了問(wèn)題2，稱之為imp算法。 在這基礎(chǔ)上，Monika R. Henzinger和Krishna Bharat還引入了傳統(tǒng)信息檢索的內(nèi)容分析技術(shù)來(lái)解決4和5，實(shí)際上也同時(shí)解決了問(wèn)題3。具體方法如下，提取根集S中的每個(gè)文檔的前1000個(gè)詞語(yǔ)，串連起來(lái)作為查詢主題Q，文檔Dj和主題Q的相似度按如下公式計(jì)算：，項(xiàng)i在查詢Q中的

17、出現(xiàn)次數(shù)，項(xiàng)i在文檔Dj中的出現(xiàn)次數(shù)，IDFi是WWW上包含項(xiàng)i的文檔數(shù)目的估計(jì)值。 在S擴(kuò)展到T后，計(jì)算每個(gè)文檔的主題相似度，根據(jù)不同的閾值（threshold）進(jìn)行刷選，可以選擇所有文檔相似度的中值，根集文檔相似度的中值，最大文檔相似度的分?jǐn)?shù)，如1/10，作為閾值。根據(jù)不同閾值進(jìn)行處理，刪除不滿足條件的文檔，再運(yùn)行imp算法計(jì)算文檔的A/H值，這些算法分別稱為med，startmed，maxby10。 在此改進(jìn)的算法中，計(jì)算文檔的相似度時(shí)間開(kāi)銷會(huì)很大。 IBM Almaden研究中心的Clever工程組提出了ARC（Automatic Resource Compilation）算法，對(duì)原始

18、的HITS做了改進(jìn)，賦予網(wǎng)頁(yè)集對(duì)應(yīng)的連結(jié)矩陣初值時(shí)結(jié)合了鏈接的錨（anchor）文本，適應(yīng)了不同的鏈接具有不同的權(quán)值的情況。 ARC算法與HITS的不同主要有以下3點(diǎn)：由根集S擴(kuò)展為T(mén)時(shí)，HITS只擴(kuò)展與根集中網(wǎng)頁(yè)鏈接路徑長(zhǎng)度為1的網(wǎng)頁(yè)，也就是只擴(kuò)展直接與S相鄰的網(wǎng)頁(yè)，而ARC中把擴(kuò)展的鏈接長(zhǎng)度增加到2，擴(kuò)展后的網(wǎng)頁(yè)集稱為增集（Augment Set）。HITS算法中，每個(gè)鏈接對(duì)應(yīng)的矩陣值設(shè)為1，實(shí)際上每個(gè)鏈接的重要性是不同的，ARC算法考慮了鏈接周圍的文本來(lái)確定鏈接的重要性?？紤]鏈接p>q，p中有若干鏈接標(biāo)記，文本1<a href=”q”>錨文本</a>文本2，

19、設(shè)查詢項(xiàng)t在文本1，錨文本，文本2，出現(xiàn)的次數(shù)為n（t），則w（p，q）1+n（t）。文本1和文本2的長(zhǎng)度經(jīng)過(guò)試驗(yàn)設(shè)為50字節(jié)10。構(gòu)造矩陣W，如果有網(wǎng)頁(yè)i>j ，Wi,jw（i，j），否則Wi,j0，H值設(shè)為1，Z為W的轉(zhuǎn)置矩陣，迭代執(zhí)行下面3個(gè)的操作：（1）AWH （2）HZA （3）規(guī)范化A，HARC算法的目標(biāo)是找到前15個(gè)最重要的網(wǎng)頁(yè)，只需要A/H的前15個(gè)值相對(duì)大小保持穩(wěn)定即可，不需要A/H整個(gè)收斂，這樣2中迭代次數(shù)很小就能滿足，10中指出迭代5次就可以，所以ARC算法有很高的計(jì)算效率，開(kāi)銷主要是在擴(kuò)展根集上。 Allan Borodin等在11指出了一種現(xiàn)象，設(shè)有M1個(gè)Hub

20、網(wǎng)頁(yè)，M1個(gè)權(quán)威網(wǎng)頁(yè)，前M個(gè)Hub指向第一個(gè)權(quán)威網(wǎng)頁(yè)，第M1個(gè)Hub網(wǎng)頁(yè)指向了所有M1個(gè)權(quán)威網(wǎng)頁(yè)。顯然根據(jù)HITS算法，第一個(gè)權(quán)威網(wǎng)頁(yè)最重要，有最高的Authority值，這是我們希望的。但是，根據(jù)HITS，第M1個(gè)Hub網(wǎng)頁(yè)有最高的Hub值，事實(shí)上，第M1個(gè)Hub網(wǎng)頁(yè)既指向了權(quán)威值很高的第一個(gè)權(quán)威網(wǎng)頁(yè)，同時(shí)也指向了其它權(quán)威值不高的網(wǎng)頁(yè)，它的Hub值不應(yīng)該比前M個(gè)網(wǎng)頁(yè)的Hub值高。因此，Allan Borodin修改了HITS的O操作：O操作： ，n是(v,u)的個(gè)數(shù) 調(diào)整以后，僅指向權(quán)威值高的網(wǎng)頁(yè)的Hub值比既指向權(quán)威值高又指向權(quán)威值低的網(wǎng)頁(yè)的Hub值高，此算法稱為Hub平均（HubAver

21、agingKleinberg）算法。Kleinberg）算法 Allan Borodin等在11中同時(shí)提出了3種閾值控制的算法，分別是Hub閾值算法，Authority閾值算法，以及結(jié)合2者的全閾值算法。 計(jì)算網(wǎng)頁(yè)p的Authority時(shí)候，不考慮指向它的所有網(wǎng)頁(yè)Hub值對(duì)它的貢獻(xiàn)，只考慮Hub值超過(guò)平均值的網(wǎng)頁(yè)的貢獻(xiàn)，這就是Hub閾值方法。 Authority閾值算法和Hub閾值方法類似，不考慮所有p指向的網(wǎng)頁(yè)的Authority對(duì)p的Hub值貢獻(xiàn)，只計(jì)算前K個(gè)權(quán)威網(wǎng)頁(yè)對(duì)它Hub值的貢獻(xiàn)，這是基于算法的目標(biāo)是查找最重要的K個(gè)權(quán)威網(wǎng)頁(yè)的前提。 同時(shí)使用Authority閾值算法和Hub閾值方法

22、的算法，就是全閾值算法.SALSA算法 PageRank算法是基于用戶隨機(jī)的向前瀏覽網(wǎng)頁(yè)的直覺(jué)知識(shí)，HITS算法考慮的是Authoritive網(wǎng)頁(yè)和Hub網(wǎng)頁(yè)之間的加強(qiáng)關(guān)系。實(shí)際應(yīng)用中，用戶大多數(shù)情況下是向前瀏覽網(wǎng)頁(yè)，但是很多時(shí)候也會(huì)回退瀏覽網(wǎng)頁(yè)?；谏鲜鲋庇X(jué)知識(shí)，R. Lempel和S. Moran提出了SALSA（Stochastic Approach for Link-Structure Analysis）算法8，考慮了用戶回退瀏覽網(wǎng)頁(yè)的情況，保留了PageRank的隨機(jī)漫游和HITS中把網(wǎng)頁(yè)分為Authoritive和Hub的思想，取消了Authoritive和Hub之間的相互加強(qiáng)關(guān)系

23、。 具體算法如下：和HITS算法的第一步一樣，得到根集并且擴(kuò)展為網(wǎng)頁(yè)集合T，并除去孤立節(jié)點(diǎn)。從集合T構(gòu)造無(wú)向圖G（Vh，Va，E）Vh = sh | sC and out-degree(s) > 0 ( G的Hub邊).Va = sa | sC and in-degree(s) > 0 (G的Authority邊).E= (sh , ra) |s>r in T這就定義了2條鏈，Authority鏈和Hub鏈。定義2條馬爾可夫鏈的變化矩陣，也是隨機(jī)矩陣，分別是Hub矩陣H，Authority矩陣A。 求出矩陣H，A的主特征向量，就是對(duì)應(yīng)的馬爾可夫鏈的靜態(tài)分布。A中值大的對(duì)應(yīng)的網(wǎng)

24、頁(yè)就是所要找的重要網(wǎng)頁(yè)。SALSA算法沒(méi)有HITS中相互加強(qiáng)的迭代過(guò)程，計(jì)算量遠(yuǎn)小于HITS。SALSA算法只考慮直接相鄰的網(wǎng)頁(yè)對(duì)自身A/H的影響，而HITS是計(jì)算整個(gè)網(wǎng)頁(yè)集合T對(duì)自身AH的影響。 實(shí)際應(yīng)用中，SALSA在擴(kuò)展根集時(shí)忽略了很多無(wú)關(guān)的鏈接，比如同一站點(diǎn)內(nèi)的鏈接，因?yàn)檫@些鏈接大多只起導(dǎo)航作用。CGI 腳本鏈接。廣告和贊助商鏈接。 試驗(yàn)結(jié)果表明，對(duì)于單主題查詢java，SALSA有比HITS更精確的結(jié)果，對(duì)于多主題查詢abortion，HITS的結(jié)果集中于主題的某個(gè)方面，而SALSA算法的結(jié)果覆蓋了多個(gè)方面，也就是說(shuō)，對(duì)于TKC現(xiàn)象，SALSA算法比HITS算法有更高的健壯性。 SA

25、LSA算法計(jì)算網(wǎng)頁(yè)的Authority值時(shí)，只考慮網(wǎng)頁(yè)在直接相鄰網(wǎng)頁(yè)集中的受歡迎程度，忽略其它網(wǎng)頁(yè)對(duì)它的影響。HITS算法考慮的是整個(gè)圖的結(jié)構(gòu)，特別的，經(jīng)過(guò)n步以后，網(wǎng)頁(yè)i的Authority的權(quán)重是，為離開(kāi)網(wǎng)頁(yè)i的的路徑的數(shù)目，也就是說(shuō)網(wǎng)頁(yè)j<>i，對(duì)i的權(quán)值貢獻(xiàn)等于從i到j(luò)的路徑的數(shù)量。如果從i到j(luò)包含有一個(gè)回路，那么j對(duì)i的貢獻(xiàn)將會(huì)呈指數(shù)級(jí)增加，這并不是算法所希望的，因?yàn)榛芈房赡懿皇桥c查詢相關(guān)的。 因此，Allan Borodin等11提出了BFS（Backward Forward Step）算法，既是SALSA的擴(kuò)展情況，也是HITS的限制情況。基本思想是，SALSA只考慮

26、直接相鄰網(wǎng)頁(yè)的影響，BFS擴(kuò)展到考慮路徑長(zhǎng)度為n的相鄰網(wǎng)頁(yè)的影響。在BFS中，被指定表示能通過(guò)路徑到達(dá)i的結(jié)點(diǎn)的集合，這樣j對(duì)i的貢獻(xiàn)依賴就與j到i的距離。BFS采用指數(shù)級(jí)降低權(quán)值的方式，結(jié)點(diǎn)i的權(quán)值計(jì)算公式如下：|B(i)|+ |BF(i)| +|BFB(i)|+| 算法從結(jié)點(diǎn)i開(kāi)始，第一步向后訪問(wèn)，然后繼續(xù)向前或者向后訪問(wèn)鄰居，每一步遇到新的結(jié)點(diǎn)加入權(quán)值計(jì)算，結(jié)點(diǎn)只有在第一次被訪問(wèn)時(shí)加入進(jìn)去計(jì)算。 .PHITS D.Cohn and H.Chang提出了計(jì)算Hub和Authority的統(tǒng)計(jì)算法PHITS（Probabilistic analogue of the HITS）12。他們提出了

27、一個(gè)概率模型，在這個(gè)模型里面一個(gè)潛在的因子或者主題z影響了文檔d到文檔c的一個(gè)鏈接，他們進(jìn)一步假定，給定因子z，文檔c的條件分布P(c|z)存在，并且給定文檔d，因子z的條件分布P（z|d）也存在。 P(d) P(z|d) P(c|z) ，其中 根據(jù)這些條件分布，提出了一個(gè)可能性函數(shù)（likelihood function）L,，M是對(duì)應(yīng)的連結(jié)矩陣 然后，PHITS算法使用Dempster等提出的EM算法20分配未知的條件概率使得L最大化，也就是最好的解釋了網(wǎng)頁(yè)之間的鏈接關(guān)系。算法要求因子z的數(shù)目事先給定。Allan Borodin指出，PHITS中使用的EM算法可能會(huì)收斂于局部的最大化，而不

28、是真正的全局最大化11。D. Cohn和T. Hofmann還提出了結(jié)合文檔內(nèi)容和超鏈接的概率模型13。 .貝葉斯算法 Allan Borodin等提出了完全的貝葉斯統(tǒng)計(jì)方法來(lái)確定Hub和Authoritive網(wǎng)頁(yè)11。假定有M個(gè)Hub網(wǎng)頁(yè)和N個(gè)Authority網(wǎng)頁(yè)，可以是相同的集合。每個(gè)Hub網(wǎng)頁(yè)有一個(gè)未知的實(shí)數(shù)參數(shù)，表示擁有超鏈的一般趨勢(shì)，一個(gè)未知的非負(fù)參數(shù)，表示擁有指向Authority網(wǎng)頁(yè)的鏈接的趨勢(shì)。每個(gè)Authoritive網(wǎng)頁(yè)j，有一個(gè)未知的非負(fù)參數(shù)，表示j的Authority的級(jí)別。 統(tǒng)計(jì)模型如下，Hub網(wǎng)頁(yè)i到Authority網(wǎng)頁(yè)j的鏈接的先驗(yàn)概率如下給定： P（i，j）

29、Exp（）/（1Exp（） Hub網(wǎng)頁(yè)i到Authority網(wǎng)頁(yè)j沒(méi)有鏈接時(shí)，P（i，j）1/（1Exp（） 從以上公式可以看出，如果很大（表示Hub網(wǎng)頁(yè)i有很高的趨勢(shì)指向任何一個(gè)網(wǎng)頁(yè)），或者和都很大（表示i是個(gè)高質(zhì)量Hub，j是個(gè)高質(zhì)量的Authority網(wǎng)頁(yè)），那么i>j的鏈接的概率就比較大。為了符合貝葉斯統(tǒng)計(jì)模型的規(guī)范，要給2MN個(gè)未知參數(shù)（，）指定先驗(yàn)分布，這些分布應(yīng)該是一般化的，不提供信息的，不依賴于被觀察數(shù)據(jù)的，對(duì)結(jié)果只能產(chǎn)生很小影響的。Allan Borodin等在中指定滿足正太分布N（，）,均值0，標(biāo)準(zhǔn)方差10，指定和滿足Exp（1）分布，即x>=0，P(>=

30、x)P(>=x)Exp（x）。 接下來(lái)就是標(biāo)準(zhǔn)的貝葉斯方法處理和HITS中求矩陣特征根的運(yùn)算。 Allan Borodin同時(shí)提出了簡(jiǎn)化的上述貝葉斯算法，完全除去了參數(shù)，也就不再需要正太分布的參數(shù)，了。計(jì)算公式變?yōu)椋篜（i，j）/（1），Hub網(wǎng)頁(yè)到Authority網(wǎng)頁(yè)j沒(méi)有鏈接時(shí)，P（i，j）1/(1)。 Allan Borodin 指出簡(jiǎn)化的貝葉斯產(chǎn)生的效果與SALSA算法的結(jié)果非常類似。 .Reputation 上面的所有算法，都是從查詢項(xiàng)或者主題出發(fā)，經(jīng)過(guò)算法處理，得到結(jié)果網(wǎng)頁(yè)。多倫多大學(xué)計(jì)算機(jī)系A(chǔ)lberto Mendelzon, Davood Rafiei提出了一種反向的算

31、法，輸入為某個(gè)網(wǎng)頁(yè)的URL地址，輸出為一組主題，網(wǎng)頁(yè)在這些主題上有聲望（repution）16“java” 給定一個(gè)網(wǎng)頁(yè)p，計(jì)算在主題t上的聲望，首先定義2個(gè)參數(shù)，滲透率和聚焦率，簡(jiǎn)單起見(jiàn)，網(wǎng)頁(yè)p包含主題項(xiàng)t，就認(rèn)為p在主題t上。 是指向p而且包含t的網(wǎng)頁(yè)數(shù)目，是指向p的網(wǎng)頁(yè)數(shù)目，是包含t的網(wǎng)頁(yè)數(shù)目。結(jié)合非條件概率，引入，是WEB上網(wǎng)頁(yè)的數(shù)目。P在t上的聲望計(jì)算如下： 指定是既指向p有包含t的概率，即，顯然有 我們可以從搜索引擎（如Altavista）的結(jié)果得到，, ,WEB上網(wǎng)頁(yè)的總數(shù)估計(jì)值某些組織會(huì)經(jīng)常公布，在計(jì)算中是個(gè)常量不影響RM的排序，RM最后如此計(jì)算： 給定網(wǎng)頁(yè)p和主題t，RM可以

32、如上計(jì)算，但是多數(shù)的情況的只給定網(wǎng)頁(yè)p，需要提取主題后計(jì)算。算法的目標(biāo)是找到一組t，使得RM（p，t）有較大的值。TOPIC系統(tǒng)中是抽取指向p的網(wǎng)頁(yè)中的錨文本的單詞作為主題（上面已經(jīng)討論過(guò)錨文本能很好描述目標(biāo)網(wǎng)頁(yè)，精度很高），避免了下載所有指向p的網(wǎng)頁(yè)，而且RM（p，t）的計(jì)算很簡(jiǎn)單，算法的效率較高。主題抽取時(shí)，還忽略了用于導(dǎo)航、重復(fù)的鏈接的文本，同時(shí)也過(guò)濾了停止字（stop word），如“a”，“the”，“for”，“in”等。 Reputation算法也是基于隨機(jī)漫游模型的（random walk），可以說(shuō)是PageRank和SALSA算法的結(jié)合體。 .鏈接算法的分類及其評(píng)價(jià) 鏈接分析算法可以用來(lái)提高搜索引擎的查詢效果，可以發(fā)現(xiàn)WWW上的重要的社區(qū)，可以分析某個(gè)網(wǎng)站的拓?fù)浣Y(jié)構(gòu)，聲望，分類等，可以用來(lái)實(shí)現(xiàn)文檔的自動(dòng)分類等。歸根結(jié)底，能夠幫助用戶在WWW海量的信息里面準(zhǔn)確找到需要的信息。這是一個(gè)正在迅速發(fā)展的研究領(lǐng)域。 上面我們從歷史的角度總結(jié)了鏈接分析算法的發(fā)展歷程，較為詳細(xì)的介紹了算法的基