搜索引擎优化中链接的三种算法PHITS+SALSA+贝叶斯

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开始，第一步向后访问，然后继续向前或者向后访问邻居，每一步遇到新的结点加入权值计算，结点只有在第一次被访问时加入进去计算。

贝叶斯算法

　Allan Borodin等提出了完全的贝叶斯统计方法来确定Hub和Authoritive网页[11]。假定有M个Hub网页和N个Authority网页，可以是相同的集合。每个Hub网页有一个未知的实数参数，表示拥有超链的一般趋势，一个未知的非负参数，表示拥有指向Authority网页的链接的趋势。每个Authoritive网页j，有一个未知的非负参数，表示j的Authority的级别。

　　统计模型如下，Hub网页i到Authority网页j的链接的先验概率如下给定：

　　P（i，j）＝Exp（＋）/（1＋Exp（＋））

　　Hub网页i到Authority网页j没有链接时，P（i，j）＝1/（1＋Exp（＋））
 从以上公式可以看出，如果很大（表示Hub网页i有很高的趋势指向任何一个网页），或者和都很大（表示i是个高质量Hub，j是个高质量的Authority网页），那么i－>j的链接的概率就比较大。