關(guān)于搜索引擎的6大超鏈接分析算法研究

時(shí)間：2022-05-29 01:39:01 | 來(lái)源：網(wǎng)絡(luò)營(yíng)銷(xiāo)

時(shí)間：2022-05-29 01:39:01 來(lái)源：網(wǎng)絡(luò)營(yíng)銷(xiāo)

萬(wàn)維網(wǎng)WWW（World Wide Web）是一個(gè)巨大的，分布全球的信息服務(wù)中心，正在以飛快的速度擴(kuò)展。據(jù)億企邦了解在1998年WWW上就已經(jīng)擁有約3.5億個(gè)文檔，每天增加約1百萬(wàn)的文檔，不到9個(gè)月的時(shí)間文檔總數(shù)就會(huì)翻一番。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é)果是包含查詢(xún)項(xiàng)的文檔，也有基于目錄分類(lèi)的搜索引擎，這些搜索引擎的結(jié)果并不令人滿(mǎn)意。有些站點(diǎn)有意提高關(guān)鍵字出現(xiàn)的頻率來(lái)提高自身在搜索引擎中的重要性，破壞搜索引擎結(jié)果的客觀性和準(zhǔn)確性。

另外，有些重要的網(wǎng)頁(yè)并不包含查詢(xún)項(xiàng)。搜索引擎的分類(lèi)目錄也不可能把所有的分類(lèi)考慮全面，并且目錄大多靠人工維護(hù)，主觀性強(qiáng)，費(fèi)用高，更新速度慢。

許多研究者發(fā)現(xiàn)，WWW上超鏈結(jié)構(gòu)是個(gè)非常豐富和重要的資源，如果能夠充分利用的話(huà)，可以極大的提高檢索結(jié)果的質(zhì)量。

基于這種超鏈分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法，同年J. Kleinberg提出了HITS算法，其它一些學(xué)者也相繼提出了另外的鏈接分析算法，如SALSA，PHITS，Bayesian等算法。這些算法有的已經(jīng)在實(shí)際的系統(tǒng)中實(shí)現(xiàn)和使用，并且取得了良好的效果。在此，億企邦就按照時(shí)間順序詳細(xì)的為大家剖析一下各種鏈接分析算法：

一、WEB超鏈分析算法

對(duì)于WEB超鏈分析算法，億企邦就從PageRank算法、HITS算法、SALSA算法、PHITS算法、貝葉斯算法和Reputation算法來(lái)為大家解說(shuō)一下：

1、Google和PageRank算法

搜索引擎Google最初是斯坦福大學(xué)的博士研究生Sergey Brin和Lawrence Page實(shí)現(xiàn)的一個(gè)原型系統(tǒng)，現(xiàn)在已經(jīng)發(fā)展成為WWW上最好的搜索引擎之一。Google的體系結(jié)構(gòu)類(lèi)似于傳統(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值（具體可查看億企邦的《pr值是什么》相關(guān)介紹），從而決定網(wǎng)頁(yè)在結(jié)果集中的出現(xiàn)位置，PageRank值越高的網(wǎng)頁(yè)，在結(jié)果中出現(xiàn)的位置越前。

（1）、PageRank算法

據(jù)億企邦了解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è)稱(chēng)為權(quán)威（Authoritive）網(wǎng)頁(yè)。

前提2：假定用戶(hù)一開(kāi)始隨機(jī)的訪(fǎng)問(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ù)，顯然 =|| ，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ì)。如下圖所示：

為了解決這個(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è)器，為用戶(hù)導(dǎo)航等（具體可查看億企邦的《pr的計(jì)算公式及影響因素》詳細(xì)介紹）。

（2）、算法的一些問(wèn)題

Google是結(jié)合文本的方法來(lái)實(shí)現(xiàn)PageRank算法的，所以只返回包含查詢(xún)項(xiàng)的網(wǎng)頁(yè)，然后根據(jù)網(wǎng)頁(yè)的rank值對(duì)搜索到的結(jié)果進(jìn)行排序，把rank值最高的網(wǎng)頁(yè)放置到最前面，但是如果最重要的網(wǎng)頁(yè)不在結(jié)果網(wǎng)頁(yè)集中，PageRank算法就無(wú)能為力了，比如在Google中查詢(xún)search engines，像Google，Yahoo，Altivisa等都是很重要的，但是Google返回的結(jié)果中這些網(wǎng)頁(yè)并沒(méi)有出現(xiàn)。

同樣的查詢(xún)例子也可以說(shuō)明另外一個(gè)問(wèn)題，Google和Yahoo都是WWW上最受歡迎的網(wǎng)頁(yè)，如果出現(xiàn)在查詢(xún)項(xiàng)car的結(jié)果集中，一定會(huì)有很多網(wǎng)頁(yè)指向它們，就會(huì)得到較高的rank值，事實(shí)上他們與car不太相關(guān)。

在PageRank算法的基礎(chǔ)上，其它的研究者提出了改進(jìn)的PageRank算法。華盛頓大學(xué)計(jì)算機(jī)科學(xué)與工程系的Matthew Richardson和Pedro Dominggos提出了結(jié)合鏈接和內(nèi)容信息的PageRank算法，去除了PageRank算法需要的前提2，增加考慮了用戶(hù)從一個(gè)網(wǎng)頁(yè)直接跳轉(zhuǎn)到非直接相鄰的但是內(nèi)容相關(guān)的另外一個(gè)網(wǎng)頁(yè)的情況。

斯坦大學(xué)計(jì)算機(jī)科學(xué)系Taher Haveliwala提出了主題敏感（Topic-sensitive）PageRank算法。斯坦福大學(xué)計(jì)算機(jī)科學(xué)系A(chǔ)rvind Arasu等經(jīng)過(guò)試驗(yàn)表明，PageRank算法計(jì)算效率還可以得到很大的提高。

2、HITS算法及其變種

PageRank算法中對(duì)于向外鏈接的權(quán)值貢獻(xiàn)是平均的，也就是不考慮不同鏈接的重要性。而WEB的鏈接具有以下特征：

①、有些鏈接具有注釋性，也有些鏈接是起導(dǎo)航或廣告作用，有注釋性的鏈接才用于權(quán)威判斷。

②、基于商業(yè)或競(jìng)爭(zhēng)因素考慮，很少有WEB網(wǎng)頁(yè)指向其競(jìng)爭(zhēng)領(lǐng)域的權(quán)威網(wǎng)頁(yè)。

③、權(quán)威網(wǎng)頁(yè)很少具有顯式的描述，比如Google主頁(yè)不會(huì)明確給出WEB搜索引擎之類(lèi)的描述信息。

可見(jiàn)平均的分布權(quán)值不符合鏈接的實(shí)際情況，J. Kleinberg提出的HITS算法中引入了另外一種網(wǎng)頁(yè)，稱(chēng)為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)的鏈接集合，比一個(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方法的基本思想。

（1）、HITS算法

HITS（Hyperlink－Induced Topic Search）算法是利用Hub/Authority方法的搜索方法，算法如下：將查詢(xún)q提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎．搜索引擎返回很多網(wǎng)頁(yè)，從中取前n個(gè)網(wǎng)頁(yè)作為根集(root set)，用S表示。S滿(mǎn)足如下3個(gè)條件：

①、S中網(wǎng)頁(yè)數(shù)量相對(duì)較小。

②、S中網(wǎng)頁(yè)大多數(shù)是與查詢(xún)q相關(guān)的網(wǎng)頁(yè)。

③、S中網(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操作：

O操作：

每次迭代后需要對(duì)a(u)，h(v)進(jìn)行規(guī)范化處理：



I操作反映了若一個(gè)網(wǎng)頁(yè)由很多好的Hub指向，則其權(quán)威值會(huì)相應(yīng)增加(即權(quán)威值增加為所有指向它的網(wǎng)頁(yè)的現(xiàn)有Hub值之和)。

O操作反映了若一個(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è)。

（2）、HITS算法的問(wèn)題

據(jù)億企邦了解，HITS算法有以下幾個(gè)問(wèn)題：

①、實(shí)際應(yīng)用中，由S生成T的時(shí)間開(kāi)銷(xiāo)是很昂貴的，需要下載和分析S中每個(gè)網(wǎng)頁(yè)包含的所有鏈接，并且排除重復(fù)的鏈接。一般T比S大很多，由T生成有向圖也很耗時(shí)。需要分別計(jì)算網(wǎng)頁(yè)的A/H值，計(jì)算量比PageRank算法大。

②、有些時(shí)候，一主機(jī)A上的很多文檔可能指向另外一臺(tái)主機(jī)B上的某個(gè)文檔，這就增加了A上文檔的Hub值和B上文檔的Authority，相反的情況也如此。

HITS是假定某一文檔的權(quán)威值是由不同的單個(gè)組織或者個(gè)人決定的，上述情況影響了A和B上文檔的Hub和Authority值。

③、網(wǎng)頁(yè)中一些無(wú)關(guān)的鏈接影響A，H值的計(jì)算。在制作網(wǎng)頁(yè)的時(shí)候，有些開(kāi)發(fā)工具會(huì)自動(dòng)的在網(wǎng)頁(yè)上加入一些鏈接，這些鏈接大多是與查詢(xún)主題無(wú)關(guān)的（具體可查看億企邦的《基于結(jié)構(gòu)化數(shù)據(jù)的豐富網(wǎng)頁(yè)摘要研究》相關(guān)介紹）。同一個(gè)站點(diǎn)內(nèi)的鏈接目的是為用戶(hù)提供導(dǎo)航幫助，也與查詢(xún)主題不甚無(wú)關(guān)，還有一些商業(yè)廣告，贊助商和用于友情交換的鏈接，也會(huì)降低HITS算法的精度。

④、HITS算法只計(jì)算主特征向量，也就是只能發(fā)現(xiàn)T集合中的主社區(qū)（Community），忽略了其它重要的社區(qū)。事實(shí)上，其它社區(qū)可能也非常重要。

⑤、HITS算法最大的弱點(diǎn)是處理不好主題漂移問(wèn)題（topic drift），也就是緊密鏈接TKC（Tightly-Knit Community Effect）現(xiàn)象。如果在集合T中有少數(shù)與查詢(xún)主題無(wú)關(guān)的網(wǎng)頁(yè)，但是他們是緊密鏈接的，HITS算法的結(jié)果可能就是這些網(wǎng)頁(yè)，因?yàn)镠ITS只能發(fā)現(xiàn)主社區(qū)，從而偏離了原來(lái)的查詢(xún)主題。

⑥、用HITS進(jìn)行窄主題查詢(xún)時(shí)，可能產(chǎn)生主題泛化問(wèn)題，即擴(kuò)展以后引入了比原來(lái)主題更重要的新的主題，新的主題可能與原始查詢(xún)無(wú)關(guān)。泛化的原因是因?yàn)榫W(wǎng)頁(yè)中包含不同主題的向外鏈接，而且新主題的鏈接具有更加的重要性。

（3）、HITS的變種

HITS算法遇到的問(wèn)題，大多是因?yàn)镠ITS是純粹的基于鏈接分析的算法，沒(méi)有考慮文本內(nèi)容，繼J. Kleinberg提出HITS算法以后，很多研究者對(duì)HITS進(jìn)行了改進(jìn)，提出了許多HITS的變種算法，主要有：

①、Monika R. Henzinger和Krishna Bharat對(duì)HITS的改進(jìn)

對(duì)于上述提到的HITS遇到的第2個(gè)問(wèn)題，Monika R. Henzinger和Krishna Bharat在中進(jìn)行了改進(jìn)。假定主機(jī)A上有k個(gè)網(wǎng)頁(yè)指向主機(jī)B上的某個(gè)文檔d，則A上的k個(gè)文檔對(duì)B的Authority貢獻(xiàn)值總共為1，每個(gè)文檔貢獻(xiàn)1/k，而不是HITS中的每個(gè)文檔貢獻(xiàn)1，總共貢獻(xiàn)k。類(lèi)似的，對(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，稱(chēng)之為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)作為查詢(xún)主題Q，文檔Dj和主題Q的相似度按如下公式計(jì)算：

，，＝項(xiàng)i在查詢(xún)Q中的出現(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)行處理，刪除不滿(mǎn)足條件的文檔，再運(yùn)行imp算法計(jì)算文檔的A/H值，這些算法分別稱(chēng)為med，startmed，maxby10。

據(jù)億企邦了解在此改進(jìn)的算法中，計(jì)算文檔的相似度時(shí)間開(kāi)銷(xiāo)會(huì)很大。

②、ARC算法

IBM Almaden研究中心的Clever工程組提出了ARC（Automatic Resource Compilation）算法，對(duì)原始的HITS做了改進(jìn)，賦予網(wǎng)頁(yè)集對(duì)應(yīng)的連結(jié)矩陣初值時(shí)結(jié)合了鏈接的錨（anchor）文本，適應(yīng)了不同的鏈接具有不同的權(quán)值的情況。

ARC算法與HITS的不同主要有以下3點(diǎn)：

a、由根集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è)集稱(chēng)為增集（Augment Set）。

b、HITS算法中，每個(gè)鏈接對(duì)應(yīng)的矩陣值設(shè)為1，實(shí)際上每個(gè)鏈接的重要性是不同的，ARC算法考慮了鏈接周?chē)奈谋緛?lái)確定鏈接的重要性?？紤]鏈接p－>q，p中有若干鏈接標(biāo)記，文本1<a href=”q”>錨文本</a>文本2，設(shè)查詢(xún)項(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é)。構(gòu)造矩陣W，如果有網(wǎng)頁(yè)i－>j ，Wi,j＝w（i，j），否則Wi,j＝0，H值設(shè)為1，Z為W的轉(zhuǎn)置矩陣，迭代執(zhí)行下面3個(gè)的操作：

A＝WH

H＝ZA

規(guī)范化A，H

c、ARC算法的目標(biāo)是找到前15個(gè)最重要的網(wǎng)頁(yè)，只需要A/H的前15個(gè)值相對(duì)大小保持穩(wěn)定即可，不需要A/H整個(gè)收斂，這樣2中迭代次數(shù)很小就能滿(mǎn)足，中指出迭代5次就可以，所以ARC算法有很高的計(jì)算效率，開(kāi)銷(xiāo)主要是在擴(kuò)展根集上。

③、Hub平均（Hub－Averaging－Kleinberg）算法

Allan Borodin等在指出了一種現(xiàn)象，設(shè)有M＋1個(gè)Hub網(wǎng)頁(yè)，M＋1個(gè)權(quán)威網(wǎng)頁(yè)，前M個(gè)Hub指向第一個(gè)權(quán)威網(wǎng)頁(yè)，第M＋1個(gè)Hub網(wǎng)頁(yè)指向了所有M＋1個(gè)權(quán)威網(wǎng)頁(yè)。顯然根據(jù)HITS算法，第一個(gè)權(quán)威網(wǎng)頁(yè)最重要，有最高的Authority值，這是我們希望的。

但是，根據(jù)HITS，第M＋1個(gè)Hub網(wǎng)頁(yè)有最高的Hub值，事實(shí)上，第M＋1個(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值高，此算法稱(chēng)為Hub平均（Hub－Averaging－Kleinberg）算法。

④、閾值（Threshhold—Kleinberg）算法

Allan Borodin等在中同時(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閾值方法類(lèi)似，不考慮所有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閾值方法的算法，就是全閾值算法。

3、SALSA算法

PageRank算法是基于用戶(hù)隨機(jī)的向前瀏覽網(wǎng)頁(yè)的直覺(jué)知識(shí)，HITS算法考慮的是Authoritive網(wǎng)頁(yè)和Hub網(wǎng)頁(yè)之間的加強(qiáng)關(guān)系。

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

據(jù)億企邦了解，其具體算法如下：

①、和HITS算法的第一步一樣，得到根集并且擴(kuò)展為網(wǎng)頁(yè)集合T，并除去孤立節(jié)點(diǎn)。

②、從集合T構(gòu)造無(wú)向圖G’＝（Vh，Va，E）

Vh = {sh |s∈C and out-degree(s) > 0 } ( G’的Hub邊)

Va = {sa |s∈C 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)頁(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 腳本鏈接。

③、廣告和贊助商鏈接。

據(jù)億企邦的試驗(yàn)結(jié)果表明，對(duì)于單主題查詢(xún)java，SALSA有比HITS更精確的結(jié)果，對(duì)于多主題查詢(xún)abortion，HITS的結(jié)果集中于主題的某個(gè)方面，而SALSA算法的結(jié)果覆蓋了多個(gè)方面，也就是說(shuō)，對(duì)于TKC現(xiàn)象，SALSA算法比HITS算法有更高的健壯性。

BFS（Backword Forward Step）算法

SALSA算法計(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查詢(xún)相關(guān)的。

因此，Allan Borodin等提出了BFS（Backward Forward Step）算法，既是SALSA的擴(kuò)展情況，也是HITS的限制情況?；舅枷胧牵琒ALSA只考慮直接相鄰網(wǎng)頁(yè)的影響，BFS擴(kuò)展到考慮路徑長(zhǎng)度為n的相鄰網(wǎng)頁(yè)的影響。

在BFS中，被指定表示能通過(guò)路徑到達(dá)i的結(jié)點(diǎn)的集合，這樣j對(duì)i的貢獻(xiàn)依賴(lài)就與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)始，第一步向后訪(fǎng)問(wèn)，然后繼續(xù)向前或者向后訪(fǎng)問(wèn)鄰居，每一步遇到新的結(jié)點(diǎn)加入權(quán)值計(jì)算，結(jié)點(diǎn)只有在第一次被訪(fǎng)問(wèn)時(shí)加入進(jìn)去計(jì)算。

4、PHITS算法

D.　Cohn and H.　Chang提出了計(jì)算Hub和Authority的統(tǒng)計(jì)算法PHITS（Probabilistic analogue of the HITS）。他們提出了一個(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算法分配未知的條件概率使得L最大化，也就是最好的解釋了網(wǎng)頁(yè)之間的鏈接關(guān)系。算法要求因子z的數(shù)目事先給定。Allan Borodin指出，PHITS中使用的EM算法可能會(huì)收斂于局部的最大化，而不是真正的全局最大化。D. Cohn和T. Hofmann還提出了結(jié)合文檔內(nèi)容和超鏈接的概率模型。

5、貝葉斯算法

Allan Borodin等提出了完全的貝葉斯統(tǒng)計(jì)方法來(lái)確定Hub和Authoritive網(wǎng)頁(yè)。假定有M個(gè)Hub網(wǎng)頁(yè)和N個(gè)Authority網(wǎng)頁(yè)（之前我也曾在億企邦上的《基于貝葉斯推斷應(yīng)用原理的過(guò)濾垃圾郵件研究》一文中跟大家介紹過(guò)），可以是相同的集合。每個(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）＝Exp（＋）/（1＋Exp（＋））

Hub網(wǎng)頁(yè)i到Authority網(wǎng)頁(yè)j沒(méi)有鏈接時(shí)，P（i，j）＝1/（1＋Exp（＋））

從以上公式可以看出，如果很大（表示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ī)范，要給2M＋N個(gè)未知參數(shù)（，，）指定先驗(yàn)分布，這些分布應(yīng)該是一般化的，不提供信息的，不依賴(lài)于被觀察數(shù)據(jù)的，對(duì)結(jié)果只能產(chǎn)生很小影響的。Allan Borodin等在中指定滿(mǎn)足正太分布N（μ，）,均值μ＝0，標(biāo)準(zhǔn)方差δ＝10，指定和滿(mǎn)足Exp（1）分布，即x>=0，P(>=x)＝P(>=x)＝Exp（－x）。

接下來(lái)就是標(biāo)準(zhǔn)的貝葉斯方法處理和HITS中求矩陣特征根的運(yùn)算。

簡(jiǎ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é)果非常類(lèi)似。

6、Reputation算法

上面的所有算法，都是從查詢(xún)項(xiàng)或者主題出發(fā)，經(jīng)過(guò)算法處理，得到結(jié)果網(wǎng)頁(yè)。多倫多大學(xué)計(jì)算機(jī)系A(chǔ)lberto Mendelzon，Davood Rafiei提出了一種反向的算法，輸入為某個(gè)網(wǎng)頁(yè)的URL地址，輸出為一組主題，網(wǎng)頁(yè)在這些主題上有聲望（repution）。比如輸入，www.mahaixiang.cn，可能的輸出結(jié)果是“java”，具體的系統(tǒng)我會(huì)在億企邦上為大家再做介紹，在此，就先不細(xì)說(shuō)了。

給定一個(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可以如上計(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é)合體。

二、鏈接算法的分類(lèi)及其評(píng)價(jià)

鏈接分析算法可以用來(lái)提高搜索引擎的查詢(xún)效果，可以發(fā)現(xiàn)WWW上的重要的社區(qū)，可以分析某個(gè)網(wǎng)站的拓?fù)浣Y(jié)構(gòu)，聲望，分類(lèi)等，可以用來(lái)實(shí)現(xiàn)文檔的自動(dòng)分類(lèi)等。歸根結(jié)底，能夠幫助用戶(hù)在WWW海量的信息里面準(zhǔn)確找到需要的信息，億企邦覺(jué)得這是搜索引擎正在迅速發(fā)展的研究領(lǐng)域。

上面我們從歷史的角度總結(jié)了鏈接分析算法的發(fā)展歷程，較為詳細(xì)的介紹了算法的基本思想和具體實(shí)現(xiàn)，對(duì)算法的存在的問(wèn)題也做了討論。這些算法有的處于研究階段，有的已經(jīng)在具體的系統(tǒng)實(shí)現(xiàn)了。

在此，億企邦將這些算法大體分為以下幾類(lèi)：

①、基于隨機(jī)漫游模型的，比如PageRank，Repution算法。

②、基于Hub和Authority相互加強(qiáng)模型的，如HITS及其變種。

③、基于概率模型的，如SALSA，PHITS。

④、基于貝葉斯模型的，如貝葉斯算法及其簡(jiǎn)化版本。

所有的算法在實(shí)際應(yīng)用中都結(jié)合傳統(tǒng)的內(nèi)容分析技術(shù)進(jìn)行了優(yōu)化。

一些實(shí)際的系統(tǒng)實(shí)現(xiàn)了某些算法，并且獲得了很好的效果，Google實(shí)現(xiàn)了PageRank算法，IBM Almaden Research Center 的Clever Project實(shí)現(xiàn)了ARC算法，多倫多大學(xué)計(jì)算機(jī)系實(shí)現(xiàn)了一個(gè)原型系統(tǒng)TOPIC，來(lái)計(jì)算指定網(wǎng)頁(yè)有聲望的主題。

AT&T香農(nóng)實(shí)驗(yàn)室的Brian Amento在指出，用權(quán)威性來(lái)評(píng)價(jià)網(wǎng)頁(yè)的質(zhì)量和人類(lèi)專(zhuān)家評(píng)價(jià)的結(jié)果是一致的，并且各種鏈接分析算法的結(jié)果在大多數(shù)的情況下差別很小。但是，Allan Borodin也指出沒(méi)有一種算法是完美的，在某些查詢(xún)下，結(jié)果可能很好，在另外的查詢(xún)下，結(jié)果可能很差。所以應(yīng)該根據(jù)不同查詢(xún)的情況，選擇不同的合適的算法。

基于鏈接分析的算法，提供了一種衡量網(wǎng)頁(yè)質(zhì)量的客觀方法，獨(dú)立于語(yǔ)言，獨(dú)立于內(nèi)容，不需人工干預(yù)就能自動(dòng)發(fā)現(xiàn)WEB上重要的資源，挖掘出WEB上重要的社區(qū)，自動(dòng)實(shí)現(xiàn)文檔分類(lèi)。但是也有一些共同的問(wèn)題影響著算法的精度，具體分為以下幾個(gè)原因：

1、根集的質(zhì)量

根集質(zhì)量應(yīng)該是很高的，否則，擴(kuò)展后的網(wǎng)頁(yè)集會(huì)增加很多無(wú)關(guān)的網(wǎng)頁(yè)，產(chǎn)生主題漂移，主題泛化等一系列的問(wèn)題，計(jì)算量也增加很多。

算法再好，也無(wú)法在低質(zhì)量網(wǎng)頁(yè)集找出很多高質(zhì)量的網(wǎng)頁(yè)。

2、噪音鏈接

WEB上不是每個(gè)鏈接都包含了有用的信息，比如廣告，站點(diǎn)導(dǎo)航，贊助商，用于友情交換的鏈接，對(duì)于鏈接分析不僅沒(méi)有幫助，而且還影響結(jié)果。如何有效的去除這些無(wú)關(guān)鏈接，做個(gè)高質(zhì)量鏈接也是算法的一個(gè)關(guān)鍵點(diǎn)（具體可查看億企邦的《如何做好網(wǎng)站的高質(zhì)量鏈接》相關(guān)介紹）。

3、錨文本的利用

錨文本有很高的精度，對(duì)鏈接和目標(biāo)網(wǎng)頁(yè)的描述比較精確，上述算法在具體的實(shí)現(xiàn)中利用了錨文本來(lái)優(yōu)化算法。如何準(zhǔn)確充分的利用錨文本，對(duì)算法的精度影響很大。

4、查詢(xún)的分類(lèi)

每種算法都有自身的適用情況，對(duì)于不同的查詢(xún)，應(yīng)該采用不同的算法，以求獲得最好的結(jié)果。因此，對(duì)于查詢(xún)的分類(lèi)也顯得非常重要。

當(dāng)然，這些問(wèn)題帶有很大的主觀性，比如，質(zhì)量不能精確的定義，鏈接是否包含重要的信息也沒(méi)有有效的方法能準(zhǔn)確的判定，分析錨文本又涉及到語(yǔ)義問(wèn)題，查詢(xún)的分類(lèi)也沒(méi)有明確界限。如果算法要取得更好的效果，在這幾個(gè)方面需要繼續(xù)做深入的研究，相信在不久的將來(lái)會(huì)有更多的有趣和有用的成果出現(xiàn)。

億企邦點(diǎn)評(píng)：

我們所探討的這個(gè)基準(zhǔn)在不同的搜索引擎之間會(huì)有很大的差異，有些搜索引擎看重網(wǎng)頁(yè)中的鏈接，有些搜索引擎看重關(guān)鍵字和上下文，有些則重視元數(shù)據(jù)，但大部分的搜索引擎都會(huì)將這些因素以一定的比例組合在一起，組合的具體方法自然是各個(gè)搜索引擎的秘密。