常見的web網(wǎng)站超鏈接分析算法

1、傳統(tǒng)的WEB搜索引擎大多數(shù)是基于關(guān)鍵字匹配的，返回的結(jié)果是包含查詢項(xiàng)的文檔，也有基于目錄分類的搜索引擎。這些搜索引擎的結(jié)果并不令人滿意。有些站點(diǎn)有意提高關(guān)鍵字出現(xiàn)的頻率來(lái)提高自身在搜索引擎中的重要性，破壞搜索引擎結(jié)果的客觀性和準(zhǔn)確性。另外，有些重要的網(wǎng)頁(yè)并不包含查詢項(xiàng)。搜索引擎的分類目錄也不可能把所有的分類考慮全面，并且目錄大多靠人工維護(hù)，主觀性強(qiáng)，費(fèi)用高，更新速度慢[2]。最近幾年，許多研究者發(fā)現(xiàn)，WWW上超鏈結(jié)構(gòu)是個(gè)非常豐富和重要的

2、資源，如果能夠充分利用的話，可以極大的提高檢索結(jié)果的質(zhì)量?；谶@種超鏈分析的思想，SergeyBrin和LawrencePage在1998年提出了PageRank算法[1]，同年J.Kleinberg提出了HITS算法[5]，其它一些學(xué)者也相繼提出了另外的鏈接分析算法，如SALSA，PHITS，Bayesian等算法。這些算法有的已經(jīng)在實(shí)際的系統(tǒng)中實(shí)現(xiàn)和使用，并且取得了良好的效果。文章的第2部分按照時(shí)間順序詳細(xì)剖析了各種鏈接分析算法，對(duì)

3、不同的算法進(jìn)行了比較。第3部分對(duì)這些算法做了評(píng)價(jià)和總結(jié)，指出了存在的問(wèn)題和改進(jìn)方向。一、WEB超鏈分析算法1Google和PageRank算法搜索引擎Google最初是斯坦福大學(xué)的博士研究生SergeyBrin和LawrencePage實(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é)

4、果的最前面。Google通過(guò)PageRank元算法計(jì)算出網(wǎng)頁(yè)的PageRank值，從而決定網(wǎng)頁(yè)在結(jié)果集中的出現(xiàn)位置，PageRank值越高的網(wǎng)頁(yè)，在結(jié)果中出現(xiàn)的位置越前。1.1PageRank算法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)威（Authitiv

5、e）網(wǎng)頁(yè)。前提2：假定用戶一開始隨機(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è)，F(xiàn)(u)是u指向的網(wǎng)頁(yè)集合，B(u)是指向u的網(wǎng)頁(yè)集合，N(u)是u指向外的鏈接數(shù)，顯然N(u)=|F(u)|，c是一個(gè)用于規(guī)范化的因子（Google通常取0.85），（這種表示法也適用于以后介紹的算法）則u的Rank值計(jì)算

6、如下：這就是算法的形式化描述，也可以用矩陣來(lái)描述此算法，設(shè)A為一個(gè)方陣，行和列對(duì)應(yīng)網(wǎng)頁(yè)集的網(wǎng)頁(yè)。如果網(wǎng)頁(yè)i有指向網(wǎng)頁(yè)j的一個(gè)鏈接，則Aij=1Ni，否則Aij＝0。設(shè)V是對(duì)應(yīng)有些鏈接具有注釋性，也有些鏈接是起導(dǎo)航或廣告作用。有注釋性的鏈接才用于權(quán)威判斷?；谏虡I(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搜索引擎之類的描述信息。可見平均的分布權(quán)值不符合鏈接的

7、實(shí)際情況[17]。J.Kleinberg[5]提出的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)的鏈接集合，比一個(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與Authitive網(wǎng)頁(yè)之間的相

8、互加強(qiáng)關(guān)系，可用于權(quán)威網(wǎng)頁(yè)的發(fā)現(xiàn)和WEB結(jié)構(gòu)和資源的自動(dòng)發(fā)現(xiàn)，這就是HubAuthity方法的基本思想。2.1HITS算法HITS（Hyperlink－InducedTopicSearch）算法是利用HubAuthity方法的搜索方法，算法如下：將查詢q提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎搜索引擎返回很多網(wǎng)頁(yè)，從中取前n個(gè)網(wǎng)頁(yè)作為根集(rootset)，用S表示。S滿足如下3個(gè)條件：S中網(wǎng)頁(yè)數(shù)量相對(duì)較小S中網(wǎng)頁(yè)大多數(shù)是與查詢q相關(guān)的網(wǎng)頁(yè)

9、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è)的Authity值。開始時(shí)h(v)＝a(u)＝1，對(duì)u執(zhí)行I操作修改它的a(u)，對(duì)v執(zhí)行O操作修改它的h(

10、v)，然后規(guī)范化a（u），h（v），如此不斷的重復(fù)計(jì)算下面的操作I，O，直到a（u），h（v）收斂。（證明此算法收斂可見）每次迭代后需要對(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算法一樣，可