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

《搜索引擎链接分析算法之：SALSA算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、SALSA算法的初衷希望能够结合PageRank和HITS算法两者的主要特点，既可以利用HITS算法与查询相关的特点，也可以采纳PageRank的“随机游走模型”，这是SALSA算法提出的背景。由此可见，SALSA算法融合了PageRank和HITS算法的基本思想，从实际效果来说，很多实验数据表明，SALSA的搜索效果也都优于前两个算法，是目前效果最好的外链链接分析算法之一。    从整体计算流程来说，可以将SALSA划分为两个大的阶段：首先是确定计算对象集合的阶段，这一阶段与HITS算法基本相同；第二个阶段是链接关系传播过程，在这一阶段则采纳了“随机游走模型”。1.确

2、定计算对象集合    PageRank的计算对象是互联网所有网页，SALSA算法与此不同，在本阶段，其与HITS算法思路大致相同，也是先得到“扩充网页集合”，之后将网页关系转换为二分图形式。    扩充网页集合    SALSA算法在接收到用户查询请求后，利用现有搜索引擎或者检索系统，获得一批与用户查询在内容上高度相关的网页，以此作为“根集”。并在此基础上，将与“根集”内网页有直接链接关系的网页纳入，形成“扩充网页集合”（参考图6.4.3-1）。之后会在“扩充网页集合”内根据一定链接分析方法获得最终搜索结果排名。    转换为无向二分图    在获得了“扩充网页集合”之

3、后，SALSA根据集合内的网页链接关系，将网页集合转换为一个二分图。即将网页划分到两个子集合中，一个子集合是Hub集合，另外一个子集合是Authority集合。划分网页节点属于哪个集合，则根据如下规则：如果一个网页包含出链，这些出链指向“扩充网页集合”内其它节点，则这个网页可被归入Hub集合；如果一个网页包含“扩充网页集合”内其它节点指向的入链，则可被归入Authority集合。    由以上规则可以看出，如果某个网页同时包含入链和出链，则可以同时归入两个集合。同时，Hub集合内网页的出链组成了二分图内的边，根据以上法则，将“扩充网页集合”转换为二分图。    图6-1

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

5、图后，原先的有向边不再保留方向，转换为无向边，而HITS算法仍然保留为有向边，这点与SALSA略有不同。                                     图6-16  二分图     到这一步骤为止，除了SALSA将“扩充网页集合”转换为无向二分图，而HITS仍然是有向二分图外，其它步骤和流程，SALSA算法与HITS算法完全相同，正因此，SALSA保证了是与用户查询相关的链接分析算法。2.链接关系传播     在链接关系传播阶段，SALSA放弃了HITS算法的Hub节点和Authority节点相互增强的假设，转而采纳PageRank的“随机游走

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

7、另外一个节点的时候，如果包含多个可供选择的链接，则以等概率随机选择一条路径，即在权值传播过程中，权值是被所有链接平均分配的。而HITS算法不同，HITS算法属于权值广播模式，即将节点本身的权值完全传播给有链接指向的节点，并不根据链接多少进行分配。  SALSA的上述权值传播模型与HITS模型关注重点不同，HITS模型关注的是Hub和Authority之间的节点相互增强关系，而SALSA实际上关注的是Hub-Hub以及Authority-Authority之间的节点关系，而另外一个子集合节点只是充当中转桥梁的作用。所以，上述权值传播模型可以