Graph Clustering Via a Discrete Uncoupling Process

By Stijn van Dongen. SIAM Journal on Matrix Analysis and Applications, 2008

749 citations recorded by the source corpus.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/53f31f82557d66b6de06ed749f426f49a78d5435

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Non-overlapping community detection (2018, background): “At the heart of the Markov Cluster algorithm lies the idea of simulating a controlled flow through random walks in order to detect communities (Van Dongen 2008).”
Unsupervised Does Not Mean Uninterpretable: The Case for Word Sense Induction and Disambiguation (2017, neutral): “The choice of Chinese Whispers among other algorithms, such as HyperLex (V´eronis, 2004) or MCL (Van Dongen, 2008), was motivated by the absence of meta-parameters and its comparable performance on the WSI task to the state-of-the-art (Di Marco and Navigli, 2013).”
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks (2008, background): “See [14] for a more extensive discussion, and Section 2 for an overview of the unifying character of the Markov Stability framework, whose dynamical character allows the interpolation between the structural (edge-counting) measures and the spectral approach to community detection.”
Ironing out the wrinkles in the rare biosphere through improved OTU clustering (2010, neutral): “Using the Markov Cluster algorithm (Van Dongen, 2008) they identified several hundred OTUs in pairwise alignments of ~8000 300 nt reads from both the 5′ (4254 reads) and the 3′ end (4244 reads) of the Escherichia coli MG1655 rRNA gene.”
The power of protein interaction networks for associating genes with diseases (2010, neutral): “We compare approaches based on direct network neighbors (Oti et al., 2006, and neighborhood), unsupervised graph partitioning [graph summarization (GS; Navlakha et al., 2008) and Markov clustering (MCL; Van Dongen, 2008)], semi-supervised graph partitioning (VI-Cut; Navlakha et al., 2009a), random w”
Detecting overlapping protein complexes in protein-protein interaction networks (2012, methodology): “5 MCL The MCL algorithm [16] has a single parameter called inflation, which tunes the granularity of the clustering.”
Microbial Co-occurrence Relationships in the Human Microbiome (2012, methodology): “We clustered the network using the Markov cluster algorithm (MCL) [80] and computed network modularities for a range of inflation parameters.”
Disentangling Interactions in the Microbiome: A Network Perspective (2016, background): “Markov clustering algorithm (MCL) tries to simulate a stochastic flow within the network structure, strengthening the flow where nodes are highly interconnected and weakening it in other regions until the flow process stabilizes [74].”
Communication optimal parallel multiplication of sparse random matrices (2013, methodology): “Generalized sparse matrix-matrix multiplication is used as a subroutine in algebraic multigrid [5], graph clustering [29] and contraction [16], quantum chemistry [30], and parsing context-free languages [23].”
The Combinatorial BLAS: design, implementation, and applications (2011, background): “Markov clustering (MCL) (Van Dongen, 2008) is a flowbased graph clustering algorithm that has been popular in computational biology, among other fields.”