MCL算法 马尔可夫聚类算法（英文）

Clustering on Graphs:

The Markov Cluster Algorithm

(MCL)

CS 595D Presentation

By Kathy Macropol

MCL Algorithm



Based on the PhD thesis by Stijn van Dongen

Van Dongen, S. (2000) Graph Clustering by Flow

Simulation. PhD Thesis, University of Utrecht, The

Outline

– Random Walks

– Markov Chains



MCL

– Basis

– Inflation Operator

– Algorithm

– Convergence



MCL Analysis

– Comparison to Other Graph Clustering Algorithms

Graph Clustering



Clustering – finding natural groupings of items.

Random Walks



Considering a graph, there will be many links within a

cluster, and fewer links between clusters.



This means if you were to start at a node, and then

randomly travel to a connected node, you’re more

likely to stay within a cluster than travel between.



This is what MCL (and several other clustering

algorithms) is based on.

– Other ways to consider graph clustering may include, for

example, looking for cliques. This tends to be sensitive to