Paper: How to Take Advantage of the Limitations with Markov Clustering?--The Foundations of Branching Markov Clustering (BMCL)

ACL ID I08-2129
Title How to Take Advantage of the Limitations with Markov Clustering?--The Foundations of Branching Markov Clustering (BMCL)
Venue International Joint Conference on Natural Language Processing
Session Main Conference
Year 2008
Authors

In this paper, we propose a novel approach to optimally employing the MCL (Markov Cluster Algorithm) by “neutralizing” the trivial disadvantages acknowledged by its original proposer. Our BMCL (Branching Markov Clustering) algorithm makes it possible to subdivide a large core cluster into appropriately resized sub-graphs. Util- izing three corpora, we examine the effects of the BMCL which varies according to the curvature (clustering coefficient) of a hub in a network. 1 MCL limitations? 1.1 MCL and modularity Q The Markov Cluster Algorithm (MCL) (Van Don- gen, 2000) is well-recognized as an effective method of graph clustering. It involves changing the values of a transition matrix toward either 0 or 1 at each step in a random walk until the stochastic condition i...