Tag Archives: 随机游走

随机矩阵及其特征值

随机矩阵是这样一类方阵,其元素为非负实数,且行和或列和为1。如果行和为1,则称为行随机矩阵;如果列和为1,则称为列随机矩阵;如果行和和列和都为1,则称为双随机矩阵。

前面我们介绍的谷歌矩阵HMM中的转移矩阵都属于随机矩阵,所以随机矩阵也称为概率矩阵、转移矩阵、或马尔可夫矩阵。

随机矩阵有一个性质,就是其所有特征值的绝对值小于等于1,且其最大特征值为1。下面通过两种方法证明这个结论。

首先,随机矩阵A肯定有特征值1,即\begin{equation}A\vec 1=1\times\vec 1\end{equation}其中的单位向量$\vec 1=(\frac{1}{n},...,\frac{1}{n})^T$,因为A的行和为1,所以上述等式成立。即1是A的特征值。

Continue reading

马尔可夫聚类算法

马尔可夫聚类算法(The Markov Cluster Algorithm, MCL)是一种快速可扩展的基于图的聚类算法。它的基本思想为:在一个稀疏图G中,如果某个区域A是稠密的(是一个聚类),则在A中随机游走k步,还在A内的概率很大,也就是说,A内的k步路径(k-length path)很多。所以我们可以在图中随机游走k步,如果某个区域连通的概率很大,则该区域是一个聚类。随机游走的下一步只和当前所处节点有关,也就是说这是一个马尔可夫的随机游走过程。

我们用一个例子来演示马尔可夫聚类算法的过程。

mcl-1 Continue reading