Header Home Home Research News Events About CWI Library Publications Home Contact Intranet Search


full record

Performance criteria for graph clustering and Markov cluster experiments [ 2000 ]

CWI report R 0012


Rights: IPR: CWI
DB ID: 4461
File upload: Original publishers version
Digital object:http://oai.cwi.nl/oai/asset/4461/04461D.pdf (published version)
Persistent Identifier:urn:NBN:nl:ui:18-4461 (resolver: http://persistent-identifier.org/ - leads to CWI repository; use
http://persistent-identifier.org/?identifier=urn:nbn:nl:ui:18-4461 to refer to this repository item)
Open Access:A publicly accessible file is available in the CWI repository
Type: BibTeX type: techreport (report type: cwireport)
OAI type: preprint
Authors: Dongen, S. van (1)
Title: Performance criteria for graph clustering and Markov cluster experiments
Abstract: In~[1] a cluster algorithm for graphs was introduced called the Markov cluster algorithm or MCL~algorithm. The algorithm is based on simulation of (stochastic) flow in graphs by means of alternation of two operators, expansion and inflation. The results in~[2] establish an intrinsic relationship between the corresponding algebraic process (MCL~process) and cluster structure in the iterands and the limits of the process. Several kinds of experiments conducted with the MCL~algorithm are described here. Test cases with varying homogeneity characteristics are used to establish some of the particular strengths and weaknesses of the algorithm. In general the algorithm performs well, except for graphs which are very homogeneous (such as weakly connected grids) and for which the natural cluster diameter (i.e. the diameter of a subgraph induced by a natural cluster) is large. This can be understood in terms of the flow characteristics of the MCL~algorithm and the heuristic on which the algorithm is grounded. A generic performance criterion for clusterings of weighted graphs is derived, by a stepwise refinement of a simple and appealing criterion for simple graphs. The most refined criterion uses a particular Schur convex function, several properties of which are established. A metric is defined on the space of partitions, which is useful for comparing different clusterings of the same graph. The metric is compared with the metric known as the equivalence mismatch coefficient. The performance criterion and the metric are used for the quantitative measurement of experiments conducted with the MCL~algorithm on randomly generated test graphs with 10000 nodes. Scaling the MCL~algorithm requires a regime of pruning the stochastic matrices which need to be computed. The effect of pruning on the quality of the retrieved clusterings is also investigated. [1] A cluster algorithm for graphs. Technical report INS-R0010, National Research Institute for Mathematics and Computer Science in the Netherlands, Amsterdam, 2000. [2] A stochastic uncoupling process for graphs. Technical report INS-R0011, National Research Institute for Mathematics and Computer Science in the Netherlands, Amsterdam, 2000.
Language: en
MSC classification codes: 05A18;05B20;15B48;15B51;62H30;68R10;68T10;90C35
MSC classification description: Partitions of sets; Matrices (incidence, Hadamard, etc.); Positive matrices and their generalizations; cones of matrices; Stochastic matrices; Classification and discrimination; cluster analysis; Graph theory; Pattern recognition, speech recognition; Programming involving graphs or networks
Publisher: CWI
Size: 36p.
ISSN: 1386-3681
Series: Information Systems [INS]
Acronym: INS
Number: R 0012
Year: 2000
Pages: 1 - 36
Pages number: 36p.
ORA creation date: 2008-09-04 14:
ORA modification date: 20090918141610
Mutation date: 2009-09-18
Darenet: x
Related postprint:
Other relations:


Feedback | CWI Home page