A discrete uncoupling process for finite spaces is introduced, called the Markov Cluster Process or the MCL process. The process is the engine for the graph clustering algorithm called the MCL algorithm. The MCL process takes a stochastic matrix as input, and then alternates expansion and inflation, each step defining a stochastic matrix in terms of the previous one. Expansion corresponds with taking the kth power of a stochastic matrix, where k ∈ N. Inflation corresponds with a parametrized operator Γr, r ≥ 0, that maps the set of (column) stochastic matrices onto itself. The image ΓrM is obtained by raising each entry in M to the rth power and rescaling each column to have sum 1 again. In practice the process converges very fast towards a limit that is invariant under both matrix multiplication and inflation, with quadratic convergence around the limit points. The heuristic behind the process is its expected behavior for (Markov) graphs possessing cluster structure. The process is typically applied to the matrix of random walks on a given graph G, and the connected components of (the graph associated with) the process limit generically allow a clustering interpretation of G. The limit is in general extremely sparse and iterands are sparse in a weighted sense, implying that the MCL algorithm is very fast and highly scalable. Several mathematical properties of the MCL process are established. Most notably, the process (and algorithm) iterands posses structural properties generalizing the mapping from process limits onto clusterings. The inflation operator Γr maps the class of matrices that are diagonally similar to a symmetric matrix onto itself. The phrase diagonally positive semi-definite (dpsd) is used for matrices that are diagonally similar to a positive semi-definite matrix. For r ∈ N and for M a stochastic dpsd matrix, the image ΓrM is again dpsd. Determinantal inequalities satisfied by a dpsd matrix M imply a natural ordering among the diagonal elements of M , generalizing the mapping of process limits onto clusterings. The spectrum of Γ∞M is of the form {0 n−k , 1 k }, where k is the number of endclasses of the ordering associated with M , and n is the dimension of M . This attests to the uncoupling effect of the inflation operator. Key words. stochastic uncoupling, graph clustering, Markov graph, Markov matrix, diagonal similarity, positive semi-definite matrices, circulant matrices AMS subject classifications. 68R10, 05C85, 05C90 DOI. 10.1137/040608635 1. Introduction. The subject of study is a parametrized algebraic process called the Markov Cluster Process (MCL process), which is the engine of a cluster algorithm for graphs, accordingly named the MCL algorithm. The algorithm is nothing more than a shell in which parameters are set, the MCL process is computed, and the result is interpreted. The process itself is defined on the space of stochastic matrices. Given a graph G, the algorithm employs the process by applying it to the matrix of random walks on G. The MCL algorithm [11, 12] was first applied in the field of protein family detection [18] . In this setting, proteins are nodes in a graph where the edge weights are derived from BLAST (Basic Local Alignment Search Tool) scores between protein amino-acid sequences. Following [18] , the algorithm has been widely applied in bioinformatics, in a diversity of settings and applications.
In REF the Markov Cluster Algorithm (mcl) is proposed for clustering weighted graphs.
Graph Clustering Via a Discrete Uncoupling Process
SIAM J. Matrix Analysis Applications
SIAM J. Matrix Analysis Applications
Computer Science Mathematics