| 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) |