SALSA算法

之前写的SALSA算法有些地方理解不到位，写错了。现在更正一下。推荐论文：Lempel R, Moran S. The stochastic approach for link-structure analysis (SALSA) and the TKC effect[J]. Computer Networks, 2000, 33(1):387-401。这篇论文提出了SALSA算法，并且里面讲的也比较详细。

在看SALSA算法的其他材料时，对于SALSA算法最后只跟联通图里的节点连边有关十分的不解。算法前面讲一大堆，最后只要根据节点连边多少进行排序，这算法未免也太哗众取宠了。有些论文，只是简单的写出最后结果；有些论文甚至连个公式都没有，个人觉得真是不靠谱。对于很多资料中所说的，最后取值是矩阵最大特征值的特征向量的标准化，无奈线性代数跟不上博主所需，花了一上午推导出的结果愣是跟那些材料中的样例结果八竿子打不到边。怕是那些写这些论文或材料的学者，自身都没有搞懂，甚至，在他们的论文中，发现了诸多的错误。现在，我把我所理解的SALSA算法在本文做一个简单的描述，希望能帮到同我一样需要且有同样困惑的人。如果博主有理解偏差之处，还望各位不吝赐教。

开始是导师推荐我去学习一下SALSA算法，并且推荐了我一篇博文http://blog.csdn.net/hguisu/article/details/8016916。作者写的很不错，图文并茂。博文中直到authority权值计算部分都写的很不错，但是我看到这一部分后，十分惊讶。因为SALSA算法的这一步，跟前面都没什么关系，那前面讲这么多有什么用呢？直接统计计算集合中的节点的度不就好了吗？带着这个疑惑，我阅读了很多文献，直到看到本文开头提及的文献才明白过来(有些文献里面有错误，公式推导不出来，即使那些是SCI论文)。

想要彻底弄懂SALSA算法，需要马尔可夫链的相关知识，也需要一点点图论的知识。本人对于马尔可夫链基本不了解，只是在看预测相关论文时，有看到过，不过，这似乎并不影响我阅读那篇论文。

导师推荐的博文，对SALSA做了一些简化，它文中的authority权值计算部分，是建立在边权相等均为1的基础上的，所以让我产生了只要直接统计节点入度的理解。不过。。。即使是边权不相等的情况下，也可以将节点的连边按权相加，这主要得益于π*p=π。对于SALSA算法最后直接与集合中节点的度挂钩，是经过上述公式的计算后得到的。这样一来，上述博文前后就能贯通了。由于上述博文对于SALSA写的还是比较好的，所以本文就不再赘述了。

这里，我想要补充的是：

1.SALSA算法的计算有一个前提条件，即计算转移概率时，两个节点之间只通过一个节点相连，即这两个节点属于文献计量学里面的共被引或耦合关系。

2.SALSA算法可以说是HITS算法的一个拓展。

3.在实际应用中，似乎可以直接在建立二分连通图后，根据节点的度对节点进行排序，而不需要对算法进行多次迭代计算。所以，SALSA算法在一定程度上效率会高于PageRank和HITS算法。

4.SALSA算法与HITS算法的不同之处在于他的authority集合和hub集合是相对独立的，两者之间不会相互增强。

5.HITS算法需要维护一个引用的邻接矩阵，PageRank算法需要维护一个对行标准化的邻接矩阵，SALSA算法需要维护一个对行和对列分别标准化的邻接矩阵。其实，这些邻接矩阵其实就是节点值之间的传递概率。

最后，想说的是：数学才是算法和编程的内核。