DOKK / manpages / debian 11 / mcl-doc / mclfaq.7.en
MCL FAQ(7) MISCELLANEOUS MCL FAQ(7)



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 precede 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.

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



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

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

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

4 Speed and complexity
4.1 How fast is mcl/MCL?
4.2 What statistics are available?
4.3 Does this implementation need to sort vectors?
4.4 mcl does not compute the ideal MCL process!

5 Comparison with other algorithms
5.1 I've read someplace that XYZ is much better than MCL
5.2 I've read someplace that MCL is slow [compared with XYZ]

6 Resource tuning / accuracy
6.1 What do you mean by resource tuning?
6.2 How do I compute the maximum amount of RAM needed by mcl?
6.3 How much does the mcl clustering differ from the clustering resulting from a perfectly computed MCL process?
6.4 How do I know that I am using enough resources?
6.5 Where is the mathematical analysis of this mcl pruning strategy?
6.6 What qualitative statements can be made about the effect of pruning?
6.7 At different high resource levels my clusterings are not identical. How can I trust the output clustering?

7 Tuning cluster granularity
7.1 How do I tune cluster granularity?
7.2 The effect of inflation on cluster granularity.
7.3 The effect of node degrees on cluster granularity.
7.4 The effect of edge weight differentiation on cluster granularity.

8 Implementing the MCL algorithm
8.1 How easy is it to implement the MCL algorithm?

9 Cluster overlap / MCL iterand cluster interpretation
9.1 Introduction
9.2 Can the clusterings returned by mcl contain overlap?
9.3 How do I obtain the clusterings associated with MCL iterands?

10 Miscellaneous
10.1 How do I find the default settings of mcl?
10.2 What's next?




General questions


1.1 For whom is mcl and for whom is this FAQ?

For everybody with an appetite for graph clustering. Regarding the FAQ, I have kept the amount of mathematics as low as possible, as far as matrix analysis is concerned. Inevitably, some terminology pops up and some references are made to the innards of the MCL algorithm, especially in the section on resources and accuracy. Graph terminology is used somewhat more carelessly though. The future might bring definition entries, right now you have to do without. Mathematically inclined people may be interested in the pointers found in the REFERENCES section.

Given this mention of mathematics, let me point out this one time only that using mcl is extremely straightforward anyway. You need only mcl and an input graph (refer to the mcl manual page), and many people trained in something else than mathematics are using mcl happily.

1.2 What is the relationship between the MCL process, the MCL algorithm, and the 'mcl' implementation?

mcl is what you use for clustering. It implements the MCL algorithm, which is a cluster algorithm for graphs. The MCL algorithm is basically a shell in which the MCL process is computed and interpreted. I will describe them in the natural, reverse, order.

The MCL process generates a sequence of stochastic matrices given some initial stochastic matrix. The elements with even index are obtained by expanding the previous element, and the elements with odd index are obtained by inflating the previous element given some inflation constant. Expansion is nothing but normal matrix squaring, and inflation is a particular way of rescaling the entries of a stochastic matrix such that it remains stochastic.

The sequence of MCL elements (from the MCL process) is in principle without end, but what happens is that the elements converge to some specific kind of matrix, called the limit of the process. The heuristic underlying MCL predicts that the interaction of expansion with inflation will lead to a limit exhibiting cluster structure in the graph associated with the initial matrix. This is indeed the case, and several mathematical results tie MCL iterands and limits and the MCL interpretation together (REFERENCES).

The MCL algorithm is simply a shell around the MCL process. It transforms an input graph into an initial matrix suitable for starting the process. It sets inflation parameters and stops the MCL process once a limit is reached, i.e. convergence is detected. The result is then interpreted as a clustering.

The mcl implementation supplies the functionality of the MCL algorithm, with some extra facilities for manipulation of the input graph, interpreting the result, manipulating resources while computing the process, and monitoring the state of these manipulations.

1.3 What do the letters MCL stand for?

For Markov Cluster. The MCL algorithm is a cluster algorithm that is basically a shell in which an algebraic process is computed. This process iteratively generates stochastic matrices, also known as Markov matrices, named after the famous Russian mathematician Andrei Markov.

1.4 How could you be so feebleminded to use MCL as abbreviation? Why is it labeled 'Markov cluster' anyway?

Sigh. It is a widely known fact that a TLA or Three-Letter-Acronym is the canonical self-describing abbreviation for the name of a species with which computing terminology is infested (quoted from the Free Online Dictionary of Computing). Back when I was thinking of a nice tag for this cute algorithm, I was totally unaware of this. I naturally dismissed MC (and would still do that today). Then MCL occurred to me, and without giving it much thought I started using it. A Google search (or was I still using Alta-Vista back then?) might have kept me from going astray.

Indeed, MCL is used as a tag for Macintosh Common Lisp, Mission Critical Linux, Monte Carlo Localization, MUD Client for Linux, Movement for Canadian Literacy, and a gazillion other things - refer to the file mclmcl.txt. Confusing. It seems that the three characters MCL possess otherworldly magical powers making them an ever so strange and strong attractor in the space of TLAs. It probably helps that Em-See-Ell (Em-Say-Ell in Dutch) has some rhythm to it as well. Anyway MCL stuck, and it's here to stay.

On a more general level, the label Markov Cluster is not an entirely fortunate choice either. Although phrased in the language of stochastic matrices, MCL theory bears very little relation to Markov theory, and is much closer to matrix analysis (including Hilbert's distance) and the theory of dynamical systems. No results have been derived in the latter framework, but many conjectures are naturally posed in the language of dynamical systems.

1.5 Where can I learn about the innards of the MCL algorithm/process?

Currently, the most basic explanation of the MCL algorithm is found in the technical report [2]. It contains sections on several other (related) subjects though, and it assumes some working knowledge on graphs, matrix arithmetic, and stochastic matrices.

1.6 For which platforms is mcl available?

It should compile and run on virtually any flavour of UNIX (including Linux and the BSD variants of course). Following the instructions in the INSTALL file shipped with mcl should be straightforward and sufficient. Courtesy to Joost van Baal who completely autofooled mcl.

Building MCL on Wintel (Windows on Intel chip) should be straightforward if you use the full suite of cygwin tools. Install cygwin if you do not have it yet. In the cygwin shell, unpack mcl and simply issue the commands ./configure, make, make install, i.e. follow the instructions in INSTALL.

This MCL implementation should also build successfully on Mac OS X.

1.7 How does mcl's versioning scheme work?

The current setup, which I hope to continue, is this. All releases are identified by a date stamp. For example 02-095 denotes day 95 in the year 2002. This date stamp agrees (as of April 2000) with the (differently presented) date stamp used in all manual pages shipped with that release. For example, the date stamp of the FAQ you are reading is 16 May 2014, which corresponds with the MCL stamp 14-137. The Changelog file contains a list of what's changed/added with each release. Currently, the date stamp is the primary way of identifying an mcl release. When asked for its version by using --version, mcl outputs both the date stamp and a version tag (see below).


Input format


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

This is described in the protocols manual page.


What kind of graphs


3.1 What is legal input for MCL?

Any graph (encoded as a matrix of similarities) that is nonnegative, i.e. all similarities are greater than or equal to zero.

3.2 What is sensible input for MCL?

Graphs can be weighted, and they should preferably be symmetric. Weights should carry the meaning of similarity, not distance. These weights or similarities are incorporated into the MCL algorithm in a meaningful way. Graphs should certainly not contain parts that are (almost) cyclic, although nothing stops you from experimenting with such input.

3.3 Does MCL work for weighted graphs?

Yes, unequivocally. They should preferably be symmetric/undirected though. See entries 3.7 and 3.8.

3.4 Does MCL work for directed graphs?

Maybe, with a big caveat. See entries 3.8 and 3.9.

3.5 Can MCL work for lattices / directed acyclic graphs / DAGs?

Such graphs [term] can surely exhibit clear cluster structure. If they do, there is only one way for mcl to find out. You have to change all arcs to edges, i.e. if there is an arc from i to j with similarity s(i,j) - by the DAG property this implies s(j,i) = 0 - then make s(j,i) equal to s(i,j).

This may feel like throwing away valuable information, but in truth the information that is thrown away (direction) is not informative with respect to the presence of cluster structure. This may well deserve a longer discussion than would be justified here.

If your graph is directed and acyclic (or parts of it are), you can transform it before clustering with mcl by using -tf '#max()', e.g.




   mcl YOUR-GRAPH -I 3.0 -tf '#max()'



3.6 Does MCL work for tree graphs?


Nah, I don't think so. More info at entry 3.7. You could
    consider the Strahler number, which is numerical measure of branching
    complexity.


3.7 For what kind of graphs does MCL work well and for
    which does it not?


Graphs in which the diameter [term] of (subgraphs induced by)
    natural clusters is not too large. Additionally, graphs should preferably be
    (almost) undirected (see entry below) and not so sparse that the cardinality
    of the edge set is close to the number of nodes.


A class of such very sparse graphs is that of tree graphs. You
    might look into graph visualization software and research if you are
    interested in decomposing trees into 'tight' subtrees.


The diameter criterion could be violated by neighbourhood graphs
    derived from vector data. In the specific case of 2 and 3 dimensional data,
    you might be interested in image segmentation and boundary
    detection, and for the general case there is a host of other algorithms
    out there. [add]


In case of weighted graphs, the notion of diameter is
    sometimes not applicable. Generalizing this notion requires inspecting the
    mixing properties of a subgraph induced by a natural cluster
    in terms of its spectrum. However, the diameter statement is something
    grounded on heuristic considerations (confirmed by practical evidence [4])
    to begin with, so you should probably forget about mixing properties.


3.8 What makes a good input graph? How do I
    construct the similarities? How to make them satisfy this Markov
    condition?


To begin with the last one: you need not and must not make
    the input graph such that it is stochastic aka Markovian [term]. What you
    need to do is make a graph that is preferably symmetric/undirected, i.e.
    where s(i,j) = s(j,i) for all nodes i and j. It need not be perfectly
    undirected, see the following faq for a discussion of that. mcl will
    work with the graph of random walks that is associated with your input
    graph, and that is the natural state of affairs.


The input graph should preferably be honest in the sense that if
    s(x,y)=N and s(x,z)=200N (i.e. the similarities differ by a
    factor 200), then this should really reflect that the similarity of y to
    x is neglectible compared with the similarity of z to x.


For the rest, anything goes. Try to get a feeling by
    experimenting. Sometimes it is a good idea to filter out high-frequency
    and/or low-frequency data, i.e. nodes with either very many neighbours or
    extremely few neighbours.


3.9 My input graph is directed. Is that bad?


It depends. The class of directed graphs can be viewed as a
    spectrum going from undirected graphs to uni-directed graphs.
    Uni-directed is terminology I am inventing here, which I define as
    the property that for all node pairs i, j, at least one of s(i,j) or s(j,i)
    is zero. In other words, if there is an arc going from i to j in a
    uni-directed graph, then there is no arc going from j to i. I call a node
    pair i, j, almost uni-directed if s(i,j) << s(j,i) or vice
    versa, i.e. if the similarities differ by an order of magnitude.


If a graph does not have (large) subparts that are (almost)
    uni-directed, have a go with mcl. Otherwise, try to make your graph less
    uni-directed. You are in charge, so do anything with your graph as you see
    fit, but preferably abstain from feeding mcl uni-directed graphs.


3.10 Why does mcl like undirected graphs and why does
    it dislike uni-directed graphs so much?


Mathematically, the mcl iterands will be nice when the
    input graph is symmetric, where nice is in this case diagonally
    symmetric to a semi-positive definite matrix (ignore as needed).
    For one thing, such nice matrices can be interpreted as clusterings in a way
    that generalizes the interpretation of the mcl limit as a clustering (if you
    are curious to these intermediate clusterings, see faq
    entry 9.3). See the REFERENCES section for pointers to
    mathematical publications.


The reason that mcl dislikes uni-directed graphs is not very mcl
    specific, it has more to do with the clustering problem itself. Somehow,
    directionality thwarts the notion of cluster structure. [add].


3.11 How do I check that my graph/matrix is
    symmetric/undirected?


Whether your graph is created by third-party software or by custom
    software written by someone you know (e.g. yourself), it is advisable to
    test whether the software generates symmetric matrices. This can be done as
    follows using the mcxi utility, assuming that you want to test the
    matrix stored in file matrix.mci. The mcxi utility should be
    available on your system if mcl was installed in the normal
  way.



  




mcxi /matrix.mci lm tp -1 mul add /check wm






This loads the graph/matrix stored in matrix.mci into
    mcxi's memory with the mcxi
    lm primitive. - the leading slash is how strings are
    introduced in the stack language interpreted by mcxi. The
    transpose of that matrix is then pushed on the stack with the
    tp primitive and multiplied by minus one. The two
    matrices are added, and the result is written to the file
    check. The transposed matrix is the mirrored version of the
    original matrix stored in matrix.mci. If a graph/matrix is
    undirected/symmetric, the mirrored image is necessarily the same, so
    if you subtract one from the other it should yield an all zero
    matrix.


Thus, the file check should look like
  this:



  




(mclheader
mcltype matrix
dimensions <num>x<num>
)
(mclmatrix
begin
)






Where <num> is the same as in the file matrix.mci. If
    this is not the case, find out what's prohibiting you from feeding mcl
    symmetric matrices. Note that any nonzero entries found in the matrix stored
    as check correspond to node pairs for which the arcs in the two
    possible directions have different weight.



  

  Speed and complexity



  

  4.1 How fast is mcl/MCL?


It's fast - here is how and why. Let N be the number of nodes
    in the input graph. A straigtforward implementation of MCL will have
    time and space complexity respecively O(N^3) (i.e. cubic in N)
    and O(N^2) (quadratic in N). So you don't want one of those.


mcl implements a slightly perturbed version of the MCL
    process, as discussed in section Resource tuning / accuracy. Refer to
    that section for a more extensive discussion of all the aspects involved.
    This section is only concerned with the high-level view of things and
    the nitty gritty complexity details.


While computing the square of a matrix (the product of that matrix
    with itself), mcl keeps the matrix sparse by allowing a certain maximum
    number of nonzero entries per stochastic column. The maximum is one of the
    mcl parameters, and it is typically set somewhere between 500 and 1500. Call
    the maximum K.


mcl's time complexity is governed by the complexity of matrix
    squaring. There are two sub-algorithms to consider. The first is the
    algorithm responsible for assembling a new vector during matrix
    multiplication. This algorithm has worst case complexity O(K^2).
    The pruning algorithm (which uses heap selection) has worst case
    complexity O(L*log(K)), where L is how large a newly computed
    matrix column can get before it is reduced to at most K entries.
    L is bound by the smallest of the two numbers
    N and K^2 (the square of K), but on average
    L will be much smaller than that, as the presence of cluster
    structure aids in keeping the factor L low. [Related to this
    is the fact that clustering algorithms are actually used to compute
    matrix splittings that minimize the number of cross-computations when
    carrying out matrix multiplication among multiple processors.]
    In actual cases of heavy usage, L is of order in the tens of
    thousands, and K is in the order of several hundreds up to a
    thousand.


It is safe to say that in general the worst case complexity of mcl
    is of order O(N*K^2); for extremely tight and dense graphs this might become
    O(N*N*log(K)). Still, these are worst case estimates, and observed running
    times for actual usage are much better than that. (refer to
  faq 4.2).


In this analysis, the number of iterations required by mcl was not
    included. It is nearly always far below 100. Only the first few (less than
    ten) iterations are genuinely time consuming, and they are usually
    responsible for more than 95 percent of the running time.


The process of removing the smallest entries of a vector is called
    pruning. mcl outputs a summary of this once it is done. More information is
    provided in the pruning section of the mcl manual and
    Section 6 in this FAQ.


The space complexity is of order O(N*K).


4.2 What statistics are available?


Few. Some experiments are described in [4], and [5] mentions large
    graphs being clustered in very reasonable time. In protein clustering,
    mcl has been applied to graphs with up to one million nodes, and on
    high-end hardware such graphs can be clustered within a few hours.


4.3 Does this implementation need to sort
  vectors?


No, it does not. You might expect that one needs to sort a vector
    in order to obtain the K largest entries, but a simpler mechanism
    called heap selection does the job nicely. Selecting
    the K largest entries from a set of L by sorting would
    require O(L*log(L)) operations; heap selection requires
    O(L*log(K)) operations. Alternatively, the K largest
    entries can be also be determined in O(N) + O(K log(K))
    asymptotic time by using partition selection (more
    here and there). It is possible to
    enable this mode of operaton in mcl with the option
    --partition-selection. However, benchmarking so far has
    shown this to be equivalent in speed to heap selection. This is
    explained by the bounded nature of K and L in
    practice.


4.4 mcl does not compute the ideal MCL process!


Indeed it does not. What are the ramifications? Several entries in
    section Resource tuning / accuracy discuss this issue. For a
    synopsis, consider two ends of a spectrum.


On the one end, a graph that has very strong cluster structure,
    with clearly (and not necessarity fully) separated clusters. This mcl
    implementation will certainly retrieve those clusters if the graphs falls
    into the category of graphs for which mcl is applicable. On the other
    end, consider a graph that has only weak cluster structure superimposed on a
    background of a more or less random graph. There might sooner be a
    difference between the clustering that should ideally result and the one
    computed by mcl. Such a graph will have a large number of whimsical nodes
    that might end up either here or there, nodes that are of a peripheral
    nature, and for which the (cluster) destination is very sensitive to
    fluctutations in edge weights or algorithm parametrizations (any algorithm,
    not just mcl).


In short, the perturbation effect of the pruning process applied
    by mcl is a source of noise. It is small compared to the effect of changing
    the inflation parametrization or perturbing the edge weights. If the change
    is larger, this is because the computed process tends to converge
    prematurely, leading to finer-grained clusterings. As a result the
    clustering will be close to a subclustering of the clustering
    resulting from more conservative resource settings, and in that respect be
    consistent. All this can be measured using the program clm dist. It
    is possible to offset such a change by slightly lowering the inflation
    parameter.


There is the issue of very large and very dense graphs. The act of
    pruning will have a larger impact as graphs grow larger and denser.
    Obviously, mcl will have trouble dealing with such very large and very dense
    graphs - so will other methods.


Finally, there is the engineering approach, which offers the
    possibility of pruning a whole lot of speculation. Do the experiments with
    mcl, try it out, and see what's there to like and dislike.



  

  Comparison with other algorithms



  

  5.1 I've read someplace that XYZ is much better than MCL


XYZ might well be the bees knees of all things clustering. Bear in
    mind though that comparing cluster algorithms is a very tricky affair. One
    particular trap is the following. Sometimes a new cluster algorithm is
    proposed based on some optimization criterion. The algorithm is then
    compared with previous algorithms (e.g. MCL). But how to compare? Quite
    often the comparison will be done by computing a criterion and astoundingly,
    quite often the chosen criterion is simply the optimization criterion again.
    Of course XYZ will do very well. It would be a very poor algorithm it
    if did not score well on its own optimization criterion, and it would be a
    very poor algorithm if it did not perform better than other algorithms which
    are built on different principles.


There are some further issues that have to be considered here.
    First, there is not a single optimization criterion that fully captures the
    notion of cluster structure, let alone best cluster structure. Second,
    leaving optimization approaches aside, it is not possible to speak of a best
    clustering. Best always depends on context - application field, data
    characteristics, scale (granularity), and practitioner to name but a few
    aspects. Accordingly, the best a clustering algorithm can hope for is to be
    a good fit for a certain class of problems. The class should not be too
    narrow, but no algorithm can cater for the broad spectre of problems for
    which clustering solutions are sought. The class of problems to which MCL is
    applicable is discussed in section What kind of graphs.


5.2 I've read someplace that MCL is slow [compared with
    XYZ]


Presumably, they did not know mcl, and did not read the parts in
    [1] and [2] that discuss implementation. Perhaps they assume or insist that
    the only way to implement MCL is to implement the ideal process. And there
    is always the genuine possibility of a really stupifyingly fast
    algorithm. It is certainly not the case that MCL has a time complexity of
    O(N^3) as is sometimes erroneously stated.



  

  Resource tuning / accuracy



  

  6.1 What do you mean by resource tuning?


mcl computes a process in which stochastic matrices are
    alternately expanded and inflated. Expansion is nothing but standard matrix
    multiplication, inflation is a particular way of rescaling the matrix
    entries.


Expansion causes problems in terms of both time and space. mcl
    works with matrices of dimension N, where N is the number of nodes in
    the input graph. If no precautions are taken, the number of entries in the
    mcl iterands (which are stochastic matrices) will soon approach the square
    of N. The time it takes to compute such a matrix will be
    proportional to the cube of N. If your input graph has 100.000
    nodes, the memory requirements become infeasible and the time requirements
    become impossible.


What mcl does is perturbing the process it computes a little by
    removing the smallest entries - it keeps its matrices sparse. This is
    a natural thing to do, because the matrices are sparse in a weighted sense
    (a very high proportion of the stochastic mass is contained in relatively
    few entries), and the process converges to matrices that are extremely
    sparse, with usually no more than N entries. It is thus known that
    the MCL iterands are sparse in a weighted sense and are usually very
    close to truly sparse matrices. The way mcl perturbs its matrices is
    by the strategy of pruning, selection, and recovery that is
    extensively described in the mcl manual page.
    The question then is: What is the effect of this perturbation on
    the resulting clustering, i.e. how would the clustering resulting
    from a perfectly computed mcl process compare with the
    clustering I have on disk? Faq entry 6.3
    discusses this issue.


The amount of resources used by mcl is bounded in terms of
    the maximum number of neighbours a node is allowed to have during all
    computations. Equivalently, this is the maximum number of nonzero entries a
    matrix column can possibly have. This number, finally, is the maximum of the
    the values corresponding with the -S and -R options. The
    latter two are listed when using the -z option (see
  faq 10.1).


6.2 How do I compute the maximum amount of RAM needed by
    mcl?


It is roughly equal to



  




2 * s * K * N






bytes, where 2 is the number of matrices held in memory by
    mcl, s is the size of a single cell (c.q. matrix entry or node/arc
    specification), N is the number of nodes in the input graph, and
    where K is the maximum of the values corresponding with the -S
    and -R options (and this assumes that the average node degree in the
    input graph does not exceed K either). The value of s can be found
    by using the -z option. It is listed in one of the
    first lines of the resulting output. s equals the size of an int plus
    the size of a float, which will be 8 on most systems. The estimate
    above will in most cases be way too pessimistic (meaning you do not
    need that amount of memory).


The -how-much-ram option is provided by mcl for computing
    the bound given above. This options takes as argument the number of nodes in
    the input graph.


The theoretically more precise upper bound is slightly larger due
    to overhead. It is something like



  




( 2 * s * (K + c)) * N






where c is 5 or so, but one should not pay attention to such a
    small difference anyway.


6.3 How much does the mcl clustering differ from the
    clustering resulting from a perfectly computed MCL process?


For graphs with up until a few thousand nodes a perfectly
    computed MCL process can be achieved by abstaining from pruning and
    doing full-blown matrix arithmetic. Of course, this still leaves the issue
    of machine precision, but let us wholeheartedly ignore that.


Such experiments give evidence (albeit incidental) that pruning is
    indeed really what it is thought to be - a small perturbation. In many
    cases, the 'approximated' clustering is identical to the 'exact' clustering.
    In other cases, they are very close to each other in terms of the metric
    split/join distance as computed by clm dist. Some experiments
    with randomly generated test graphs, clustering, and pruning are described
    in [4].


On a different level of abstraction, note that perturbations of
    the inflation parameter will also lead to perturbations in the resulting
    clusterings, and surely, large changes in the inflation parameter will in
    general lead to large shifts in the clusterings. Node/cluster pairs that are
    different for the approximated and the exact clustering will very likely
    correspond with nodes that are in a boundary region between two or more
    clusters anyway, as the perturbation is not likely to move a node from one
    core of attraction to another.


Faq entry 6.6 has more to say about this subject.


6.4 How do I know that I am using enough
  resources?


In mcl parlance, this becomes how do I know that my
    -scheme parameter is high enough or more elaborately how do
    I know that the values of the {-P, -S, -R, -pct} combo are high
    enough?


There are several aspects. First, watch the jury marks
    reported by mcl when it's done. The jury marks are three grades, each
    out of 100. They indicate how well pruning went. If the marks are in the
    seventies, eighties, or nineties, mcl is probably doing fine. If they are in
    the eighties or lower, try to see if you can get the marks higher by
    spending more resources (e.g. increase the parameter to the -scheme
    option).


Second, you can do multiple mcl runs for different resource
    schemes, and compare the resulting clusterings using clm dist. See
    the clmdist manual for a case study.


6.5 Where is the mathematical analysis of this mcl
    pruning strategy?


There is none. [add]


Ok, the next entry gives an engineer's rule of thumb.


6.6 What qualitative statements can be made about the
    effect of pruning?


The more severe pruning is, the more the computed process will
    tend to converge prematurely. This will generally lead to finer-grained
    clusterings. In cases where pruning was severe, the mcl clustering
    will likely be closer to a clustering ideally resulting from another MCL
    process with higher inflation value, than to the clustering ideally
    resulting from the same MCL process. Strong support for this is found in a
    general observation illustrated by the following example. Suppose u is a
    stochastic vector resulting from expansion:



  




u   =  0.300 0.200 0.200 0.100 0.050 0.050 0.050 0.050






Applying inflation with inflation value 2.0 to u gives



  




v   =  0.474 0.211 0.211 0.053 0.013 0.013 0.013 0.013






Now suppose we first apply pruning to u such that the 3 largest
    entries 0.300, 0.200 and 0.200 survive, throwing away 30 percent of the
    stochastic mass (which is quite a lot by all means). We rescale those three
    entries and obtain



  




u'  =  0.429 0.286 0.286 0.000 0.000 0.000 0.000 0.000






Applying inflation with inflation value 2.0 to u' gives



  




v'  =  0.529 0.235 0.235 0.000 0.000 0.000 0.000 0.000






If we had applied inflation with inflation value 2.5 to u, we
    would have obtained



  




v'' =  0.531 0.201 0.201 0.038 0.007 0.007 0.007 0.007






The vectors v' and v'' are much closer to each other than the
    vectors v' and v, illustrating the general idea.


In practice, mcl should (on average) do much better than in
    this example.


6.7 At different high resource levels my clusterings are
    not identical. How can I trust the output clustering?


Did you read all other entries in this section? That should have
    reassured you somewhat, except perhaps for Faq answer 6.5.


You need not feel uncomfortable with the clusterings still being
    different at high resource levels, if ever so slightly. In all likelihood,
    there are anyway nodes which are not in any core of attraction, and that are
    on the boundary between two or more clusterings. They may go one way or
    another, and these are the nodes which will go different ways even at high
    resource levels. Such nodes may be stable in clusterings obtained for lower
    inflation values (i.e. coarser clusterings), in which the different clusters
    to which they are attracted are merged.


By the way, you do know all about clm dist, don't
    you? Because the statement that clusterings are not identical should be
    quantified: How much do they differ? This issue is discussed
    in the clm dist manual page - clm dist gives you a
    robust measure for the distance (dissimilarity) between two clusterings.


There are other means of gaining trust in a clustering, and there
    are different issues at play. There is the matter of how accurately this
    mcl computed the mcl process, and there is the matter of how well the
    chosen inflation parameter fits the data. The first can be judged by looking
    at the jury marks (faq 6.4) and applying clm dist to
    different clusterings. The second can be judged by measurement (e.g. use
    clm info) and/or inspection (use your judgment).



  

  Tuning cluster granularity



  

  7.1 How do I tune cluster granularity?


There are several ways for influencing cluster granularity. These
    ways and their relative merits are successively discussed below. Reading
    clmprotocols(5) is also a good idea.


7.2 The effect of inflation on cluster
  granularity.


The main handle for changing inflation is the -I option.
    This is also the principal handle for regulating cluster granularity.
    Unless you are mangling huge graphs it could be the only mcl option
    you ever need besides the output redirection option -o.


Increasing the value of -I will increase cluster
    granularity. Conceivable values are from 1.1 to 10.0 or so, but the range of
    suitable values will certainly depend on your input graph. For many graphs,
    1.1 will be far too low, and for many other graphs, 8.0 will be far too
    high. You will have to find the right value or range of values by
    experimenting, using your judgment, and using measurement tools such as
    clm dist and clm info. A good set of values to
    start with is 1.4, 2 and 6.


7.3 The effect of node degrees on cluster
    granularity.


Preferably the network should not have nodes of very high degree,
    that is, with exorbitantly many neighbours. Such nodes tend to obscure
    cluster structure and contribute to coarse clusters. The ways to combat this
    using mcl and sibling programs are documented in
    clmprotocols(5). Briefly, they are the transformations #knn() and
    #ceilnb() available to mcl, mcx alter and several
    more programs.


7.4 The effect of edge weight differentiation on cluster
    granularity.


How similarities in the input graph were derived, constructed,
    adapted, filtered (et cetera) will affect cluster granularity. It is
    important that the similarities are honest; refer to
  faq 3.8.


Another issue is that homogeneous similarities tend to result in
    more coarse-grained clusterings. You can make a set of similarities more
    homogeneous by applying some function to all of them, e.g. for all pairs of
    nodes (x y) replace S(x,y) by the square root, the logarithm, or some other
    convex function. Note that you need not worry about scaling, i.e. the
    possibly large changes in magnitude of the similarities. MCL is not affected
    by absolute magnitudes, it is only affected by magnitudes taken relative to
    each other.


As of version 03-154, mcl supports the pre-inflation
    -pi f option. Make a graph more homogeneous with
    respect to the weight function by using -pi with argument f
    somewhere in the interval [0,1] - 0.5 can be considered a reasonable first
    try. Make it less homogeneous by setting f somewhere in the interval
    [1,10]. In this case 3 is a reasonable starting point.



  

  Implementing the MCL algorithm



  

  8.1 How easy is it to implement the MCL algorithm?


Very easy, if you will be doing small graphs only, say up to a few
    thousand entries at most. These are the basic ingredients:



  

  o Adding loops to the input graph, conversion to a stochastic matrix.
  

  

  

  o Matrix multiplication and matrix inflation.
  

  

  

  o The interpretation function mapping MCL limits onto clusterings.
  




These must be wrapped in a program that does graph input and
    cluster output, alternates multiplication (i.e. expansion) and inflation in
    a loop, monitors the matrix iterands thus found, quits the loop when
    convergence is detected, and interprets the last iterand.


Implementing matrix muliplication is a standard exercise.
    Implementing inflation is nearly trivial. The hardest part may actually be
    the interpretation function, because you need to cover the corner cases of
    overlap and attractor systems of cardinality greater than one. Note that MCL
    does not use intricate and expensive operations such as matrix inversion or
    matrix reductions.


In Mathematica or Maple, mcl should be doable in at most 100 lines
    of code. For perl you may need twice that amount. In lower level languages
    such as C or Fortran a basic MCL program may need a few hundred lines, but
    the largest part will probably be input/output and interpretation.


To illustrate all these points, mcl now ships with minimcl,
    a small perl script that implements mcl for educational purposes. Its
    structure is very simple and should be easy to follow.


Implementing the basic MCL algorithm makes a nice programming
    exercise. However, if you need an implementation that scales to several
    hundreds of thousands of nodes and possibly beyond, then your duties become
    much heavier. This is because one needs to prune MCL iterands (c.q.
    matrices) such that they remain sparse. This must be done carefully and
    preferably in such a way that a trade-off between speed, memory usage, and
    potential losses or gains in accuracy can be controlled via monitoring and
    logging of relevant characteristics. Some other points are i) support for
    threading via pthreads, openMP, or some other parallel programming API. ii)
    a robust and generic interpretation function is written in terms of weakly
    connected components.



  

  Cluster overlap / MCL iterand cluster interpretation



  

  9.1 Introduction


A natural mapping exists of MCL iterands to DAGs (directed acyclic
    graphs). This is because MCL iterands are generally diagonally positive
    semi-definite - see [3]. Such a DAG can be interpreted as a clustering,
    simply by taking as cores all endnodes (sinks) of the DAG, and by attaching
    to each core all the nodes that reach it. This procedure may result in
    clusterings containing overlap.


In the MCL limit, the associated DAG has in general a very
    degenerated form, which induces overlap only on very rare occasions (see
    faq entry 9.2).


Interpreting mcl iterands as clusterings may well be
    interesting. Few experiments have been done so far. It is clear though that
    early iterands generally contain the most overlap (when interpreted as
    clusterings). Overlap dissappears soon as the iterand index increases. For
    more information, consult the other entries in this section and the
    clmimac manual page.


9.2 Can the clusterings returned by mcl contain
    overlap?


No. Clusterings resulting from the abstract MCL algorithm may in
    theory contain overlap, but the default behaviour in mcl is to remove
    it should it occur, by allocating the nodes in overlap to the first cluster
    in which they are seen. mcl will warn you if this occurs. This
    behaviour is switched off by supplying --keep-overlap=yes.


Do note that overlap is mostly a theoretical possibility. It is
    conjectured that it requires the presence of very strong symmetries in the
    input graph, to the extent that there exists an automorphism of
    the input graph mapping the overlapping part onto itself.


It is possible to construct (highly symmetric) input graphs
    leading to cluster overlap. Examples of overlap in which a few nodes are
    involved are easy to construct; examples with many nodes are exceptionally
    hard to construct.


Clusterings associated with intermediate/early MCL iterands may
    very well contain overlap, see the introduction in this section and
    other entries.


9.3 How do I obtain the clusterings associated with MCL
    iterands?


There are two options. If you are interested in clusterings
    containing overlap, you should go for the second. If not, use the first, but
    beware that the resulting clusterings may contain overlap.


The first solution is to use -dump cls
    (probably in conjunction with either -L or -dumpi in order to
    limit the number of matrices written). This will cause mcl to write
    the clustering generically associated with each iterand to file. The
    -dumpstem option may be convenient as well.


The second solution is to use the -dump ite
    option (-dumpi and -dumpstem may be of use again). This will
    cause mcl to write the intermediate iterands to file. After that, you
    can apply clm imac (interpret matrix as clustering) to those
    iterands. clm imac has a -strict parameter which affects the
    mapping of matrices to clusterings. It takes a value between 0.0 and 1.0 as
    argument. The default is 0.001 and corresponds with promoting overlap.
    Increasing the -strict value will generally result in clusterings
    containing less overlap. This will have the largest effect for early
    iterands; its effect will diminish as the iterand index increases.


When set to 0, the -strict parameter results in the
    clustering associated with the DAG associated with an MCL iterand as
    described in [3]. This DAG is pruned (thus possibly resulting in less
    overlap in the clustering) by increasing the -strict parameter.
  [add]



  

  Miscellaneous



  

  10.1 How do I find the default settings of mcl?


Use -z to find out the actual settings - it shows the
    settings as resulting from the command line options (e.g. the default
    settings if no other options are given).


10.2 What's next?


I'd like to port MCL to cluster computing, using one of the PVM,
    MPI, or openMP frameworks. For the 1.002 release, mcl's internals were
    rewritten to allow more general matrix computations. Among other things,
    mcl's data structures and primitive operations are now more suited to be
    employed in a distributed computing environment. However, much remains to be
    done before mcl can operate in such an environment.


If you feel that mcl should support some other standard matrix
    format, let us know.












This FAQ tries to compromise between being concise and
    comprehensive. The collection of answers should preferably cover the
    universe of questions at a pleasant level of semantic granularity without
    too much overlap. It should offer value to people interested in clustering
    but without sound mathematical training. Therefore, if this FAQ has not
    failed somewhere, it must have failed.


Send criticism and missing questions for consideration to mcl-faq
    at micans.org.












Stijn van Dongen.












mclfamily(7) for an overview of all the documentation and
    the utilities in the mcl family.


mcl's home at http://micans.org/mcl/.












[1] Stijn van Dongen. Graph Clustering by Flow Simulation.
    PhD thesis, University of Utrecht, May 2000.
  

  http://www.library.uu.nl/digiarchief/dip/diss/1895620/inhoud.htm


[2] Stijn van Dongen. A cluster algorithm for graphs.
    Technical Report INS-R0010, National Research Institute for Mathematics and
    Computer Science in the Netherlands, Amsterdam, May 2000.
  

  http://www.cwi.nl/ftp/CWIreports/INS/INS-R0010.ps.Z


[3] Stijn van Dongen. A stochastic uncoupling process for
    graphs. Technical Report INS-R0011, National Research Institute for
    Mathematics and Computer Science in the Netherlands, Amsterdam, May 2000.
  

  http://www.cwi.nl/ftp/CWIreports/INS/INS-R0011.ps.Z


[4] Stijn van Dongen. Performance criteria for graph clustering
    and Markov cluster experiments. Technical Report INS-R0012,
    National Research Institute for Mathematics and Computer Science in the
    Netherlands, Amsterdam, May 2000.
  

  http://www.cwi.nl/ftp/CWIreports/INS/INS-R0012.ps.Z


[5] Enright A.J., Van Dongen S., Ouzounis C.A. An efficient
    algorithm for large-scale detection of protein families, Nucleic Acids
    Research 30(7):1575-1584 (2002).












This page was generated from ZOEM manual macros,
    http://micans.org/zoem. Both html and roff pages can be created from the
    same source without having to bother with all the usual conversion problems,
    while keeping some level of sophistication in the typesetting.







  

    16 May 2014
    MCL FAQ 14-137