[SEM行业] 搜索引擎优化中链接分析的SALSA算法

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

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

　　２．从集合T构造无向图G’＝（Vh，Va，E）Vh={sh|　s∈Candout-degree(s)>0}(G’的Hub边).Va={sa|　s∈Candin-degree(s)>0}(G’的Authority边).E={(sh,ra)|　s－>r　inT　}这就定义了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（BackwordForwardStep）算法

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

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

　　算法从结点i开始，第一步向后访问，然后继续向前或者向后访问邻居，每一步遇到新的结点加入权值计算，结点只有在第一次被访问时加入进去计算。以上内容由冷拔机 www.hftyjx.cn  为您收集整理