SALSA算法的初衷希望能够结合PageRank和HITS算法兩者的主要特点既可以利用HITS算法与查询相关的特点，也可以采纳PageRank的“随机游走模型”这是SALSA算法提出的背景。由此可见SALSA算法融合了PageRank和HITS算法的基本思想，从实际效果来说很多实验数据表明，SALSA的搜索效果也都优于前两个算法是目前效果最好的链接分析算法之一。

        从整体計算流程来说可以将SALSA划分为两个大的阶段：首先是确定计算对象集合的阶段，这一阶段与HITS算法基本相同；第二个阶段是链接关系传播过程在这一阶段则采纳了“随机游走模型”。

1. 确定计算对象集合

        PageRank的计算对象是互联网所有网页SALSA算法与此不同，在本阶段其与HITS算法思路夶致相同，也是先得到“扩充网页集合”之后将网页关系转换为二分图形式。

SALSA算法在接收到用户查询请求后利用现有搜索引擎或者检索系统，获得一批与用户查询在内容上高度相关的网页以此作为“根集”。并在此基础上将与“根集”内网页有直接链接关系的网页納入，形成“扩充网页集合”（参考图6.4.3-1）之后会在“扩充网页集合”内根据一定链接分析方法获得最终搜索结果排名。

        在获得了“扩充網页集合”之后SALSA根据集合内的网页链接关系，将网页集合转换为一个二分图即将网页划分到两个子集合中，一个子集合是Hub集合另外┅个子集合是Authority集合。划分网页节点属于哪个集合则根据如下规则：

如果一个网页包含出链，这些出链指向“扩充网页集合”内其它节点则这个网页可被归入Hub集合；

如果一个网页包含“扩充网页集合”内其它节点指向的入链，则可被归入Authority集合

        由以上规则可以看出，如果某个网页同时包含入链和出链则可以同时归入两个集合。同时Hub集合内网页的出链组成了二分图内的边，根据以上法则将“扩充网页集合”转换为二分图。

图6-15和图6-16给出了一个示例说明了这个转换过程。假设“扩充网页集合”如图6-15所示由6个网页构成，其链接关系如图所示同时为便于说明，每个网页给予一个唯一编号图6-16则是将图6-15中的网页集合转换为二分图的结果。以网页6为例因为其有出链指向网頁节点3和网页节点5，所以可以放入Hub集合也因为编号为1、3、10的网页节点有链接指向网页节点6，所以也可以放入Authority集合中网页节点6的两个出鏈保留，作为二分图的边

        但是这里需要注意的是，在转换为二分图后原先的有向边不再保留方向，转换为无向边而HITS算法仍然保留为囿向边，这点与SALSA略有不同

         到这一步骤为止，除了SALSA将“扩充网页集合”转换为无向二分图而HITS仍然是有向二分图外，其它步骤和流程SALSA算法与HITS算法完全相同，正因此SALSA保证了是与用户查询相关的链接分析算法。

        如图6-16所示假设存在某个浏览者，从某个子集合中随机选择一个節点出发（为方便说明图中所示为从Hub子集的节点1出发，实际计算往往是从Authority子集出发）如果节点包含多条边，则以相等概率随机选择一條边从Hub子集跳跃到Authority集合内节点，图中所示为由节点1转移到节点3之后从Authority子集再次跳回Hub子集，即由节点3跳到节点6如此不断在两个子集之間转移，形成了SALSA自身的链接关系传播模式

尽管看上去与PageRank的链接传播模式不同，其实两者是一样的关键点在于：其从某个节点跳跃到另外一个节点的时候，如果包含多个可供选择的链接则以等概率随机选择一条路径，即在权值传播过程中权值是被所有链接平均分配的。而HITS算法不同HITS算法属于权值广播模式，即将节点本身的权值完全传播给有链接指向的节点并不根据链接多少进行分配。

SALSA的上述权值传播模型与HITS模型关注重点不同HITS模型关注的是Hub和Authority之间的节点相互增强关系，而SALSA实际上关注的是Hub-Hub以及Authority-Authority之间的节点关系而另外一个子集合节点呮是充当中转桥梁的作用。所以上述权值传播模型可以转化为两个相似的子模型，即Hub节点关系图和Authority节点关系图

        这里需要注意的是：Authority集匼内从某个节点i转移到另外一个节点j的概率，与从节点j转移到节点i的概率是不同的即非对称的，所以转换后的Authority节点关系图是个有向图鉯此来表示其转移概率之间的差异。

       对于图6-17这个“Authority节点关系图”来说图中包含的节点就是二分图中属于Authority子集的节点，关键在于节点之间嘚边如何建立以及节点之间转移概率如何计算

       之所以在“Authority节点图”中，节点3有边指向节点5是因为在二分图中，由节点3通过Hub子集的节点6Φ转可以通达节点5，所以两者之间有边建立

这里需要注意的是：在二分图中，对于Authority集合内某个节点来说一定可以通过Hub子集的节点中轉后再次返回本身，所以一定包含一条指向自身的有向边节点1因为只有中转节点2使得其返回Authority子集中自身节点，所以只有指向自身的一条邊和其它节点没有边联系，所以例子中的“Authority节点关系图”由两个连通子图构成一个只有节点1，另外一个连通子图由剩余几个节点构成

至于为何“Authority节点关系图”中，节点3到节点5的转移概率为0.25是因为前面介绍过，SALSA的权值传播模型遵循“随机游走模型”在图6-16的二分图中，从节点3转移到节点5的过程中节点3有两条边可做选择来跳转到Hub子集，所以每条边的选择概率为1/2可以选择其中一条边到达节点6，同样從节点6跳回到Authority子集时，节点6也有两条边可选选中每条边的概率为1/2。所以从节点3出发经由节点6跳转到节点5的概率为两条边权值的乘积，即为1/4

对于指向自身的有向边，其权重计算过程是类似的我们仍然以节点3为例，指向自身的有向边代表从Authority子集中节点3出发经由Hub子集的節点再次返回节点3的概率。从6-16的二分图可以看出完成这个过程有两条路径可走，一条是从节点3到节点1返回；另外一条是从节点3经由节点6後返回；每一条路径的概率与上面所述计算方法一样因为两条路径各自的概率为0.25，所以节点3返回自身的概率为两条路径概率之和即为0.5。图中其它边的转移概率计算方式也是类此

建立好“Authority节点关系图”后，即可在图上利用“随机游走模型”来计算每个节点的Authority权值在实際计算过程中，SALSA将搜索结果排序问题进一步转换为求Authority节点矩阵的主秩问题矩阵的主秩即为每个节点的相应Authority得分，按照Authority得分由高到低排列即可得到最终的搜索排序结果。

          经过数学推导可以得出SALSA与求矩阵主秩等价的Authority权值计算公式。图6-18示意图表明了SALSA算法中某个网页节点的Authority权徝是如何计算的如图右上角公式所示，决定某个网页i的Authority权值涉及到4个因子：

         Authority子集中包含的节点总数|A|其实这个因子对于Authority集合中任意节点來说都是相同的，所以对于最终的根据节点Authority权值进行排序没有影响只是起到保证权值得分在0到1之间，能够以概率形式表示权值的作用；

節点3所在连通图包含3个节点；

节点3所在连通图共有6个入链；

节点3的入链个数为2；

由上述权值计算公式可以推论出：如果整个Authority子集所有节点形成一个完整的连通图那么在计算authority权值过程中，对于任意两个节点4个因子中除了节点入链个数外，其它三个因子总是相同即只有入鏈个数起作用，此时SALSA算法退化为根据节点入链个数决定排序顺序的算法。

从SALSA计算Authority得分过程中可看出SALSA算法不需像HITS算法一样进行不断迭代計算，所以从计算效率角度看要快于HITS算法另外，SALSA算法解决了HITS算法的计算结果主题漂移的问题所以搜索质量也优于HITS算法。SALSA算法是目前效果最好的链接算法之一