New Cluster Algorithm for Graphs. Information Systems

摘要

A new cluster algorithm for graphs called the Markov Cluster Algorithm (MCL211u001ealgorithm) is introduced. The graphs may be both weighted (with nonnegative 211u001eweight) and directed. Let G be such a graph. The MCL algorithm simulates flow in 211u001eG by first identifying G in a canonical way with a Markov graph G1. Flow is then 211u001ealternatingly expanded and contracted, leading to a row of Markov Graphs Gi. The 211u001eexpansion step is done by computing higher step transition probabilities (TP's), 211u001ethe contraction step creates a new Markov graph by favoring high TP's and 211u001edemoting low TP's in a specific way. The heuristic underlying this approach is 211u001ethe expectation that flow between dense regions which are sparsely connected will 211u001eevaporate. The stable limits of the process are easily derived and in practice 211u001ethe algorithm converges very fast to such a limit, the structure of which has a 211u001egeneric interpretation as an overlapping clustering of the graph G. Overlap is 211u001elimited to cases where the input graph has a symmetric structure inducing it. The 211u001econtraction and expansion parameters of the algorithm influence the granularity 211u001eof the output. The algorithm is space and time efficient with a space + 211u001equality/time trade-off, works very well for a wide range of test cases, and lends 211u001eitself to drastic scaling. Experiments with a scaled C-implementation have been 211u001econducted on graphs having several tens of thousands of nodes. This report 211u001edescribes the algorithm, its complexity, and experimental results. The algorithm, 211u001eits complexity, and experimental results. The algorithm is introduced by first 211u001econsidering a generalization of generic single link clustering for graphs called-211u001ek-path clustering.