Langue: en

Version: 27 Feb 2006 (ubuntu - 08/07/09)

Section: 7 (Divers)


    mclfaq - faqs and facts about the MCL cluster algorithm.

    MCL refers to the generic MCL algorithm and the MCL process on which the algorithm is based. mcl refers to the implementation. This FAQ answers questions related to both. In some places MCL is written where MCL or mcl can be read. This is the case for example in section 3, What kind of graphs. It should in general be obvious from the context.

    This FAQ does not begin to attempt to explain the motivation and mathematics behind the MCL algorithm - the internals are not explained. A broad view is given in faq 1.2, and see also faq 1.5 and section REFERENCES.

    Some additional sections preceed the actual faq entries. The TOC section contains a listing of all questions.

    The manual pages for all the utilities that come with mcl; refer to mclfamily(7) for an overview.

    mcl development is discussed on, list information is at

    See the REFERENCES Section for publications detailing the mathematics behind the MCL algorithm.

    0m 1

    General questions
    1m 1.1
    For whom is mcl and for whom is this FAQ?
    1m 1.2
    What is the relationship between the MCL process, the MCL algorithm, and the 'mcl' implementation?
    1m 1.3
    What do the letters MCL stand for?
    1m 1.4
    How could you be so feebleminded to use MCL as abbreviation? Why is it labeled 'Markov cluster' anyway?
    1m 1.5
    Where can I learn about the innards of the MCL algorithm/process?
    1m 1.6
    For which platforms is mcl available?
    1m 1.7
    How does mcl's versioning scheme work?

    0m 2

    Input format
    1m 2.1
    How can I get my data into the MCL matrix format?

    0m 3

    What kind of graphs
    1m 3.1
    What is legal input for MCL?
    1m 3.2
    What is sensible input for MCL?
    1m 3.3
    Does MCL work for weighted graphs?
    1m 3.4
    Does MCL work for directed graphs?
    1m 3.5
    Can MCL work for lattices / directed acyclic graphs / DAGs?
    1m 3.6
    Does MCL work for tree graphs?
    1m 3.7
    For what kind of graphs does MCL work well and for which does it not?
    1m 3.8
    What makes a good input graph? How do I construct the similarities? How to make them satisfy this Markov condition?
    1m 3.9
    My input graph is directed. Is that bad?
    1m 3.10
    Why does mcl like undirected graphs and why does it dislike uni-directed graphs so much?
    1m 3.11
    How do I check that my graph/matrix is symmetric/undirected?

    0m 4

    Speed and complexity
    1m 4.1
    How fast is mcl/MCL?
    1m 4.2
    What statistics are available?
    1m 4.3
    Does this implementation need to sort vectors?
    1m 4.4
    mcl does not compute the ideal MCL process!
    1m 4.5
    I've read elsewhere that MCL is slow [compared with XYZ]

    0m 5

    Resource tuning / accuracy
    1m 5.1
    What do you mean by resource tuning?
    1m 5.2
    How do I compute the maximum amount of RAM needed by mcl?
    1m 5.3
    How much does the mcl clustering differ from the clustering resulting from a perfectly computed MCL process?
    1m 5.4
    How do I know that I am using enough resources?
    1m 5.5
    Where is the mathematical analysis of this mcl pruning strategy?
    1m 5.6
    What qualitative statements can be made about the effect of pruning?
    1m 5.7
    At different high resource levels my clusterings are not identical. How can I trust the output clustering?

    0m 6

    Tuning cluster granularity
    1m 6.1
    How do I tune cluster granularity?
    1m 6.2
    The effect of inflation on cluster granularity.
    1m 6.3
    The effect of similarity distribution homogeneity on cluster granularity.
    1m 6.4
    The effect of initial centering on cluster granularity.

    0m 7

    Implementing the MCL algorithm
    1m 7.1
    How easy is it to implement the MCL algorithm?

    0m 8

    Cluster overlap / MCL iterand cluster interpretation
    1m 8.1
    1m 8.2
    Can the clusterings returned by mcl contain overlap?
    1m 8.3
    How do I obtain the clusterings associated with MCL iterands?

    0m 9

    1m 9.1
    How do I find the default settings of mcl?
    1m 9.2