aihot  2020-11-12 11:22:34  OpenCV |   查看评论   

  首先SALSA算法像HITS算法一样算出扩展网页集合

  之后,SALSA算法根据网页链接关系,将扩展网页集合转换为一个二分图,一个子集合是Hub集合,另一个是Authroity集合,规则如下:

  • 如果一个网页网页包含出链指向扩展网页集合内其他节点,则这个网页可以被归入Hub集合
  • 如果一个网页网页包含扩展网页集合内其他节点指向的入链,则这个网页可以被归入Authority集合

  根据以上规则,如果某个网页同时包含入链和出链,则可以同时归入两个集合。Hub集合内网页的出链组成了二分图的边。

  与HITS算法不同,这里SALSA在形成二分图之后,原来的有向边不再保留方向,转换为无向边:

二分图

二分图

  接下来是链接关系传播阶段,SALSA算法舍弃了HITS的相互增强假设,转而采用PageRank随机游走模型的思想。

  SALSA算法假设存在某个浏览者,从子集合中随机选择一个节点出发,如果节点包含多条边,则以相等概率随机选择一条边,从Hub(Authority)子集合跳到Authority(Hub)集合内节点,如此不断在两个子集之间转移,形成了SALSA自身的链接关系传播模式。

  这个随机游走模型看起来与PageRank不同,但实际上『以相等概率随机选择一条边』与『每个页面将其当前的PageRank值平均分配到本页包含的出链上』是等价的。而HITS算法属于权值广播模式,即将节点本身的权值完全传播给有链接指向的节点,并不根据链接多少进行分配。

  之后我们要将二分图转化为Authority节点关系图。

  得到Authority节点关系图要去掉原二分图中的Hub节点,只保留Authority节点,并新建Authority节点之间的链接关系,Authority节点之间的链接关系继承自二分图中原有的链接关系。简单举个例子,Authority节点A到B的链接概率为原二分图中所有A到B的间接路径的概率和,而每条间接路径的概率通过这条路径上所有子路径的概率乘积计算得出,每条子路径的概率根据所属节点出链的个数平均分配。最后得到的Authority节点关系图如下:

Authority

  可以发现节点1是独立的,是因为在原二分图中并不存在由节点1到节点3/5/6的任何间接路径。(其实Authority节点关系图在后面起到的作用只是判断哪些节点之间是连通的,转移概率并没有用到)

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

  简单说一下,我们根据Authority节点关系图得知节点3、5、6是连通的,1是独立的,然后我们根据如下公式计算每个Authority节点的Authority权值得分:

Authority

  这个式子很好理解,第一部分就是当前节点所在的子连通图的节点个数占总节点个数的百分比,也即当前节点所在子连通图对于整个Authority节点关系图的重要程度;第二部分是当前节点的入链个数占当前节点所在子连通图入链个数的百分比,也即当前节点在当前节点所在子连通图的重要程度。从式子中也可以看出,所有Authority节点的权值之和为1。

  举个例子,节点3的权重最后计算结果为0.25,3/4乘2/6。

  另外,如果整个Authority节点关系图是连通的,那么SALSA算法退化为根据节点入链个数决定排序顺序的算法。

  SALSA算法不需要像HITS算法一样进行不断的迭代,所以计算效率要快于HITS算法,也同时解决了HITS算法的主题漂移问题(一是因为去掉了Hub页面,二是倾向于取Authority中重要连通图中重要的子Authority节点)。SALSA算法是目前效果最好的链接分析算法之一。

 

除特别注明外,本站所有文章均为 赢咖4注册 原创,转载请注明出处来自浅谈搜索引擎基础(下)

留言与评论(共有 0 条评论)
   
验证码:
[lianlun]1[/lianlun]