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

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

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

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

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

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

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

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

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