SALSA算法

PageRank算法是基于用户随机的向前浏览网页的直觉知识，HITS算法考虑的是Authoritive网页和Hub网页之间的加强关系。实际应用中，用户大多数情况下是向前浏览网页，但是很多时候也会回退浏览网页。基于上述直觉知识，R. Lempel和S. Moran提出了SALSA（Stochastic Approach for Link-Structure Analysis）算法[8]，考虑了用户回退浏览网页的情况，保留了PageRank的随机漫游和HITS中把网页分为Authoritive和Hub的思想，取消了Authoritive和Hub之间的相互加强关系。 具体算法如下：

１．和HITS算法的第一步一样，得到根集并且扩展为网页集合T，并除去孤立节点。

２．从集合T构造无向图G’＝（Vh，Va，E） Vh = { sh |　s∈C and out-degree(s) > 0 } ( G’的Hub边). Va = { sa |　s∈C and in-degree(s) > 0 } (G’的Authority边). E= { (sh , ra) |　s－>r　in T　} 这就定义了2条链，Authority链和Hub链。

３．定义2条马尔可夫链的变化矩阵，也是随机矩阵，分别是Hub矩阵H，Authority矩

４．求出矩阵H，A的主特征向量，就是对应的马尔可夫链的静态分布。

５．A中值大的对应的网页就是所要找的重要网页。 SALSA算法没有HITS中相互加强的迭代过程，计算量远小于HITS。SALSA算法只考虑直接相邻的网页对自身A/H的影响，而HITS是计算整个网页集合T对自身AH的影响。

实际应用中，SALSA在扩展根集时忽略了很多无关的链接，比如

１．同一站点内的链接，因为这些链接大多只起导航作用。

２．CGI 脚本链接。

３．广告和赞助商链接。 试验结果表明，对于单主题查询java，SALSA有比HITS更精确的结果，对于多主题查询abortion，HITS的结果集中于主题的某个方面，而SALSA算法的结果覆盖了多个方面，也就是说，对于TKC现象，SALSA算法比HITS算法有更高的健壮性。

BFS（Backword Forward Step）算法

SALSA算法计算网页的Authority值时，只考虑网页在直接相邻网页集中的受欢迎程度，忽略其它网页对它的影响。HITS算法考虑的是整个图的结构，特别的，经过n步以后，网页i的Authority的权重是>，为离开网页i的的路径的数目，也就是说网页j<>i，对i的权值贡献等于从i到j的路径的数量。如果从i到j包含有一个回路，那么j对i的贡献将会呈指数级增加，这并不是算法所希望的，因为回路可能不是与查询相关的。

因此，Allan Borodin等[11]提出了BFS（Backward Forward Step）算法，既是SALSA的扩展情况，也是HITS的限制情况。基本思想是，SALSA只考虑直接相邻网页的影响，BFS扩展到考虑路径长度为n的相邻网页的影响。在BFS中，被指定表示能通过路径到达i的结点的集合，这样j对i的贡献依赖就与j到i的距离。BFS采用指数级降低权值的方式，结点i的权值计算公式如下： ＝|B(i)|+ |BF(i)| +|BFB(i)|+……+||

算法从结点i开始，第一步向后访问，然后继续向前或者向后访问邻居，每一步遇到新的结点加入权值计算，结点只有在第一次被访问时加入进去计算。