The Markov Cluster Algorithm (MCL)

算法

MCL算法是一种快速可扩展的无监督聚类算法，它的思想非常简单，其核心包括两个内容：Expansion 和 Inflation。

算法基础

这个算法的基础是 随机游走 和 马尔科夫链：

随机游走 它是基于这样一个假设：当我们在划分社团的时候，我们会发现社团内部节点的连边会比较多，而社团与社团之间的连边相对较少。基于这个假设，假设我们从图中的某一个点开始“瞎转”，那么我们很可能就会在某一个社团里面转悠，而不是在社团间来回游荡，而随机游走的计算是通过马尔科夫链来实现的。

马尔科夫链 指的是给定一个随机序列，将来的状态只与现在的状态有关，而与过去的状态无关，满足这样的性质的离散序列就成为马尔科夫链，这也就是大名鼎鼎的马尔科夫“无后效性”，也就是说不管我以前犯了多少错做了多少坏事，只有我现在认真改正，好好学习，天天向上，将来还是有机会迎娶白富美，当上CEO，走向人生巅峰的。

算法核心

Expansion 这个步骤其实就是求前面提到的马尔科夫链的转移矩阵的极限分布。转移矩阵表示的就是在初识状态下，某个节点转移到另一个节点的概率所组成的矩阵。这里举一个例子，比如一个图中有1,2,3这3个节点，他们之间两两互相连接，不考虑权重，那么这个时候它的转系矩阵就是P=[0 0.5 0.5; 0.5 0 0.5; 0.5 0.5 0]了。而 expansion 这个步骤不断地对这个转移矩阵进行自乘直到它不再改变为止，这也就是求平稳分布的过程。而expansion的作用就是为了能够将图中不同的区域连接起来。

Infaltion 的思想也很简单。首先，我们先说inflation的目的是什么，它的目的是为了强邻居的连接更强，弱邻居的连接更弱，也就是让转系矩阵中概率大的概率更大，而小的更小。一种最直观的操作就是进行幂操作！比若说我对概率矩阵进行平方操作，（需要注意的是，这个操作与expansion的不同之处在于expansion是矩阵的乘法，而这里是分别对矩阵中的每一个元素进行平方操作），然后我们在将每一列归一化，这样就达到了上述目的。

算法流程

有了上述的算法基础和核心内容，我们就可以很轻松的给出MCL算法的流程步骤：

1. 给定一个无向图（有权无权都可），以及expansion 和 inflation 的参数 e 和 r。
2. 生成连接矩阵。
3. 给每个节点添加自环（可选）。
4. 归一化矩阵，得到转移矩阵。
5. 对矩阵进行 expansion 操作。
6. 对矩阵进行 inflation 操作。
7. 重复 5 和 6 直至收敛。
8. 根据最后得到的矩阵进行划分cluster。

参考文献

[1] PDF
[2] http://micans.org/mcl/。
[3] Markdown原稿。