搜索引擎算法研究(四)-搜索引擎技术

２.３　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）
V_h = { s_h |　　 s∈C and out-degree(s) > 0 } ( G’的Hub边).
V_a = { s_a |　　 s∈C and in-degree(s) > 0 } (G’的Authority边).
E= { (s_h , r_a) |　　s－>r　　 in T　}
这就定义了2条链，Authority链和Hub链。
３．定义2条马尔可夫链的变化矩阵，也是随机矩阵，分别是Hub矩阵H，Authority矩阵A。
４．求出矩阵H，A的主特征向量，就是对应的马尔可夫链的静态分布。
５．A中值大的对应的网页就是所要找的重要网页。

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

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

１．同一站点内的链接，因为这些链接大多只起导航作用。
２．CGI 脚本链接。
３．广告和赞助商链接。

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