搜索引擎鏈接分析算法之：SALSA算法

《搜索引擎鏈接分析算法之：SALSA算法》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、SALSA算法的初衷希望能夠結(jié)合PageRank和HITS算法兩者的主要特點(diǎn)，既可以利用HITS算法與查詢(xún)相關(guān)的特點(diǎn)，也可以采納PageRank的“隨機(jī)游走模型”，這是SALSA算法提出的背景。由此可見(jiàn)，SALSA算法融合了PageRank和HITS算法的基本思想，從實(shí)際效果來(lái)說(shuō)，很多實(shí)驗(yàn)數(shù)據(jù)表明，SALSA的搜索效果也都優(yōu)于前兩個(gè)算法，是目前效果最好的外鏈鏈接分析算法之一。????從整體計(jì)算流程來(lái)說(shuō)，可以將SALSA劃分為兩個(gè)大的階段：首先是確定計(jì)算對(duì)象集合的階段，這一階段與HITS算法基本相同；第二個(gè)階段是鏈接關(guān)系傳播過(guò)程，在這一階段則采納了“隨機(jī)游走模型”。1.確

2、定計(jì)算對(duì)象集合????PageRank的計(jì)算對(duì)象是互聯(lián)網(wǎng)所有網(wǎng)頁(yè)，SALSA算法與此不同，在本階段，其與HITS算法思路大致相同，也是先得到“擴(kuò)充網(wǎng)頁(yè)集合”，之后將網(wǎng)頁(yè)關(guān)系轉(zhuǎn)換為二分圖形式。????擴(kuò)充網(wǎng)頁(yè)集合????SALSA算法在接收到用戶(hù)查詢(xún)請(qǐng)求后，利用現(xiàn)有搜索引擎或者檢索系統(tǒng)，獲得一批與用戶(hù)查詢(xún)?cè)趦?nèi)容上高度相關(guān)的網(wǎng)頁(yè)，以此作為“根集”。并在此基礎(chǔ)上，將與“根集”內(nèi)網(wǎng)頁(yè)有直接鏈接關(guān)系的網(wǎng)頁(yè)納入，形成“擴(kuò)充網(wǎng)頁(yè)集合”（參考圖6.4.3-1）。之后會(huì)在“擴(kuò)充網(wǎng)頁(yè)集合”內(nèi)根據(jù)一定鏈接分析方法獲得最終搜索結(jié)果排名。????轉(zhuǎn)換為無(wú)向二分圖????在獲得了“擴(kuò)充網(wǎng)頁(yè)集合”之

3、后，SALSA根據(jù)集合內(nèi)的網(wǎng)頁(yè)鏈接關(guān)系，將網(wǎng)頁(yè)集合轉(zhuǎn)換為一個(gè)二分圖。即將網(wǎng)頁(yè)劃分到兩個(gè)子集合中，一個(gè)子集合是Hub集合，另外一個(gè)子集合是Authority集合。劃分網(wǎng)頁(yè)節(jié)點(diǎn)屬于哪個(gè)集合，則根據(jù)如下規(guī)則：如果一個(gè)網(wǎng)頁(yè)包含出鏈，這些出鏈指向“擴(kuò)充網(wǎng)頁(yè)集合”內(nèi)其它節(jié)點(diǎn)，則這個(gè)網(wǎng)頁(yè)可被歸入Hub集合；如果一個(gè)網(wǎng)頁(yè)包含“擴(kuò)充網(wǎng)頁(yè)集合”內(nèi)其它節(jié)點(diǎn)指向的入鏈，則可被歸入Authority集合。????由以上規(guī)則可以看出，如果某個(gè)網(wǎng)頁(yè)同時(shí)包含入鏈和出鏈，則可以同時(shí)歸入兩個(gè)集合。同時(shí)，Hub集合內(nèi)網(wǎng)頁(yè)的出鏈組成了二分圖內(nèi)的邊，根據(jù)以上法則，將“擴(kuò)充網(wǎng)頁(yè)集合”轉(zhuǎn)換為二分圖。????圖6-1

4、5和圖6-16給出了一個(gè)示例，說(shuō)明了這個(gè)轉(zhuǎn)換過(guò)程。假設(shè)“擴(kuò)充網(wǎng)頁(yè)集合”如圖6-15所示，由6個(gè)網(wǎng)頁(yè)構(gòu)成，其鏈接關(guān)系如圖所示，同時(shí)為便于說(shuō)明，每個(gè)網(wǎng)頁(yè)給予一個(gè)唯一編號(hào)。圖6-16則是將圖6-15中的網(wǎng)頁(yè)集合轉(zhuǎn)換為二分圖的結(jié)果。以網(wǎng)頁(yè)6為例，因?yàn)槠溆谐鲦溨赶蚓W(wǎng)頁(yè)節(jié)點(diǎn)3和網(wǎng)頁(yè)節(jié)點(diǎn)5，所以可以放入Hub集合，也因?yàn)榫幪?hào)為1、3、10的網(wǎng)頁(yè)節(jié)點(diǎn)有鏈接指向網(wǎng)頁(yè)節(jié)點(diǎn)6，所以也可以放入Authority集合中。網(wǎng)頁(yè)節(jié)點(diǎn)6的兩個(gè)出鏈保留，作為二分圖的邊，?????????????????????????????????圖6-15擴(kuò)充網(wǎng)頁(yè)集合示例?????但是這里需要注意的是，在轉(zhuǎn)換為二分

5、圖后，原先的有向邊不再保留方向，轉(zhuǎn)換為無(wú)向邊，而HITS算法仍然保留為有向邊，這點(diǎn)與SALSA略有不同。?????????????????????????????????????圖6-16??二分圖?????到這一步驟為止，除了SALSA將“擴(kuò)充網(wǎng)頁(yè)集合”轉(zhuǎn)換為無(wú)向二分圖，而HITS仍然是有向二分圖外，其它步驟和流程，SALSA算法與HITS算法完全相同，正因此，SALSA保證了是與用戶(hù)查詢(xún)相關(guān)的鏈接分析算法。2.鏈接關(guān)系傳播?????在鏈接關(guān)系傳播階段，SALSA放棄了HITS算法的Hub節(jié)點(diǎn)和Authority節(jié)點(diǎn)相互增強(qiáng)的假設(shè)，轉(zhuǎn)而采納PageRank的“隨機(jī)游走

6、模型”。鏈接關(guān)系傳播概念模型????如圖6-16所示，假設(shè)存在某個(gè)瀏覽者，從某個(gè)子集合中隨機(jī)選擇一個(gè)節(jié)點(diǎn)出發(fā)（為方便說(shuō)明，圖中所示為從Hub子集的節(jié)點(diǎn)1出發(fā)，實(shí)際計(jì)算往往是從Authority子集出發(fā)），如果節(jié)點(diǎn)包含多條邊，則以相等概率隨機(jī)選擇一條邊，從Hub子集跳躍到Authority集合內(nèi)節(jié)點(diǎn)，圖中所示為由節(jié)點(diǎn)1轉(zhuǎn)移到節(jié)點(diǎn)3，之后從Authority子集再次跳回Hub子集，即由節(jié)點(diǎn)3跳到節(jié)點(diǎn)6。如此不斷在兩個(gè)子集之間轉(zhuǎn)移，形成了SALSA自身的鏈接關(guān)系傳播模式。?????盡管看上去與PageRank的鏈接傳播模式不同，其實(shí)兩者是一樣的，關(guān)鍵點(diǎn)在于：其從某個(gè)節(jié)點(diǎn)跳躍到

7、另外一個(gè)節(jié)點(diǎn)的時(shí)候，如果包含多個(gè)可供選擇的鏈接，則以等概率隨機(jī)選擇一條路徑，即在權(quán)值傳播過(guò)程中，權(quán)值是被所有鏈接平均分配的。而HITS算法不同，HITS算法屬于權(quán)值廣播模式，即將節(jié)點(diǎn)本身的權(quán)值完全傳播給有鏈接指向的節(jié)點(diǎn)，并不根據(jù)鏈接多少進(jìn)行分配。??SALSA的上述權(quán)值傳播模型與HITS模型關(guān)注重點(diǎn)不同，HITS模型關(guān)注的是Hub和Authority之間的節(jié)點(diǎn)相互增強(qiáng)關(guān)系，而SALSA實(shí)際上關(guān)注的是Hub-Hub以及Authority-Authority之間的節(jié)點(diǎn)關(guān)系，而另外一個(gè)子集合節(jié)點(diǎn)只是充當(dāng)中轉(zhuǎn)橋梁的作用。所以，上述權(quán)值傳播模型可以