Debian Codegraph @

doc/mclfaq.txt

raw ◀ ▶
Source reconstructed at patch state 0 of 1 — not the installed (fully patched) source.
1 Debian patch touch this file
1 MCL FAQ(7) MISCELLANEOUS MCL FAQ(7)
2
3
4
5 NAME
6 mclfaq - faqs and facts about the MCL cluster algorithm.
7
8 MCL refers to the generic MCL algorithm and the MCL process on which
9 the algorithm is based. mcl refers to the implementation. This FAQ
10 answers questions related to both. In some places MCL is written
11 where MCL or mcl can be read. This is the case for example in sec-
12 tion 3, What kind of graphs. It should in general be obvious from
13 the context.
14
15 This FAQ does not begin to attempt to explain the motivation and
16 mathematics behind the MCL algorithm - the internals are not
17 explained. A broad view is given in faq 1.2, and see also faq 1.5
18 and section REFERENCES.
19
20 Some additional sections preceed the actual faq entries. The TOC
21 section contains a listing of all questions.
22
23 RESOURCES
24 The manual pages for all the utilities that come with mcl; refer to
25 mclfamily(7) for an overview.
26
27 See the REFERENCES Section for publications detailing the mathemat-
28 ics behind the MCL algorithm.
29
30 TOC
31 1...... General questions
32 1.1... For whom is mcl and for whom is this FAQ?
33 1.2... What is the relationship between the MCL process, the MCL algorithm,
34 and the 'mcl' implementation?
35 1.3... What do the letters MCL stand for?
36 1.4... How could you be so feebleminded to use MCL as abbreviation? Why is
37 it labeled 'Markov cluster' anyway?
38 1.5... Where can I learn about the innards of the MCL algorithm/process?
39 1.6... For which platforms is mcl available?
40 1.7... How does mcl's versioning scheme work?
41
42 2...... Input format
43 2.1... How can I get my data into the MCL matrix format?
44
45 3...... What kind of graphs
46 3.1... What is legal input for MCL?
47 3.2... What is sensible input for MCL?
48 3.3... Does MCL work for weighted graphs?
49 3.4... Does MCL work for directed graphs?
50 3.5... Can MCL work for lattices / directed acyclic graphs / DAGs?
51 3.6... Does MCL work for tree graphs?
52 3.7... For what kind of graphs does MCL work well and for which does it
53 not?
54 3.8... What makes a good input graph? How do I construct the similarities?
55 How to make them satisfy this Markov condition?
56 3.9... My input graph is directed. Is that bad?
57 3.10.. Why does mcl like undirected graphs and why does it dislike uni-
58 directed graphs so much?
59 3.11.. How do I check that my graph/matrix is symmetric/undirected?
60
61 4...... Speed and complexity
62 4.1... How fast is mcl/MCL?
63 4.2... What statistics are available?
64 4.3... Does this implementation need to sort vectors?
65 4.4... mcl does not compute the ideal MCL process!
66
67 5...... Comparison with other algorithms
68 5.1... I've read someplace that XYZ is much better than MCL
69 5.2... I've read someplace that MCL is slow [compared with XYZ]
70
71 6...... Resource tuning / accuracy
72 6.1... What do you mean by resource tuning?
73 6.2... How do I compute the maximum amount of RAM needed by mcl?
74 6.3... How much does the mcl clustering differ from the clustering result-
75 ing from a perfectly computed MCL process?
76 6.4... How do I know that I am using enough resources?
77 6.5... Where is the mathematical analysis of this mcl pruning strategy?
78 6.6... What qualitative statements can be made about the effect of pruning?
79 6.7... At different high resource levels my clusterings are not identical.
80 How can I trust the output clustering?
81
82 7...... Tuning cluster granularity
83 7.1... How do I tune cluster granularity?
84 7.2... The effect of inflation on cluster granularity.
85 7.3... The effect of node degrees on cluster granularity.
86 7.4... The effect of edge weight differentiation on cluster granularity.
87
88 8...... Implementing the MCL algorithm
89 8.1... How easy is it to implement the MCL algorithm?
90
91 9...... Cluster overlap / MCL iterand cluster interpretation
92 9.1... Introduction
93 9.2... Can the clusterings returned by mcl contain overlap?
94 9.3... How do I obtain the clusterings associated with MCL iterands?
95
96 10..... Miscellaneous
97 10.1.. How do I find the default settings of mcl?
98 10.2.. What's next?
99
100 FAQ
101 General questions
102
103 1.1 For whom is mcl and for whom is this FAQ?
104
105 For everybody with an appetite for graph clustering. Regarding the
106 FAQ, I have kept the amount of mathematics as low as possible, as
107 far as matrix analysis is concerned. Inevitably, some terminology
108 pops up and some references are made to the innards of the MCL algo-
109 rithm, especially in the section on resources and accuracy. Graph
110 terminology is used somewhat more carelessly though. The future
111 might bring definition entries, right now you have to do without.
112 Mathematically inclined people may be interested in the pointers
113 found in the REFERENCES section.
114
115 Given this mention of mathematics, let me point out this one time
116 only that using mcl is extremely straightforward anyway. You need
117 only mcl and an input graph (refer to the mcl manual page), and many
118 people trained in something else than mathematics are using mcl hap-
119 pily.
120
121 1.2 What is the relationship between the MCL process, the MCL algorithm,
122 and the 'mcl' implementation?
123
124 mcl is what you use for clustering. It implements the MCL algorithm,
125 which is a cluster algorithm for graphs. The MCL algorithm is basi-
126 cally a shell in which the MCL process is computed and interpreted.
127 I will describe them in the natural, reverse, order.
128
129 The MCL process generates a sequence of stochastic matrices given
130 some initial stochastic matrix. The elements with even index are
131 obtained by expanding the previous element, and the elements with
132 odd index are obtained by inflating the previous element given some
133 inflation constant. Expansion is nothing but normal matrix squaring,
134 and inflation is a particular way of rescaling the entries of a
135 stochastic matrix such that it remains stochastic.
136
137 The sequence of MCL elements (from the MCL process) is in principle
138 without end, but what happens is that the elements converge to some
139 specific kind of matrix, called the limit of the process. The
140 heuristic underlying MCL predicts that the interaction of expansion
141 with inflation will lead to a limit exhibiting cluster structure in
142 the graph associated with the initial matrix. This is indeed the
143 case, and several mathematical results tie MCL iterands and limits
144 and the MCL interpretation together (REFERENCES).
145
146 The MCL algorithm is simply a shell around the MCL process. It
147 transforms an input graph into an initial matrix suitable for start-
148 ing the process. It sets inflation parameters and stops the MCL pro-
149 cess once a limit is reached, i.e. convergence is detected. The
150 result is then interpreted as a clustering.
151
152 The mcl implementation supplies the functionality of the MCL algo-
153 rithm, with some extra facilities for manipulation of the input
154 graph, interpreting the result, manipulating resources while comput-
155 ing the process, and monitoring the state of these manipulations.
156
157 1.3 What do the letters MCL stand for?
158
159 For Markov Cluster. The MCL algorithm is a cluster algorithm that is
160 basically a shell in which an algebraic process is computed. This
161 process iteratively generates stochastic matrices, also known as
162 Markov matrices, named after the famous Russian mathematician Andrei
163 Markov.
164
165 1.4 How could you be so feebleminded to use MCL as abbreviation? Why is
166 it labeled 'Markov cluster' anyway?
167
168 Sigh. It is a widely known fact that a TLA or Three-Letter-Acronym
169 is the canonical self-describing abbreviation for the name of a
170 species with which computing terminology is infested (quoted from
171 the Free Online Dictionary of Computing). Back when I was thinking
172 of a nice tag for this cute algorithm, I was totally unaware of
173 this. I naturally dismissed MC (and would still do that today). Then
174 MCL occurred to me, and without giving it much thought I started
175 using it. A Google search (or was I still using Alta-Vista back
176 then?) might have kept me from going astray.
177
178 Indeed, MCL is used as a tag for Macintosh Common Lisp, Mission
179 Critical Linux, Monte Carlo Localization, MUD Client for Linux,
180 Movement for Canadian Literacy, and a gazillion other things - refer
181 to the file mclmcl.txt. Confusing. It seems that the three charac-
182 ters MCL possess otherworldly magical powers making them an ever so
183 strange and strong attractor in the space of TLAs. It probably helps
184 that Em-See-Ell (Em-Say-Ell in Dutch) has some rhythm to it as well.
185 Anyway MCL stuck, and it's here to stay.
186
187 On a more general level, the label Markov Cluster is not an entirely
188 fortunate choice either. Although phrased in the language of
189 stochastic matrices, MCL theory bears very little relation to Markov
190 theory, and is much closer to matrix analysis (including Hilbert's
191 distance) and the theory of dynamical systems. No results have been
192 derived in the latter framework, but many conjectures are naturally
193 posed in the language of dynamical systems.
194
195 1.5 Where can I learn about the innards of the MCL algorithm/process?
196
197 Currently, the most basic explanation of the MCL algorithm is found
198 in the technical report [2]. It contains sections on several other
199 (related) subjects though, and it assumes some working knowledge on
200 graphs, matrix arithmetic, and stochastic matrices.
201
202 1.6 For which platforms is mcl available?
203
204 It should compile and run on virtually any flavour of UNIX (includ-
205 ing Linux and the BSD variants of course). Following the instruc-
206 tions in the INSTALL file shipped with mcl should be straightforward
207 and sufficient. Courtesy to Joost van Baal who completely autofooled
208 mcl.
209
210 Building MCL on Wintel (Windows on Intel chip) should be straight-
211 forward if you use the full suite of cygwin tools. Install cygwin if
212 you do not have it yet. In the cygwin shell, unpack mcl and simply
213 issue the commands ./configure, make, make install, i.e. follow the
214 instructions in INSTALL.
215
216 This MCL implementation should also build successfully on Mac OS X.
217
218 1.7 How does mcl's versioning scheme work?
219
220 The current setup, which I hope to continue, is this. All releases
221 are identified by a date stamp. For example 02-095 denotes day 95 in
222 the year 2002. This date stamp agrees (as of April 2000) with the
223 (differently presented) date stamp used in all manual pages shipped
224 with that release. For example, the date stamp of the FAQ you are
225 reading is 16 May 2014, which corresponds with the MCL stamp 14-137.
226 The Changelog file contains a list of what's changed/added with each
227 release. Currently, the date stamp is the primary way of identifying
228 an mcl release. When asked for its version by using --version, mcl
229 outputs both the date stamp and a version tag (see below).
230
231 Input format
232
233 2.1 How can I get my data into the MCL matrix format?
234
235 This is described in the protocols manual page.
236
237 What kind of graphs
238
239 3.1 What is legal input for MCL?
240
241 Any graph (encoded as a matrix of similarities) that is nonnegative,
242 i.e. all similarities are greater than or equal to zero.
243
244 3.2 What is sensible input for MCL?
245
246 Graphs can be weighted, and they should preferably be symmetric.
247 Weights should carry the meaning of similarity, not distance. These
248 weights or similarities are incorporated into the MCL algorithm in a
249 meaningful way. Graphs should certainly not contain parts that are
250 (almost) cyclic, although nothing stops you from experimenting with
251 such input.
252
253 3.3 Does MCL work for weighted graphs?
254
255 Yes, unequivocally. They should preferably be symmetric/undirected
256 though. See entries 3.7 and 3.8.
257
258 3.4 Does MCL work for directed graphs?
259
260 Maybe, with a big caveat. See entries 3.8 and 3.9.
261
262 3.5 Can MCL work for lattices / directed acyclic graphs / DAGs?
263
264 Such graphs [term] can surely exhibit clear cluster structure. If
265 they do, there is only one way for mcl to find out. You have to
266 change all arcs to edges, i.e. if there is an arc from i to j with
267 similarity s(i,j) - by the DAG property this implies s(j,i) = 0 -
268 then make s(j,i) equal to s(i,j).
269
270 This may feel like throwing away valuable information, but in truth
271 the information that is thrown away (direction) is not informative
272 with respect to the presence of cluster structure. This may well
273 deserve a longer discussion than would be justified here.
274
275 If your graph is directed and acyclic (or parts of it are), you can
276 transform it before clustering with mcl by using -tf '#max()', e.g.
277
278 mcl YOUR-GRAPH -I 3.0 -tf '#max()'
279
280 3.6 Does MCL work for tree graphs?
281
282 Nah, I don't think so. More info at entry 3.7. You could consider
283 the Strahler number, which is numerical measure of branching com-
284 plexity.
285
286 3.7 For what kind of graphs does MCL work well and for which does it
287 not?
288
289 Graphs in which the diameter [term] of (subgraphs induced by) natu-
290 ral clusters is not too large. Additionally, graphs should prefer-
291 ably be (almost) undirected (see entry below) and not so sparse that
292 the cardinality of the edge set is close to the number of nodes.
293
294 A class of such very sparse graphs is that of tree graphs. You might
295 look into graph visualization software and research if you are
296 interested in decomposing trees into 'tight' subtrees.
297
298 The diameter criterion could be violated by neighbourhood graphs
299 derived from vector data. In the specific case of 2 and 3 dimen-
300 sional data, you might be interested in image segmentation and
301 boundary detection, and for the general case there is a host of
302 other algorithms out there. [add]
303
304 In case of weighted graphs, the notion of diameter is sometimes not
305 applicable. Generalizing this notion requires inspecting the mixing
306 properties of a subgraph induced by a natural cluster in terms of
307 its spectrum. However, the diameter statement is something grounded
308 on heuristic considerations (confirmed by practical evidence [4]) to
309 begin with, so you should probably forget about mixing properties.
310
311 3.8 What makes a good input graph? How do I construct the similarities?
312 How to make them satisfy this Markov condition?
313
314 To begin with the last one: you need not and must not make the input
315 graph such that it is stochastic aka Markovian [term]. What you need
316 to do is make a graph that is preferably symmetric/undirected, i.e.
317 where s(i,j) = s(j,i) for all nodes i and j. It need not be per-
318 fectly undirected, see the following faq for a discussion of that.
319 mcl will work with the graph of random walks that is associated with
320 your input graph, and that is the natural state of affairs.
321
322 The input graph should preferably be honest in the sense that if
323 s(x,y)=N and s(x,z)=200N (i.e. the similarities differ by a factor
324 200), then this should really reflect that the similarity of y to x
325 is neglectible compared with the similarity of z to x.
326
327 For the rest, anything goes. Try to get a feeling by experimenting.
328 Sometimes it is a good idea to filter out high-frequency and/or low-
329 frequency data, i.e. nodes with either very many neighbours or
330 extremely few neighbours.
331
332 3.9 My input graph is directed. Is that bad?
333
334 It depends. The class of directed graphs can be viewed as a spectrum
335 going from undirected graphs to uni-directed graphs. Uni-directed is
336 terminology I am inventing here, which I define as the property that
337 for all node pairs i, j, at least one of s(i,j) or s(j,i) is zero.
338 In other words, if there is an arc going from i to j in a uni-
339 directed graph, then there is no arc going from j to i. I call a
340 node pair i, j, almost uni-directed if s(i,j) << s(j,i) or vice
341 versa, i.e. if the similarities differ by an order of magnitude.
342
343 If a graph does not have (large) subparts that are (almost) uni-
344 directed, have a go with mcl. Otherwise, try to make your graph less
345 uni-directed. You are in charge, so do anything with your graph as
346 you see fit, but preferably abstain from feeding mcl uni-directed
347 graphs.
348
349 3.10 Why does mcl like undirected graphs and why does it dislike uni-
350 directed graphs so much?
351
352 Mathematically, the mcl iterands will be nice when the input graph
353 is symmetric, where nice is in this case diagonally symmetric to a
354 semi-positive definite matrix (ignore as needed). For one thing,
355 such nice matrices can be interpreted as clusterings in a way that
356 generalizes the interpretation of the mcl limit as a clustering (if
357 you are curious to these intermediate clusterings, see faq
358 entry 9.3). See the REFERENCES section for pointers to mathematical
359 publications.
360
361 The reason that mcl dislikes uni-directed graphs is not very mcl
362 specific, it has more to do with the clustering problem itself.
363 Somehow, directionality thwarts the notion of cluster structure.
364 [add].
365
366 3.11 How do I check that my graph/matrix is symmetric/undirected?
367
368 Whether your graph is created by third-party software or by custom
369 sofware written by someone you know (e.g. yourself), it is advisable
370 to test whether the software generates symmetric matrices. This can
371 be done as follows using the mcxi utility, assuming that you want to
372 test the matrix stored in file matrix.mci. The mcxi utility should
373 be available on your system if mcl was installed in the normal way.
374
375 mcxi /matrix.mci lm tp -1 mul add /check wm
376
377 This loads the graph/matrix stored in matrix.mci into mcxi's memory
378 with the mcxi lm primitive. - the leading slash is how strings are
379 introduced in the stack language interpreted by mcxi. The transpose
380 of that matrix is then pushed on the stack with the tp primitive and
381 multiplied by minus one. The two matrices are added, and the result
382 is written to the file check. The transposed matrix is the mirrored
383 version of the original matrix stored in matrix.mci. If a
384 graph/matrix is undirected/symmetric, the mirrored image is neces-
385 sarily the same, so if you subtract one from the other it should
386 yield an all zero matrix.
387
388 Thus, the file check should look like this:
389
390 (mclheader
391 mcltype matrix
392 dimensions <num>x<num>
393 )
394 (mclmatrix
395 begin
396 )
397
398 Where <num> is the same as in the file matrix.mci. If this is not
399 the case, find out what's prohibiting you from feeding mcl symmetric
400 matrices. Note that any nonzero entries found in the matrix stored
401 as check correspond to node pairs for which the arcs in the two pos-
402 sible directions have different weight.
403
404 Speed and complexity
405
406 4.1 How fast is mcl/MCL?
407
408 It's fast - here is how and why. Let N be the number of nodes in the
409 input graph. A straigtforward implementation of MCL will have time
410 and space complexity respecively O(N^3) (i.e. cubic in N) and O(N^2)
411 (quadratic in N). So you don't want one of those.
412
413 mcl implements a slightly perturbed version of the MCL process, as
414 discussed in section Resource tuning / accuracy. Refer to that sec-
415 tion for a more extensive discussion of all the aspects involved.
416 This section is only concerned with the high-level view of things
417 and the nitty gritty complexity details.
418
419 While computing the square of a matrix (the product of that matrix
420 with itself), mcl keeps the matrix sparse by allowing a certain max-
421 imum number of nonzero entries per stochastic column. The maximum is
422 one of the mcl parameters, and it is typically set somewhere between
423 500 and 1500. Call the maximum K.
424
425 mcl's time complexity is governed by the complexity of matrix squar-
426 ing. There are two sub-algorithms to consider. The first is the
427 algorithm responsible for assembling a new vector during matrix mul-
428 tiplication. This algorithm has worst case complexity O(K^2). The
429 pruning algorithm (which uses heap selection) has worst case com-
430 plexity O(L*log(K)), where L is how large a newly computed matrix
431 column can get before it is reduced to at most K entries. L is bound
432 by the smallest of the two numbers N and K^2 (the square of K), but
433 on average L will be much smaller than that, as the presence of
434 cluster structure aids in keeping the factor L low. [Related to this
435 is the fact that clustering algorithms are actually used to compute
436 matrix splittings that minimize the number of cross-computations
437 when carrying out matrix multiplication among multiple processors.]
438 In actual cases of heavy usage, L is of order in the tens of thou-
439 sands, and K is in the order of several hundreds up to a thousand.
440
441 It is safe to say that in general the worst case complexity of mcl
442 is of order O(N*K^2); for extremely tight and dense graphs this
443 might become O(N*N*log(K)). Still, these are worst case estimates,
444 and observed running times for actual usage are much better than
445 that. (refer to faq 4.2).
446
447 In this analysis, the number of iterations required by mcl was not
448 included. It is nearly always far below 100. Only the first few
449 (less than ten) iterations are genuinely time consuming, and they
450 are usually responsible for more than 95 percent of the running
451 time.
452
453 The process of removing the smallest entries of a vector is called
454 pruning. mcl outputs a summary of this once it is done. More infor-
455 mation is provided in the pruning section of the mcl manual and Sec-
456 tion 6 in this FAQ.
457
458 The space complexity is of order O(N*K).
459
460 4.2 What statistics are available?
461
462 Few. Some experiments are described in [4], and [5] mentions large
463 graphs being clustered in very reasonable time. In protein cluster-
464 ing, mcl has been applied to graphs with up to one million nodes,
465 and on high-end hardware such graphs can be clustered within a few
466 hours.
467
468 4.3 Does this implementation need to sort vectors?
469
470 No, it does not. You might expect that one needs to sort a vector in
471 order to obtain the K largest entries, but a simpler mechanism
472 called heap selection does the job nicely. Selecting the K largest
473 entries from a set of L by sorting would require O(L*log(L)) opera-
474 tions; heap selection requires O(L*log(K)) operations. Alterna-
475 tively, the K largest entries can be also be determined in O(N) +
476 O(K log(K)) asymptotic time by using partition selection (more here
477 and there). It is possible to enable this mode of operaton in mcl
478 with the option --partition-selection. However, benchmarking so far
479 has shown this to be equivalent in speed to heap selection. This is
480 explained by the bounded nature of K and L in practice.
481
482 4.4 mcl does not compute the ideal MCL process!
483
484 Indeed it does not. What are the ramifications? Several entries in
485 section Resource tuning / accuracy discuss this issue. For a synop-
486 sis, consider two ends of a spectrum.
487
488 On the one end, a graph that has very strong cluster structure, with
489 clearly (and not necessarity fully) separated clusters. This mcl
490 implementation will certainly retrieve those clusters if the graphs
491 falls into the category of graphs for which mcl is applicable. On
492 the other end, consider a graph that has only weak cluster structure
493 superimposed on a background of a more or less random graph. There
494 might sooner be a difference between the clustering that should ide-
495 ally result and the one computed by mcl. Such a graph will have a
496 large number of whimsical nodes that might end up either here or
497 there, nodes that are of a peripheral nature, and for which the
498 (cluster) destination is very sensitive to fluctutations in edge
499 weights or algorithm parametrizations (any algorithm, not just mcl).
500
501 In short, the perturbation effect of the pruning process applied by
502 mcl is a source of noise. It is small compared to the effect of
503 changing the inflation parametrization or perturbing the edge
504 weights. If the change is larger, this is because the computed pro-
505 cess tends to converge prematurely, leading to finer-grained clus-
506 terings. As a result the clustering will be close to a subclustering
507 of the clustering resulting from more conservative resource set-
508 tings, and in that respect be consistent. All this can be measured
509 using the program clm dist. It is possible to offset such a change
510 by slightly lowering the inflation parameter.
511
512 There is the issue of very large and very dense graphs. The act of
513 pruning will have a larger impact as graphs grow larger and denser.
514 Obviously, mcl will have trouble dealing with such very large and
515 very dense graphs - so will other methods.
516
517 Finally, there is the engineering approach, which offers the possi-
518 bility of pruning a whole lot of speculation. Do the experiments
519 with mcl, try it out, and see what's there to like and dislike.
520
521 Comparison with other algorithms
522
523 5.1 I've read someplace that XYZ is much better than MCL
524
525 XYZ might well be the bees knees of all things clustering. Bear in
526 mind though that comparing cluster algorithms is a very tricky
527 affair. One particular trap is the following. Sometimes a new clus-
528 ter algorithm is proposed based on some optimization criterion. The
529 algorithm is then compared with previous algorithms (e.g. MCL). But
530 how to compare? Quite often the comparison will be done by computing
531 a criterion and astoundingly, quite often the chosen criterion is
532 simply the optimization criterion again. Of course XYZ will do very
533 well. It would be a very poor algorithm it if did not score well on
534 its own optimization criterion, and it would be a very poor algo-
535 rithm if it did not perform better than other algorithms which are
536 built on different principles.
537
538 There are some further issues that have to be considered here.
539 First, there is not a single optimization criterion that fully cap-
540 tures the notion of cluster structure, let alone best cluster struc-
541 ture. Second, leaving optimization approaches aside, it is not pos-
542 sible to speak of a best clustering. Best always depends on context
543 - application field, data characteristics, scale (granularity), and
544 practitioner to name but a few aspects. Accordingly, the best a
545 clustering algorithm can hope for is to be a good fit for a certain
546 class of problems. The class should not be too narrow, but no algo-
547 rithm can cater for the broad spectre of problems for which cluster-
548 ing solutions are sought. The class of problems to which MCL is
549 applicable is discussed in section What kind of graphs.
550
551 5.2 I've read someplace that MCL is slow [compared with XYZ]
552
553 Presumably, they did not know mcl, and did not read the parts in [1]
554 and [2] that discuss implementation. Perhaps they assume or insist
555 that the only way to implement MCL is to implement the ideal pro-
556 cess. And there is always the genuine possibility of a really stupi-
557 fyingly fast algorithm. It is certainly not the case that MCL has a
558 time complexity of O(N^3) as is sometimes erroneously stated.
559
560 Resource tuning / accuracy
561
562 6.1 What do you mean by resource tuning?
563
564 mcl computes a process in which stochastic matrices are alternately
565 expanded and inflated. Expansion is nothing but standard matrix mul-
566 tiplication, inflation is a particular way of rescaling the matrix
567 entries.
568
569 Expansion causes problems in terms of both time and space. mcl works
570 with matrices of dimension N, where N is the number of nodes in the
571 input graph. If no precautions are taken, the number of entries in
572 the mcl iterands (which are stochastic matrices) will soon approach
573 the square of N. The time it takes to compute such a matrix will be
574 proportional to the cube of N. If your input graph has 100.000
575 nodes, the memory requirements become infeasible and the time
576 requirements become impossible.
577
578 What mcl does is perturbing the process it computes a little by
579 removing the smallest entries - it keeps its matrices sparse. This
580 is a natural thing to do, because the matrices are sparse in a
581 weighted sense (a very high proportion of the stochastic mass is
582 contained in relatively few entries), and the process converges to
583 matrices that are extremely sparse, with usually no more than N
584 entries. It is thus known that the MCL iterands are sparse in a
585 weighted sense and are usually very close to truly sparse matrices.
586 The way mcl perturbs its matrices is by the strategy of pruning,
587 selection, and recovery that is extensively described in the mcl
588 manual page. The question then is: What is the effect of this per-
589 turbation on the resulting clustering, i.e. how would the clustering
590 resulting from a perfectly computed mcl process compare with the
591 clustering I have on disk? Faq entry 6.3 discusses this issue.
592
593 The amount of resources used by mcl is bounded in terms of the maxi-
594 mum number of neighbours a node is allowed to have during all compu-
595 tations. Equivalently, this is the maximum number of nonzero
596 entries a matrix column can possibly have. This number, finally, is
597 the maximum of the the values corresponding with the -S and -R
598 options. The latter two are listed when using the -z option (see
599 faq 10.1).
600
601 6.2 How do I compute the maximum amount of RAM needed by mcl?
602
603 It is rougly equal to
604
605 2 * s * K * N
606
607 bytes, where 2 is the number of matrices held in memory by mcl, s is
608 the size of a single cell (c.q. matrix entry or node/arc specifica-
609 tion), N is the number of nodes in the input graph, and where K is
610 the maximum of the values corresponding with the -S and -R options
611 (and this assumes that the average node degree in the input graph
612 does not exceed K either). The value of s can be found by using the
613 -z option. It is listed in one of the first lines of the resulting
614 output. s equals the size of an int plus the size of a float, which
615 will be 8 on most systems. The estimate above will in most cases be
616 way too pessimistic (meaning you do not need that amount of memory).
617
618 The -how-much-ram option is provided by mcl for computing the bound
619 given above. This options takes as argument the number of nodes in
620 the input graph.
621
622 The theoretically more precise upper bound is slightly larger due to
623 overhead. It is something like
624
625 ( 2 * s * (K + c)) * N
626
627 where c is 5 or so, but one should not pay attention to such a small
628 difference anyway.
629
630 6.3 How much does the mcl clustering differ from the clustering result-
631 ing from a perfectly computed MCL process?
632
633 For graphs with up until a few thousand nodes a perfectly computed
634 MCL process can be achieved by abstaining from pruning and doing
635 full-blown matrix arithmetic. Of course, this still leaves the issue
636 of machine precision, but let us wholeheartedly ignore that.
637
638 Such experiments give evidence (albeit incidental) that pruning is
639 indeed really what it is thought to be - a small perturbation. In
640 many cases, the 'approximated' clustering is identical to the
641 'exact' clustering. In other cases, they are very close to each
642 other in terms of the metric split/join distance as computed by
643 clm dist. Some experiments with randomly generated test graphs,
644 clustering, and pruning are described in [4].
645
646 On a different level of abstraction, note that perturbations of the
647 inflation parameter will also lead to perturbations in the resulting
648 clusterings, and surely, large changes in the inflation parameter
649 will in general lead to large shifts in the clusterings. Node/clus-
650 ter pairs that are different for the approximated and the exact
651 clustering will very likely correspond with nodes that are in a
652 boundary region between two or more clusters anyway, as the pertur-
653 bation is not likely to move a node from one core of attraction to
654 another.
655
656 Faq entry 6.6 has more to say about this subject.
657
658 6.4 How do I know that I am using enough resources?
659
660 In mcl parlance, this becomes how do I know that my -scheme parame-
661 ter is high enough or more elaborately how do I know that the values
662 of the {-P, -S, -R, -pct} combo are high enough?
663
664 There are several aspects. First, watch the jury marks reported by
665 mcl when it's done. The jury marks are three grades, each out of
666 100. They indicate how well pruning went. If the marks are in the
667 seventies, eighties, or nineties, mcl is probably doing fine. If
668 they are in the eighties or lower, try to see if you can get the
669 marks higher by spending more resources (e.g. increase the parameter
670 to the -scheme option).
671
672 Second, you can do multiple mcl runs for different resource schemes,
673 and compare the resulting clusterings using clm dist. See the
674 clmdist manual for a case study.
675
676 6.5 Where is the mathematical analysis of this mcl pruning strategy?
677
678 There is none. [add]
679
680 Ok, the next entry gives an engineer's rule of thumb.
681
682 6.6 What qualitative statements can be made about the effect of pruning?
683
684 The more severe pruning is, the more the computed process will tend
685 to converge prematurely. This will generally lead to finer-grained
686 clusterings. In cases where pruning was severe, the mcl clustering
687 will likely be closer to a clustering ideally resulting from another
688 MCL process with higher inflation value, than to the clustering ide-
689 ally resulting from the same MCL process. Strong support for this is
690 found in a general observation illustrated by the following example.
691 Suppose u is a stochastic vector resulting from expansion:
692
693 u = 0.300 0.200 0.200 0.100 0.050 0.050 0.050 0.050
694
695 Applying inflation with inflation value 2.0 to u gives
696
697 v = 0.474 0.211 0.211 0.053 0.013 0.013 0.013 0.013
698
699 Now suppose we first apply pruning to u such that the 3 largest
700 entries 0.300, 0.200 and 0.200 survive, throwing away 30 percent of
701 the stochastic mass (which is quite a lot by all means). We rescale
702 those three entries and obtain
703
704 u' = 0.429 0.286 0.286 0.000 0.000 0.000 0.000 0.000
705
706 Applying inflation with inflation value 2.0 to u' gives
707
708 v' = 0.529 0.235 0.235 0.000 0.000 0.000 0.000 0.000
709
710 If we had applied inflation with inflation value 2.5 to u, we would
711 have obtained
712
713 v'' = 0.531 0.201 0.201 0.038 0.007 0.007 0.007 0.007
714
715 The vectors v' and v'' are much closer to each other than the vec-
716 tors v' and v, illustrating the general idea.
717
718 In practice, mcl should (on average) do much better than in this
719 example.
720
721 6.7 At different high resource levels my clusterings are not identical.
722 How can I trust the output clustering?
723
724 Did you read all other entries in this section? That should have
725 reassured you somewhat, except perhaps for Faq answer 6.5.
726
727 You need not feel uncomfortable with the clusterings still being
728 different at high resource levels, if ever so slightly. In all like-
729 lihood, there are anyway nodes which are not in any core of attrac-
730 tion, and that are on the boundary between two or more clusterings.
731 They may go one way or another, and these are the nodes which will
732 go different ways even at high resource levels. Such nodes may be
733 stable in clusterings obtained for lower inflation values (i.e.
734 coarser clusterings), in which the different clusters to which they
735 are attracted are merged.
736
737 By the way, you do know all about clm dist, don't you? Because the
738 statement that clusterings are not identical should be quantified:
739 How much do they differ? This issue is discussed in the clm dist
740 manual page - clm dist gives you a robust measure for the distance
741 (dissimilarity) between two clusterings.
742
743 There are other means of gaining trust in a clustering, and there
744 are different issues at play. There is the matter of how accurately
745 this mcl computed the mcl process, and there is the matter of how
746 well the chosen inflation parameter fits the data. The first can be
747 judged by looking at the jury marks (faq 6.4) and applying clm dist
748 to different clusterings. The second can be judged by measurement
749 (e.g. use clm info) and/or inspection (use your judgment).
750
751 Tuning cluster granularity
752
753 7.1 How do I tune cluster granularity?
754
755 There are several ways for influencing cluster granularity. These
756 ways and their relative merits are successively discussed below.
757 Reading clmprotocols(5) is also a good idea.
758
759 7.2 The effect of inflation on cluster granularity.
760
761 The main handle for changing inflation is the -I option. This is
762 also the principal handle for regulating cluster granularity. Unless
763 you are mangling huge graphs it could be the only mcl option you
764 ever need besides the output redirection option -o.
765
766 Increasing the value of -I will increase cluster granularity. Con-
767 ceivable values are from 1.1 to 10.0 or so, but the range of suit-
768 able values will certainly depend on your input graph. For many
769 graphs, 1.1 will be far too low, and for many other graphs, 8.0 will
770 be far too high. You will have to find the right value or range of
771 values by experimenting, using your judgment, and using measurement
772 tools such as clm dist and clm info. A good set of values to start
773 with is 1.4, 2 and 6.
774
775 7.3 The effect of node degrees on cluster granularity.
776
777 Preferably the network should not have nodes of very high degree,
778 that is, with exorbitantly many neighbours. Such nodes tend to
779 obscure cluster structure and contribute to coarse clusters. The
780 ways to combat this using mcl and sibling programs are documented in
781 clmprotocols(5). Briefly, they are the transformations #knn() and
782 #ceilnb() available to mcl, mcx alter and several more programs.
783
784 7.4 The effect of edge weight differentiation on cluster granularity.
785
786 How similarities in the input graph were derived, constructed,
787 adapted, filtered (et cetera) will affect cluster granularity. It
788 is important that the similarities are honest; refer to faq 3.8.
789
790 Another issue is that homogeneous similarities tend to result in
791 more coarse-grained clusterings. You can make a set of similarities
792 more homogeneous by applying some function to all of them, e.g. for
793 all pairs of nodes (x y) replace S(x,y) by the square root, the log-
794 arithm, or some other convex function. Note that you need not worry
795 about scaling, i.e. the possibly large changes in magnitude of the
796 similarities. MCL is not affected by absolute magnitudes, it is only
797 affected by magnitudes taken relative to each other.
798
799 As of version 03-154, mcl supports the pre-inflation -pi f option.
800 Make a graph more homogeneous with respect to the weight function by
801 using -pi with argument f somewhere in the interval [0,1] - 0.5 can
802 be considered a reasonable first try. Make it less homogeneous by
803 setting f somewhere in the interval [1,10]. In this case 3 is a
804 reasonable starting point.
805
806 Implementing the MCL algorithm
807
808 8.1 How easy is it to implement the MCL algorithm?
809
810 Very easy, if you will be doing small graphs only, say up to a few
811 thousand entries at most. These are the basic ingredients:
812
813 o Adding loops to the input graph, conversion to a stochastic
814 matrix.
815 o Matrix multiplication and matrix inflation.
816 o The interpretation function mapping MCL limits onto clusterings.
817
818 These must be wrapped in a program that does graph input and cluster
819 output, alternates multiplication (i.e. expansion) and inflation in
820 a loop, monitors the matrix iterands thus found, quits the loop when
821 convergence is detected, and interprets the last iterand.
822
823 Implementing matrix muliplication is a standard exercise. Implement-
824 ing inflation is nearly trivial. The hardest part may actually be
825 the interpretation function, because you need to cover the corner
826 cases of overlap and attractor systems of cardinality greater than
827 one. Note that MCL does not use intricate and expensive operations
828 such as matrix inversion or matrix reductions.
829
830 In Mathematica or Maple, mcl should be doable in at most 100 lines
831 of code. For perl you may need twice that amount. In lower level
832 languages such as C or Fortran a basic MCL program may need a few
833 hundred lines, but the largest part will probably be input/output
834 and interpretation.
835
836 To illustrate all these points, mcl now ships with minimcl, a small
837 perl script that implements mcl for educational purposes. Its
838 structure is very simple and should be easy to follow.
839
840 Implementing the basic MCL algorithm makes a nice programming exer-
841 cise. However, if you need an implementation that scales to several
842 hundreds of thousands of nodes and possibly beyond, then your duties
843 become much heavier. This is because one needs to prune MCL iterands
844 (c.q. matrices) such that they remain sparse. This must be done
845 carefully and preferably in such a way that a trade-off between
846 speed, memory usage, and potential losses or gains in accuracy can
847 be controlled via monitoring and logging of relevant characteris-
848 tics. Some other points are i) support for threading via pthreads,
849 openMP, or some other parallel programming API. ii) a robust and
850 generic interpretation function is written in terms of weakly con-
851 nected components.
852
853 Cluster overlap / MCL iterand cluster interpretation
854
855 9.1 Introduction
856
857 A natural mapping exists of MCL iterands to DAGs (directed acyclic
858 graphs). This is because MCL iterands are generally diagonally posi-
859 tive semi-definite - see [3]. Such a DAG can be interpreted as a
860 clustering, simply by taking as cores all endnodes (sinks) of the
861 DAG, and by attaching to each core all the nodes that reach it. This
862 procedure may result in clusterings containing overlap.
863
864 In the MCL limit, the associated DAG has in general a very degener-
865 ated form, which induces overlap only on very rare occasions (see
866 faq entry 9.2).
867
868 Interpreting mcl iterands as clusterings may well be interesting.
869 Few experiments have been done so far. It is clear though that early
870 iterands generally contain the most overlap (when interpreted as
871 clusterings). Overlap dissappears soon as the iterand index
872 increases. For more information, consult the other entries in this
873 section and the clmimac manual page.
874
875 9.2 Can the clusterings returned by mcl contain overlap?
876
877 No. Clusterings resulting from the abstract MCL algorithm may in
878 theory contain overlap, but the default behaviour in mcl is to
879 remove it should it occur, by allocating the nodes in overlap to the
880 first cluster in which they are seen. mcl will warn you if this
881 occurs. This behaviour is switched off by supplying --keep-over-
882 lap=yes.
883
884 Do note that overlap is mostly a theoretical possibility. It is
885 conjectured that it requires the presence of very strong symmetries
886 in the input graph, to the extent that there exists an automorphism
887 of the input graph mapping the overlapping part onto itself.
888
889 It is possible to construct (highly symmetric) input graphs leading
890 to cluster overlap. Examples of overlap in which a few nodes are
891 involved are easy to construct; examples with many nodes are excep-
892 tionally hard to construct.
893
894 Clusterings associated with intermediate/early MCL iterands may very
895 well contain overlap, see the introduction in this section and other
896 entries.
897
898 9.3 How do I obtain the clusterings associated with MCL iterands?
899
900 There are two options. If you are interested in clusterings contain-
901 ing overlap, you should go for the second. If not, use the first,
902 but beware that the resulting clusterings may contain overlap.
903
904 The first solution is to use -dump cls (probably in conjunction with
905 either -L or -dumpi in order to limit the number of matrices writ-
906 ten). This will cause mcl to write the clustering generically asso-
907 ciated with each iterand to file. The -dumpstem option may be conve-
908 nient as well.
909
910 The second solution is to use the -dump ite option (-dumpi and
911 -dumpstem may be of use again). This will cause mcl to write the
912 intermediate iterands to file. After that, you can apply clm imac
913 (interpret matrix as clustering) to those iterands. clm imac has a
914 -strict parameter which affects the mapping of matrices to cluster-
915 ings. It takes a value between 0.0 and 1.0 as argument. The default
916 is 0.001 and corresponds with promoting overlap. Increasing the
917 -strict value will generally result in clusterings containing less
918 overlap. This will have the largest effect for early iterands; its
919 effect will diminish as the iterand index increases.
920
921 When set to 0, the -strict parameter results in the clustering asso-
922 ciated with the DAG associated with an MCL iterand as described in
923 [3]. This DAG is pruned (thus possibly resulting in less overlap in
924 the clustering) by increasing the -strict parameter. [add]
925
926 Miscellaneous
927
928 10.1 How do I find the default settings of mcl?
929
930 Use -z to find out the actual settings - it shows the settings as
931 resulting from the command line options (e.g. the default settings
932 if no other options are given).
933
934 10.2 What's next?
935
936 I'd like to port MCL to cluster computing, using one of the PVM,
937 MPI, or openMP frameworks. For the 1.002 release, mcl's internals
938 were rewritten to allow more general matrix computations. Among
939 other things, mcl's data structures and primitive operations are now
940 more suited to be employed in a distributed computing environment.
941 However, much remains to be done before mcl can operate in such an
942 environment.
943
944 If you feel that mcl should support some other standard matrix for-
945 mat, let us know.
946
947 BUGS
948 This FAQ tries to compromise between being concise and comprehen-
949 sive. The collection of answers should preferably cover the universe
950 of questions at a pleasant level of semantic granularity without too
951 much overlap. It should offer value to people interested in cluster-
952 ing but without sound mathematical training. Therefore, if this FAQ
953 has not failed somewhere, it must have failed.
954
955 Send criticism and missing questions for consideration to mcl-faq at
956 micans.org.
957
958 AUTHOR
959 Stijn van Dongen.
960
961 SEE ALSO
962 mclfamily(7) for an overview of all the documentation and the utili-
963 ties in the mcl family.
964
965 mcl's home at http://micans.org/mcl/.
966
967 REFERENCES
968 [1] Stijn van Dongen. Graph Clustering by Flow Simulation. PhD the-
969 sis, University of Utrecht, May 2000.
970 http://www.library.uu.nl/digiarchief/dip/diss/1895620/inhoud.htm
971
972 [2] Stijn van Dongen. A cluster algorithm for graphs. Technical
973 Report INS-R0010, National Research Institute for Mathematics and
974 Computer Science in the Netherlands, Amsterdam, May 2000.
975 http://www.cwi.nl/ftp/CWIreports/INS/INS-R0010.ps.Z
976
977 [3] Stijn van Dongen. A stochastic uncoupling process for graphs.
978 Technical Report INS-R0011, National Research Institute for Mathe-
979 matics and Computer Science in the Netherlands, Amsterdam, May 2000.
980 http://www.cwi.nl/ftp/CWIreports/INS/INS-R0011.ps.Z
981
982 [4] Stijn van Dongen. Performance criteria for graph clustering and
983 Markov cluster experiments. Technical Report INS-R0012, National
984 Research Institute for Mathematics and Computer Science in the
985 Netherlands, Amsterdam, May 2000.
986 http://www.cwi.nl/ftp/CWIreports/INS/INS-R0012.ps.Z
987
988 [5] Enright A.J., Van Dongen S., Ouzounis C.A. An efficient algo-
989 rithm for large-scale detection of protein families, Nucleic Acids
990 Research 30(7):1575-1584 (2002).
991
992 NOTES
993 This page was generated from ZOEM manual macros,
994 http://micans.org/zoem. Both html and roff pages can be created from
995 the same source without having to bother with all the usual conver-
996 sion problems, while keeping some level of sophistication in the
997 typesetting.
998
999
1000
1001 MCL FAQ 14-137 16 May 2014 MCL FAQ(7)