SALSA算法的初衷希望能夠結(jié)合PageRank和HITS算法兩者的主要特點，既可以利用HITS算法與查詢相關(guān)的特點，也可以采納PageRank的“隨機游走模型”，這是SALSA算法提出的背景由此可見，SALSA算法融合了PageRank和HITS算法的基本思想，從實際效果來說，很多實驗數(shù)據(jù)表明，SALSA的搜索效果也都優(yōu)于前兩個算法，是目前效果最好的外鏈鏈接分析算法之一? ? ? ? 從整體計算流程來說，可以將SALSA劃分為兩個大的階段：首先是確定計算對象集合的階段，這一階段與HITS算法基本相同；第二個階段是鏈接關(guān)系傳播過程，在這一階段則采納了“隨機游走模型”1. 確定計算對象集合? ? ? ? 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)頁集合”之后，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-15和圖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)換為二分圖后，原先的有向邊不再保留方向，轉(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é)點相互增強的假設(shè)，轉(zhuǎn)而采納PageRank的“隨機游走模型”鏈接關(guān)系傳播概念模型? ? ? ? 如圖6-16所示，假設(shè)存在某個瀏覽者，從某個子集合中隨機選擇一個節(jié)點出發(fā)（為方便說明，圖中所示為從Hub子集的節(jié)點1出發(fā)，實際計算往往是從Authority子集出發(fā)），如果節(jié)點包含多條邊，則以相等概率隨機選擇一條邊，從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é)點跳躍到另外一個節(jié)點的時候，如果包含多個可供選擇的鏈接，則以等概率隨機選擇一條路徑，即在權(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é)點相互增強關(guān)系，而SALSA實際上關(guān)注的是Hub-Hub以及Authority-Authority之間的節(jié)點關(guān)系，而另外一個子集合節(jié)點只是充當(dāng)中轉(zhuǎn)橋梁的作用所以，上述權(quán)值傳播模型可以轉(zhuǎn)化為兩個相似的子模型，即Hub節(jié)點關(guān)系圖和Authority節(jié)點關(guān)系圖?Authority節(jié)點關(guān)系圖? ? ? ? ? 圖6-17是由6-16的二分圖轉(zhuǎn)化成的“Authority節(jié)點關(guān)系圖”，“Hub節(jié)點關(guān)系圖”與此類似，兩者轉(zhuǎn)化過程是相似的，我們以“Authority節(jié)點關(guān)系圖”為例來看如何從二分圖轉(zhuǎn)化為節(jié)點關(guān)系圖。

? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖6-17? Authority節(jié)點關(guān)系圖?? ? ? ? 這里需要注意的是：Authority集合內(nèi)從某個節(jié)點i轉(zhuǎn)移到另外一個節(jié)點j的概率，與從節(jié)點j轉(zhuǎn)移到節(jié)點i的概率是不同的，即非對稱的，所以轉(zhuǎn)換后的Authority節(jié)點關(guān)系圖是個有向圖，以此來表示其轉(zhuǎn)移概率之間的差異? ? ? ?對于圖6-17這個“Authority節(jié)點關(guān)系圖”來說，圖中包含的節(jié)點就是二分圖中屬于Authority子集的節(jié)點，關(guān)鍵在于節(jié)點之間的邊如何建立以及節(jié)點之間轉(zhuǎn)移概率如何計算?節(jié)點關(guān)系圖中邊的建立? ? ? ?之所以在“Authority節(jié)點圖”中，節(jié)點3有邊指向節(jié)點5，是因為在二分圖中，由節(jié)點3通過Hub子集的節(jié)點6中轉(zhuǎn)，可以通達(dá)節(jié)點5，所以兩者之間有邊建立? ? ? ?這里需要注意的是：在二分圖中，對于Authority集合內(nèi)某個節(jié)點來說，一定可以通過Hub子集的節(jié)點中轉(zhuǎn)后再次返回本身，所以一定包含一條指向自身的有向邊節(jié)點1因為只有中轉(zhuǎn)節(jié)點2使得其返回Authority子集中自身節(jié)點，所以只有指向自身的一條邊，和其它節(jié)點沒有邊聯(lián)系，所以例子中的“Authority節(jié)點關(guān)系圖”由兩個連通子圖構(gòu)成，一個只有節(jié)點1，另外一個連通子圖由剩余幾個節(jié)點構(gòu)成。

?節(jié)點之間的轉(zhuǎn)移概率? ? ? ? 至于為何“Authority節(jié)點關(guān)系圖”中，節(jié)點3到節(jié)點5的轉(zhuǎn)移概率為0.25，是因為前面介紹過，SALSA的權(quán)值傳播模型遵循“隨機游走模型”在圖6-16的二分圖中，從節(jié)點3轉(zhuǎn)移到節(jié)點5的過程中，節(jié)點3有兩條邊可做選擇來跳轉(zhuǎn)到Hub子集，所以每條邊的選擇概率為1/2，可以選擇其中一條邊到達(dá)節(jié)點6，同樣，從節(jié)點6跳回到Authority子集時，節(jié)點6也有兩條邊可選，選中每條邊的概率為1/2所以從節(jié)點3出發(fā)，經(jīng)由節(jié)點6跳轉(zhuǎn)到節(jié)點5的概率為兩條邊權(quán)值的乘積，即為1/4? ? ? ?對于指向自身的有向邊，其權(quán)重計算過程是類似的，我們?nèi)匀灰怨?jié)點3為例，指向自身的有向邊代表從Authority子集中節(jié)點3出發(fā)，經(jīng)由Hub子集的節(jié)點再次返回節(jié)點3的概率從6-16的二分圖可以看出，完成這個過程有兩條路徑可走，一條是從節(jié)點3到節(jié)點1返回；另外一條是從節(jié)點3經(jīng)由節(jié)點6后返回；每一條路徑的概率與上面所述計算方法一樣，因為兩條路徑各自的概率為0.25，所以節(jié)點3返回自身的概率為兩條路徑概率之和，即為0.5圖中其它邊的轉(zhuǎn)移概率計算方式也是類此? ? ? ?建立好“Authority節(jié)點關(guān)系圖”后，即可在圖上利用“隨機游走模型”來計算每個節(jié)點的Authority權(quán)值。

在實際計算過程中，SALSA將搜索結(jié)果排序問題進(jìn)一步轉(zhuǎn)換為求Authority節(jié)點矩陣的主秩問題，矩陣的主秩即為每個節(jié)點的相應(yīng)Authority得分，按照Authority得分由高到低排列，即可得到最終的搜索排序結(jié)果?3. Authority權(quán)值計算?? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖6-18? SALSA節(jié)點權(quán)值計算公式?? ? ? ? ? 經(jīng)過數(shù)學(xué)推導(dǎo)，可以得出SALSA與求矩陣主秩等價的Authority權(quán)值計算公式圖6-18示意圖表明了SALSA算法中某個網(wǎng)頁節(jié)點的Authority權(quán)值是如何計算的如圖右上角公式所示，決定某個網(wǎng)頁i的Authority權(quán)值涉及到4個因子：? ? ? ? ?Authority子集中包含的節(jié)點總數(shù)|A|其實這個因子對于Authority集合中任意節(jié)點來說都是相同的，所以對于最終的根據(jù)節(jié)點Authority權(quán)值進(jìn)行排序沒有影響，只是起到保證權(quán)值得分在0到1之間，能夠以概率形式表示權(quán)值的作用；? ? ? ? 網(wǎng)頁i所在連通圖中包含的節(jié)點個數(shù)|Aj|。

網(wǎng)頁所在的連通圖包含的節(jié)點個數(shù)越多，則網(wǎng)頁的Authority權(quán)值越大；? ? ? ? 網(wǎng)頁i所在連通圖中包含的入鏈總數(shù)|Ej|網(wǎng)頁所在的連通圖包含的入鏈總數(shù)越少，則網(wǎng)頁的Authority權(quán)值越大；? ? ? ? 網(wǎng)頁i的入鏈個數(shù)|Bi|節(jié)點入鏈越多，則Authority權(quán)值越大，這個因子是唯一一個和節(jié)點本身屬性相關(guān)的由此可見，SALSA權(quán)值計算和節(jié)點入鏈個數(shù)成正比? ? ? ? ?之前圖6-17的“Authority節(jié)點關(guān)系圖”由兩個連通子圖組成，一個由唯一的節(jié)點1構(gòu)成，另外一個由節(jié)點3、5、6三個節(jié)點構(gòu)成，兩個連通子圖在圖6-18中也被分別圈出? ? ? ? ?我們以節(jié)點3為例，看其對應(yīng)的四個計算因素取值：Authority子集共包括4個節(jié)點；節(jié)點3所在連通圖包含3個節(jié)點；節(jié)點3所在連通圖共有6個入鏈；節(jié)點3的入鏈個數(shù)為2；? ? ? ? ?所以，節(jié)點3的Authority權(quán)值為：（3/4）*(2/6)=0.25其它節(jié)點權(quán)值的計算過程與此類似SALSA根據(jù)節(jié)點的Authority權(quán)值由高到低排序輸出，即為搜索結(jié)果? ? ? ? ?由上述權(quán)值計算公式可以推論出：如果整個Authority子集所有節(jié)點形成一個完整的連通圖，那么在計算authority權(quán)值過程中，對于任意兩個節(jié)點，4個因子中除了節(jié)點入鏈個數(shù)外，其它三個因子總是相同，即只有入鏈個數(shù)起作用，此時，SALSA算法退化為根據(jù)節(jié)點入鏈個數(shù)決定排序順序的算法。

? ? ? ? ? 從SALSA計算Authority得分過程中可看出，SALSA算法不需像HITS算法一樣進(jìn)行不斷迭代計算，所以從計算效率角度看要快于HITS算法另外，SALSA算法解決了HITS算法的計算結(jié)果主題漂移的問題，所以搜索質(zhì)量也優(yōu)于HITS算法SALSA算法是目前效果最好的鏈接算法之一。