4mmcl24m(1)                          USER COMMANDS                           4mmcl24m(1)

  1mNAME0m
      mcl - The Markov Cluster Algorithm, aka the MCL algorithm.

      This  program  implements  1mmcl22m, a cluster algorithm for graphs. A single
      parameter controls the granularity of the output clustering, namely  the
      1m-I 4m22minflation24m  option  described further below.  In standard usage of the
      program this parameter is the only one that may require changing. By de-
      fault it is set to 2.0 and this is a good way to start. If you  want  to
      explore cluster structure in graphs with MCL, vary this parameter to ob-
      tain  clusterings  at  different  levels  of  granularity. A good set of
      starting values is 1.4, 2, 4, and 6.

      The program has a rather large set of options. Except for  1m-I  22mnone  af-
      fects  the clustering method itself. The other options are for a variety
      of aspects, such as study of the underlying MCL process  (i.e.   dumping
      of  iterands),  network preprocessing (incorporated for efficiency), re-
      source allocation options (for large-scale analyses), output naming  and
      placement, output formatting, setting of verbosity levels, and so on.

      Network  construction  and reduction techniques should not be considered
      as part of a clustering algorithm.  Nevertheless  particular  techniques
      may  benefit particular methods or applications. In mcl many transforma-
      tions are accessible through the 1m-tf 22moption. It can  be  used  for  edge
      weight  transformations  and  selection, as well as transformations that
      act on a graph as a whole.  It is for example possible to  remove  edges
      with  weight  below  0.7  by issuing 1m-tf 'gq(0.7)'22m, where the quotes are
      necessary to prevent the shell from interpreting  the  parentheses.  The
      option     accepts     more     complicated     sequences,    such    as
      1m-tf 'gq(0.7),add(-0.7)'22m. This causes all remaining edge  weights  to  be
      shifted  to the range [0-0.3], assuming that the input contains correla-
      tions.  Many  more  transformations  are  supported,  as  documented  in
      1mmcxio(5)22m.  Examples  of graph-wide transformations are '#knn(<num>)' and
      '#ceilnb(<num>)'. The first only keeps those edges  that  occur  in  the
      list of top-<num> edges of highest weight in both of its incident nodes.
      The  second removes edges from nodes of highest degree first, proceeding
      until all node degrees satisfy the given threshold.  The 1m-pi 22m(pre-infla-
      tion) option can be used to increase the contrast in edge weights.  This
      may  be  useful when clusterings are coarse and fine-grained clusterings
      are difficult to obtain.

  1mGETTING STARTED0m
      There are two main modes of invocation. The  most  accessible  is  4mlabel0m
      4mmode24m which assumes a format alternatively called label input or ABC-for-
      mat.   The  input is then a file or stream in which each line encodes an
      edge in terms of two labels (the 'A' and the 'B') and a numerical  value
      (the 'C'), all separated by white space. The most basic example of usage
      is this:

         1mmcl 22m<-|fname> 1m--abc -o 4m22mfname-out0m

      The  output is then a file where each line is a cluster of tab-separated
      labels.  If clustering is part of a larger workflow where it  is  desir-
      able to analyse and compare multiple clusterings, then it is a good idea
      to  use  native  mode rather than ABC mode.  The reason for this is that
      native mode is understood by all programs in the mcl suite. It is a more
      stringent and unambiguous format, and hence more suitable for  data  ex-
      change.  The reader is referred to 1mclmprotocols(5) 22mfor more information.

  1mSYNOPSIS0m
      The  example  invocation  below assumes matrix input, as explained above
      and described in the 1mmcxio(5) 22msection. Switching to label mode  requires
      the input file to be in ABC-format and the addition of the 1m--abc 22moption.

      1mmcl 22m<-|fname> 1m[-I 22m<num> (4minflation24m)1m] [-o 22m<str> (4mfname24m)1m]0m

      These  options  are  sufficient  in 95 percent of the cases or more. The
      first argument must be the name of a file containing a  graph/matrix  in
      the  mcl  input  format, or a hyphen to read from STDIN. With respect to
      clustering, the 1m-I 22moption is foremost relevant.

      The full listing of 1mmcl 22moptions is shown further below,  separated  into
      parts  corresponding with functional aspects such as clustering, thread-
      ing, verbosity, network preprocessing, pruning and resource  management,
      automatic output naming, and dumping.

      1mBaseline clustering options0m
      1m[-I 22m<num> (4minflation24m)1m] [-o 22m<fname> (4mfname24m)1m]0m

      1mOutput options0m
      1m[-odir 22m<dname> (4mdirectory24m)1m] [--d 22m(4muse24m 4minput24m 4mdirectory24m 4mfor24m 4moutput24m)1m]0m

      1mInput options0m
      1m[--abc  22m(4mexpect/write24m 4mlabels24m)1m] [--sif 22m(4mexpect/write24m 4mlabels24m)1m] [--etc 22m(4mex-0m
      4mpect/write24m 4mlabels24m)1m] [--expect-values 22m(4msif24m 4mor24m 4metc24m  4mstream24m  4mcontains24m  4mval-0m
      4mues24m)1m] [-use-tab 22m<fname> (4muse24m 4mmapping24m 4mto24m 4mwrite24m)1m]0m

      1mTransform options0m
      1m[-tf  22m<tf-spec>  (4mtransform24m  4minput24m  4mmatrix24m  4mvalues24m)1m]  [-abc-tf 22m<tf-spec>
      (4mtransform24m 4minput24m 4mstream24m 4mvalues24m)1m] [--abc-neg-log10 22m(4mtake24m 4mlog1024m 4mof24m  4mstream0m
      4mvalues,24m  4mnegate24m 4msign24m)1m] [--abc-neg-log 22m(4mtake24m 4mlog24m 4mof24m 4mstream24m 4mvalues,24m 4mnegate0m
      4msign24m)1m] [-icl 22m<fname> (4mcreate24m 4msubgraph24m 4mon24m 4mclustering24m)1m]0m

      1mCache options0m
      1m[-write-graph  22m<fname>  (4mwrite24m  4mgraph24m)1m]  [-write-graphx  22m<fname>  (4mwrite0m
      4mtransformed24m  4mgraph24m)1m]  [-write-expanded  22m<fname>  (4mwrite24m 4mexpanded24m 4mgraph24m)1m]0m
      1m[--write-limit 22m(4mwrite24m 4mmcl24m 4mprocess24m 4mlimit24m)1m]0m

      1mInput manipulation options0m
      1m[-pi 22m<num> (4mpre-inflation24m)1m] [-if  22m<num>  (4mstart-inflation24m)1m]  [--discard-0m
      1mloops=22m<y/n> (4mdiscard24m 4my/n24m 4mloops24m 4min24m 4minput24m)1m] [-c 22m<num> (4mreweight24m 4mloops24m)1m]0m

      1mClustering processing options0m
      1m[-sort  22m<str> (4msort24m 4mmode24m)1m] [-overlap 22m<str> (4moverlap24m 4mmode24m)1m] [--force-con-0m
      1mnected=22m<y/n>  (4manalyze24m  4mcomponents24m)1m]  [--check-connected=22m<y/n>  (4manalyze0m
      4mcomponents24m)1m]  [--analyze=22m<y/n> (4mperformance24m 4mcriteria24m)1m] [--show-log=22m<y/n>
      (4mshow24m 4mlog24m)1m]0m

      1mVerbosity options0m
      1m[-q 22m<spec> (4mlog24m 4mlevels24m)1m] [-v 22m<str> (4mverbosity24m 4mtype24m 4mon24m)1m] [-V 22m<str>  (4mver-0m
      4mbosity24m 4mtype24m 4moff24m)1m] [--show 22m(4mprint24m 4m(small)24m 4mmatrices24m 4mto24m 4mscreen24m)1m]0m

      1mThread options0m
      1m[-te 22m<int> (4m#expansion24m 4mthreads24m)1m]0m

      1mOutput file name and annotation options0m
      1m[-o  22m<str> (4mfname24m)1m] [-ap 22m<str> (4muse24m 4mstr24m 4mas24m 4mfile24m 4mname24m 4mprefix24m)1m] [-aa 22m<str>
      (4mappend24m 4mstr24m 4mto24m 4msuffix24m)1m] [-az 22m(4mshow24m 4moutput24m  4mfile24m  4mname24m  4mand24m  4mexit24m)1m]  [-ax0m
      (4mshow24m 4moutput24m 4msuffix24m 4mand24m 4mexit24m)1m] [-annot 22m<str> (4mdummy24m 4mannotation24m 4moption24m)1m]0m

      1mDump options0m
      1m[-dump-interval  22m<i:j>  (4mdump24m  4minterval24m)1m] [-dump-modulo 22m<int> (4mdump24m 4mmod-0m
      4mulo24m)1m] [-dump-stem 22m<stem> (4mdump24m 4mfile24m 4mstem24m)1m] [-dump 22m<str> (4mtype24m)1m] [-digits0m
      <int> (4mprinting24m 4mprecision24m)1m] [--write-binary 22m(4mwrite24m  4mmatrices24m  4min24m  4mbinary0m
      4mformat24m)1m]0m

      1mInfo options0m
      1m[--jury-charter  22m(4mexplains24m 4mjury24m)1m] [--version 22m(4mshow24m 4mversion24m)1m] [-how-much-0m
      1mram 22mk (4mRAM24m 4mupper24m 4mbound24m)1m] [-h 22m(4mmost24m 4mimportant24m 4moptions24m)1m] [--help 22m(4mone-line0m
      4mdescription24m 4mfor24m 4mall24m 4moptions24m)1m] [-z 22m(4mshow24m 4mcurrent24m  4msettings24m)1m]  [-az  22m(4mshow0m
      4moutput24m 4mfile24m 4mname24m 4mand24m 4mexit24m)1m] [-ax 22m(4mshow24m 4moutput24m 4msuffix24m 4mand24m 4mexit24m)1m] [--show-0m
      1mschemes 22m(4mshow24m 4mresource24m 4mschemes24m)1m]0m

      1mImplementation options0m
      1m[-sparse 22m<int> (4msparse24m 4mmatrix24m 4mmultiplication24m 4mthreshold24m)1m]0m

      1mPruning options0m
      The following options all pertain to the various pruning strategies that
      can  be  employed by 1mmcl22m. They are described in the 1mPRUNING OPTIONS 22msec-
      tion, accompanied by a description of the mcl pruning strategy.  If your
      graphs are huge and you have an appetite for tuning, have a look at  the
      following:

      1m[-scheme  22m<int>  (4mresource24m  4mscheme24m)1m] [-resource 22m<int> (4mper-node24m 4mresource0m
      4mmaximum24m)1m] [-p 22m<num> (4mcutoff24m)1m] [-P 22m<int> (4m1/cutoff24m)1m] [-S 22m<int> (4mselection0m
      4mnumber24m)1m] [-R 22m<int> (4mrecovery24m 4mnumber24m)1m] [-pct 22m<int> (4mrecover24m  4mpercentage24m)1m]0m
      1m[-warn-pct  22m<int>  (4mprune24m  4mwarn24m  4mpercentage24m)1m] [-warn-factor 22m<int> (4mprune0m
      4mwarn24m 4mfactor24m)1m]0m

      The first argument of 1mmcl 22mmust be a file name, but some options are  al-
      lowed  to  appear  as  the first argument instead. These are the options
      that cause mcl to print out information of some  kind,  after  which  it
      will gracefully exit. The full list of these options is

      1m-z22m, 1m-h22m, 1m--help22m, 1m--version22m, 1m--show-settings22m, 1m--show-schemes22m, 1m--jury-char-0m
      1mter22m.

  1mDESCRIPTION0m
      1mmcl  22mimplements  the  1mMCL  algorithm22m, short for the 1mMarkov cluster algo-0m
      1mrithm22m, a cluster algorithm for graphs developed by Stijn van  Dongen  at
      the  Centre  for  Mathematics  and  Computer  Science  in Amsterdam, the
      Netherlands. The algorithm simulates flow using two simple algebraic op-
      erations on matrices.  The inception of this flow process and the theory
      behind it are described elsewhere  (see  1mREFERENCES22m).  Frequently  asked
      questions  are answered in the 1mmclfaq(7) 22msection.  The program described
      here is a fast threaded implementation written by the  algorithm's  cre-
      ator  with contributions by several others. Anton Enright co-implemented
      threading; see the 1mHISTORY/CREDITS 22msection for a complete account.   See
      the  1mAPPLICABILITY  22msection  for  a description of the type of graph mcl
      likes best, and for a qualitative assessment of its speed.  1mmcl  22mis  ac-
      companied  by several other utilities for analyzing clusterings and per-
      forming matrix and graph operations; see the 1mSEE ALSO 22msection.

      The first argument is the input file name, or a single  hyphen  to  read
      from  stdin. The rationale for making the name of the input file a fixed
      parameter is that you typically do several runs with  different  parame-
      ters.  In  command  line  mode it is pleasant if you do not have to skip
      over an immutable parameter all the time.

      The 1m-I 4m22mf24m option is the main control, affecting cluster granularity.   In
      finding good 1mmcl 22mparameter settings for a particular domain, or in find-
      ing  cluster structure at different levels of granularity, one typically
      runs mcl multiple times for varying values of f (refer to the  1m-I 4m22minfla-0m
      4mtion24m option for further information).

      1mNOTE 22mMCL interprets the matrix entries or graph edge weights as 1msimilar-0m
      1mities22m, and it likes 1mundirected input graphs 22mbest. It can handle directed
      graphs,  but  any  node pair (i,j) for which w(i,j) is much smaller than
      w(j,i) or vice versa will presumably have a slightly negative effect  on
      the  clusterings  output  by  mcl. Many such node pairs will have a dis-
      tinctly negative effect, so try to make your  input  graphs  undirected.
      How your edge weights are computed may affect mcl's performance. In pro-
      tein clustering, one way to go is to choose the negated logarithm of the
      BLAST probabilities (see 1mREFERENCES22m).

      1mmcl22m's default parameters should make it quite fast under almost all cir-
      cumstances.  Taking  default  parameters,  mcl has been used to generate
      good protein clusters on 133k proteins, taking 10 minutes  running  time
      on  a  Compaq  ES40 system with four alpha EV6.7 processors. It has been
      applied (with good results) to graphs with two million nodes, and if you
      have the memory (and preferably CPUs as well) nothing  should  stop  you
      from going further.

      For  large  graphs, there are several groups of parameters available for
      tuning the mcl computing process, should it be  necessary.  The  easiest
      thing  to  do  is  just vary the 1m-scheme 22moption. This triggers different
      settings for the group of pruning parameters 1m-p/-P22m, 1m-R22m,  1m-S22m,  and  1m-pct22m.
      The default setting corresponds with 1m-scheme 622m.  When doing multiple mcl
      runs for the same graphs with different 1m-I 22msettings (for obtaining clus-
      terings  at different levels of granularity), it can be useful to factor
      out the first bit of computation that is common to all  runs,  by  using
      the  1m-write-expanded  22moption  one  time and then using 1m-if 4m22minflation24m for
      each run in the set.  Whether mcl considers a graph large depends mainly
      on the graph connectivity; a highly connected graph on 50,000  nodes  is
      large  to  mcl  (so  that  you  might  want to tune resources) whereas a
      sparsely connected graph on 500,000 nodes may be business as usual.

      1mmcl 22mis a memory munger. Its precise appetite  depends  on  the  resource
      settings.  You  can get a rough (and usually much too pessimistic) upper
      bound for the amount of RAM that is needed by  using  the  1m-how-much-ram0m
      option.  The corresponding entry in this manual page contains the simple
      formula via which the upper bound is computed.

      Other options of interest are the option to specify threads 1m-te22m, and the
      verbosity-related options 1m-v 22mand 1m-V22m.  The actual settings are shown with
      1m-z22m, and for graphs with at most 12 nodes or so you can view the MCL  ma-
      trix  iterands  on  screen  by supplying 1m--show 22m(this may give some more
      feeling).

      MCL iterands allow a generic interpretation as clusterings as well.  The
      clusterings  associated with early iterands may contain a fair amount of
      overlap. Refer to the 1m-dump 22moption, the 1mmclfaq(7) 22mmanual,  and  the  1mclm0m
      1mimac  22mutility (Interpret Matrices As Clusterings).  Use 1mclm imac 22monly if
      you have a special reason; the normal usage of 1mmcl  22mis  to  do  multiple
      runs for varying 1m-I 22mparameters and use the clusterings output by mcl it-
      self.

      Under  very rare circumstances, 1mmcl 22mmight get stuck in a seemingly infi-
      nite loop. If the number of iterations exceeds a hundred and  the  4mchaos0m
      indicator  remains  nearly  constant (presumably around value 0.37), you
      can force mcl to stop by sending it the ALRM  signal  (usually  done  by
      1mkill  -s  ALRM 4m22mpid24m). It will finish the current iteration, and interpret
      the last iterand as a clustering. Alternatively, you can  wait  and  mcl
      might  converge  by itself or it will certainly stop after 10,000 itera-
      tions. The most probable explanation for such an infinite loop  is  that
      the  input  graph  contains  the flip-flop graph of node size three as a
      subgraph.

      The creator of this page feels that manual  pages  are  a  valuable  re-
      source, that online html documentation is also a good thing to have, and
      that  info  pages are way 4mway24m ahead of their time. The 1mNOTES 22msection ex-
      plains how this page was created.

      In the 1mOPTIONS 22msection options are listed in order of  importance,  with
      related options grouped together.

  1mOPTIONS0m
      1m-I 22m<num> (4minflation24m)
        Sets  the main inflation value to 4m<num>24m. This value is the main handle
        for affecting cluster granularity. It is usually chosen  somewhere  in
        the  range [1.2-5.0]. 1m-I 5.0 22mwill tend to result in fine-grained clus-
        terings, and 1m-I 1.2 22mwill tend to result in very coarse  grained  clus-
        terings.  Your  mileage  will vary depending on the characteristics of
        your data. That is why it is a good idea to test the quality  and  co-
        herency  of  your  clusterings  using 1mclm dist 22mand 1mclm info22m. This will
        most likely reveal that certain values of 1m-I 22mare simply not right  for
        your  data.  The  1mclm dist 22msection contains a discussion of how to use
        the cluster validation tools shipped with 1mmcl 22m(see the 1mSEE  ALSO  22msec-
        tion).

        With  low  values  for  1m-I22m, like 1m-I 1.222m, you should be prepared to use
        more resources in order to maintain quality of clusterings,  i.e.  in-
        crease the argument to the 1m-scheme 22moption.

      1m-o 22m<fname> (4moutput24m 4mfile24m 4mname24m)
      1m-odir 22m<dname> (4moutput24m 4mdirectory24m 4mname24m)
      1m--d 22m(4muse24m 4minput24m 4mdirectory24m 4mfor24m 4moutput24m)
        The  default  mode of output creation for 1mmcl 22mis to create a file name
        that uses the input file name stripped of any leading path components,
        augmented with a prefix 'out.' and a suffix encoding pivotal 1mmcl 22mpara-
        meters.  This will usually be the inflation value which is  the  argu-
        ment  to  the  1m-I 22moption. By default the output file is written in the
        current directory.  For example, if the input is named  data/small.mci
        for  example  and  inflation  is set to three, the output file will be
        named out.small.mci.I30.

        This behaviour can be overridden in various ways. The 1m-o 22moption simply
        specifies the output file name, which may include path components that
        should exist. It is possible to send the clustering to STDOUT by  sup-
        plying  1m-o -22m.  With the 1m-odir 4m22m<dname>24m option 1mmcl 22mconstructs the output
        file name as before, but writes the file  in  the  directory  4m<dname>24m.
        Finally,  the option 1m--d 22mis similar but more specific in that 1mmcl 22mwill
        write the output in the directory specified by the path  component  of
        the  input  file,  that  is, the directory in which the input file re-
        sides.

        If either one of 1m--abc22m, 1m--sif22m, 1m--etc 22mor 1m-use-tab 4m22mtab-file24m is used  the
        output will be in label format.  Otherwise the clustering is output in
        the  mcl  matrix format; see the 1mmcxio(5) 22msection for more information
        on this. Refer also to the group of options discussed at 1m--abc22m.

        Look at the 1m-ap 4m22mprefix24m option and its siblings for the automatic  nam-
        ing constructions employed by 1mmcl 22mif the 1m-o 22moption is not used.

      1m-c 22m<num> (4mreweight24m 4mloops24m)
        With  the  1m-c 4m22m<num>24m  option, as the final step of loop computation all
        loop weights are multiplied by 1m<num>22m, if supplied.

      1m--discard-loops22m=<y/n> (4mdiscard24m 4mloops24m 4min24m 4minput24m)
        By default 1mmcl 22mwill remove any loops that are present  in  the  input.
        Use  1m--discard-loops22m=1mn  22mto turn this off. Bear in mind that loops will
        still be modified in all cases where the loop weight  is  not  maximal
        among the list of edge weights for a given node.

      1m--abc 22m(4mexpect/write24m 4mlabels24m)
      1m--sif 22m(4mexpect/write24m 4mlabels24m)
      1m--etc 22m(4mexpect/write24m 4mlabels24m)
      1m--expect-values 22m(4mexpect24m 4mlabel:weight24m 4mformat24m)
      1m-use-tab 22m<fname> (4muse24m 4mmapping24m 4mto24m 4mwrite24m)
        These  items  all  relate  to  label input and/or label output.  1m--abc0m
        tells 1mmcl 22mto expect label input and output clusters in terms of  those
        labels.  This  simple  format expects two or three fields separated by
        white space on each line.  The first and second fields are interpreted
        as labels specifying source and  destination  node  respectively.  The
        third  field,  if  present, specifies the weight of the arc connecting
        the two nodes.

        The option 1m--sif 22mtells 1mmcl 22mto expect  SIF  (Simple  Interaction  File)
        format.  This  format  is line based. The first two fields specify the
        source node (as a label) and the relationship type. An arbitrary  num-
        ber of fields may follow, each containing a label identifying a desti-
        nation node.  The second field is simply ignored by 1mmcl22m.  As an exten-
        sion to the SIF format weights may optionally follow the labels, sepa-
        rated  from them with a colon character.  It is in this case necessary
        to use the 1m--expect-values 22moption.  The 1m--etc 22moption expects a  format
        identical  in  all  respects  except that the relationship type is not
        present, so that all fields after the first are interpreted as  desti-
        nation labels.

        1m-use-tab  22mis  only  useful when matrix input is used.  It will use the
        tab file to convert the output to labels; it does not fail on  indices
        missing  from the tab file, but will bind these to generated dummy la-
        bels.

      1m-tf 22m<tf-spec> (4mtransform24m 4minput24m 4mmatrix24m 4mvalues24m)
      1m-abc-tf 22m<tf-spec> (4mtransform24m 4minput24m 4mstream24m 4mvalues24m)
      1m--abc-neg-log10 22m(4mtake24m 4mlog1024m 4mof24m 4mstream24m 4mvalues,24m 4mnegate24m 4msign24m)
      1m--abc-neg-log 22m(4mtake24m 4mlog24m 4mof24m 4mstream24m 4mvalues,24m 4mnegate24m 4msign24m)
        1m-tf 22mtransforms the values of the input matrix according to  1m<tf-spec>22m.
        1m-abc-tf 22mtransforms the stream values (when 1m--abc 22mis used) according to
        1m<tf-spec>22m.   1m--abc-neg-log  22mand  1m--abc-neg-log10 22mimply that the stream
        input values are replaced by the negation of their log or  log10  val-
        ues,  respectively.   The  reason for their existence is documented in
        1mmcxio(5)22m.  For a description of the transform  language  excpected/ac-
        cepted in 1m<tf-spec> 22mrefer to the same.

      1m-icl 22m<fname> (4mcreate24m 4msubgraph24m 4mon24m 4mclustering24m)

        With this option 1mmcl 22mwill subcluster the provided clustering.  It does
        so by removing, first of all, all edges from the input graph that con-
        nect  different  clusters.   The resulting graph consists of different
        components, at least as many as there are clusters in the input  clus-
        tering.  This  graph  is then subjected to transformations, if any are
        specified, and then clustered.  The output name is constructed by  ap-
        pending the normal mcl-created file name suffix to the name of the in-
        put clustering.

      1m-write-graph 22m<fname> (4mwrite24m 4mgraph24m)
      1m-write-graphx 22m<fname> (4mwrite24m 4mtransformed24m 4mgraph24m)
      1m-write-expanded 22m<fname> (4mwrite24m 4mexpanded24m 4mgraph24m)
      1m--write-limit 22m(4mwrite24m 4mmcl24m 4mprocess24m 4mlimit24m)
        The first two options are somewhat outdated, in that the preferred way
        of loading networks is by using 1mmcxload(1)22m. The option 1m-write-expanded0m
        can  be  useful  for  exploring more complicated input transformations
        that incorporate an expansion step, but is  not  really  relevant  for
        production  use. The last option is mainly educational and for analyz-
        ing the 1mmcl 22mprocess itself.

      1m-scheme 22m<num> (4muse24m 4ma24m 4mpreset24m 4mresource24m 4mscheme24m)
      1m-resource 22m<num> (4mallow24m 4mn24m 4mneighbours24m 4mthroughout24m)
        There are currently seven different resource  schemes,  indexed  1..7.
        High  schemes  result in more expensive computations that may possibly
        be more accurate. The default scheme is 4. When 1mmcl 22mis done,  it  will
        give  a  grade (the so called 4mjury24m 4msynopsis24m) to the appropriateness of
        the scheme used. 4mA24m 4mlow24m 4mgrade24m 4mdoes24m 4mnot24m 4mnecessarily24m 4mimply24m 4mthat24m  4mthe24m  4mre-0m
        4msulting24m  4mclustering24m  4mis24m 4mbad24m - but anyway, a low grade should be reason
        to try for a higher scheme.

        Use the 1m-resource 4m22m<num>24m option to cap for each  nodes  the  number  of
        neighbours tracked during computation at 4m<num>24m nodes.

        The  1mPRUNING  OPTIONS 22msection contains an elaborate description of the
        way 1mmcl 22mmanages resources, should you be interested.  In case you  are
        worried  about  the  validation  of  the  resulting  clusterings,  the
        1mmclfaq(7) 22msection has several entries discussing this issue. The  bot-
        tom  line  is  that you have to compare the clusterings resulting from
        different schemes (and otherwise identical parameters) using utilities
        such as 1mclm dist22m, 1mclm info 22mon the one hand, and your own  sound  judg-
        ment on the other hand.

        If  your  input  graph is extremely dense, with an average node degree
        (i.e. the number of neighbours per node) that is somewhere above  500,
        you  may need to filter the input graph by removing edges, for example
        by using one of 1m-tf '#ceilnb()' 22mor 1m-tf '#knn()'22m.

      1m--show-schemes 22m(4mshow24m 4mpreset24m 4mresource24m 4mschemes24m)
        Shows the explicit settings to which the different preset schemes cor-
        respond.

        The characteristics are written in the same format (more or  less)  as
        the output triggered by 1m-v pruning22m.

      1m-V 22m<str> (4mverbosity24m 4mtype24m 4moff24m)
        See the 1m-v 22moption below.

      1m-v 22m<str> (4mverbosity24m 4mtype24m 4mon24m)
        These are the different verbosity modes:

        1mpruning0m
        1mexplain0m
        1mcls0m
        1mall0m

      1m-q 22m<spec> (4mlog24m 4mlevels24m)

        To make mcl as quiet as can be, add 1m-q x -V all 22mto the command line.

        The  1m-q  22moption  governs  a general logging mechanism.  The format ac-
        cepted is described in the 1mtingea.log(7) 22mmanual page.

        The other options govern verbosity  levels  specific  to  mcl.  1m-v all0m
        turns  them  all on, 1m-V all 22mturns them all off. 1m-v 4m22mstr24m and 1m-V 4m22mstr24m turn
        on/off the single mode 4mstr24m (for 4mstr24m equal to one of 1mpruning22m,  1mcls22m,  or
        1mexplain22m). Each verbosity mode is given its own entry below.

      1m-v explain0m
        This  mode  causes  the output of explanatory headers illuminating the
        output generated with the 1mpruning 22mverbosity mode.

      1m-v pruning0m
        This mode causes output of resource-related quantities. It has a sepa-
        rate entry in the PRUNING OPTIONS section.

      1m-v cls0m
        This mode (on by default) prints a terse list  of  characteristics  of
        the  clusterings associated with intermediate iterands. The character-
        istics are 1mE/V22m, 1mcls22m, 1molap22m, and 1mdd22m. They  respectively  stand  for  the
        number  of outgoing arcs per node (as an average), the number of clus-
        ters in the overlapping clustering associated with  the  iterand,  the
        number  of nodes in overlap, and the 4mdag24m 4mdepth24m associated with the DAG
        (directed acyclic graph) associated with the iterand. For more  infor-
        mation  on this DAG refer to the 1m-dump 22moption description in this man-
        ual and also 1mmclfaq(7)22m.

        1mStandard log information0m

        m-ie This gives the ratio of (1) the number of edges after initial ex-
             pansion, before pruning, to (2) the number of edges of  the  cur-
             rent iterand.
        m-ex This  gives  the ratio of (1) the number of edges after expansion
             (including pruning), to (2) the number of edges  of  the  current
             iterand.
        i-ex This  gives  the ratio of (1) the number of edges after expansion
             (including pruning), to (2) the number of edges of  the  original
             input graph.
        fmv  This  gives  the  percentage  of nodes (matrix columns) for which
             full matrix/vector computation was used (as opposed  to  using  a
             sparse technique).

      1m-aa 22m<str> (4mappend24m 4m<str>24m 4mto24m 4msuffix24m)
        See the 1m-ap 22moption below.

      1m-ap 22m<str> (4muse24m 4m<str>24m 4mas24m 4mfile24m 4mname24m 4mprefix24m)
        If  the  1m-o 4m22mfname24m option is not used, 1mmcl 22mwill create a file name (for
        writing output to) that should uniquely characterize the important pa-
        rameters used in the current invocation of mcl. The default format  is
        1mout.fname.suf22m,  where  1mout  22mis simply the literal string out, 1mfname 22mis
        the first argument containing the name of the file (with the graph) to
        be clustered, and where 1msuf 22mis the suffix encoding a set of parameters
        (described further below).

        The 1m-ap 4m22mstr24m option specifies a prefix to use rather than 1mout.fname  22mas
        sketched  above.   However,  1mmcl  22mwill interpret the character '=', if
        present in 4mstr24m, as a placeholder for the input file name.

        If the 1m-aa 4m22mstr24m option is used, 1mmcl 22mwill append 1mstr 22mto the  suffix  1msuf0m
        created  by itself.  You can use this if you need to encode some extra
        information in the file name suffix.

        The suffix is constructed as follows. The 1m-I 4m22mf24m and  1m-scheme  22mparameter
        are  always  encoded.   Other options, such as 1m-pi 4m22mf24m and 1m-knn 22mare only
        encoded if they are used. Any real argument 4mf24m is encoded using 4mexactly0m
        4mone24m trailing digit behind the decimal separator (which itself  is  not
        written).  The setting 1m-I 3.14 22mis thus encoded as I31. The 1m-scheme 22mop-
        tion is encoded using the letter 's', all other options mentioned here
        are encoded as themselves (stripped of the hyphen). For example

        mcl small.mci -I 3 -c 2.5 -pi 0.8 -scheme 5

        results in the file name out.small.mci.I30s5c25pi08.  If you  want  to
        know beforehand what file name will be produced, use the 1m-az 22moption.

      1m-az 22m(4mshow24m 4moutput24m 4mfile24m 4mname24m 4mand24m 4mexit24m)
      1m-ax 22m(4mshow24m 4moutput24m 4msuffix24m 4mand24m 4mexit24m)
        If  1mmcl  22mautomatically  constructs  a  file name, it can be helpful to
        known beforehand what that file name will be. Use  1m-az  22mand  mcl  will
        write the file name to STDOUT and exit. This can be used if mcl is in-
        tegrated  into  other  software  for  which  the automatic creation of
        unique file names is convenient.

        By default mcl incorporates the input file name into the  output  file
        name  and  appends a short suffix describing the most important option
        settings. Use 1m-ax 22mto find out what that suffix is.  This can be useful
        in wrapper pipeline scripts such as clxcoarse.

      1m-annot 22m<str> (4mdummy24m 4mannotation24m 4moption24m)
        1mmcl 22mwrites the command line with which it was invoked  to  the  output
        clustering  file.  Use  this option to include any additional informa-
        tion. MCL does nothing with this option except copying it as just  de-
        scribed.

      1m-te 22m<int> (4m#expansion24m 4mthreads24m)
        Threading  is  useful  if  you have a multi-processor system. 1mmcl 22mwill
        spawn 4mk24m threads of computation. If  these  are  computed  in  parallel
        (this  depends  on the number of CPUs available to the mcl process) it
        will speed up the process accordingly.

        When threading, it is best not to turn on pruning  verbosity  mode  if
        you  are letting mcl run unattended, unless you want to scrutinize its
        output later. This is because it makes 1mmcl 22mrun  somewhat  slower,  al-
        though the difference is not dramatic.

      1m-pi 22m<num> (4mpre-inflation24m)
        If  used,  1mmcl 22mwill apply inflation one time to the input graph before
        entering the main process. This can be  useful  for  making  the  edge
        weights  in  a graph either more homogeneous (which may result in less
        granular clusterings) or more heterogeneous (which may result in  more
        granular  clusterings).  Homogeneity is achieved for values 4m<num>24m less
        than one, heterogeneity for values larger than one.  Values to try are
        normally in the range [2.0,10.0].

      1m-if 22m<num> (4mstart-inflation24m)
        If used, 1mmcl 22mwill apply inflation one time to the input  graph  before
        entering  the  main  process. The difference with 1m-pi 22mis that with the
        latter option mcl may apply certain transformations after  reading  in
        the  matrix  such as adding or modifying loops. The purpose of the 1m-if0m
        (mnemonic for 4minflation-first24m) option is to use  it  on  graphs  saved
        with  the 1m--write-expanded 22moption and convey to mcl that it should not
        apply those transformations.

      1m-dump-interval 22m<i:j> (4mdump24m 4minterval24m)
      1m-dump-interval 4m22mall0m
        Dump during iterations i..j-1. Use 4mall24m to dump in all iterations.  See
        the 1m-dump 4m22mstr24m option below.

      1m-dump-modulo 22m<int> (4mdump24m 4mi+0..i+<int>..24m)
        Sampling rate: select only these iterations in the dump interval.  See
        the 1m-dump 4m22mstr24m option below.

      1m-dump-stem 22m<stem> (4mfile24m 4mstem24m)
        Set  the  the stem for file names of dumped objects (default 4mmcl24m). See
        the 1m-dump 4m22mstr24m option below.

      1m-dump 22m<str> (4mtype24m)
        4mstr24m is checked for substring occurrences  of  the  following  entries.
        Repeated use of 1m-dump 22mis also allowed.

        1mite0m
        1mdag0m
        1mcls0m
        1mchr0m
        1mlines0m
        1mcat0m

        1mlines  22mand  1mcat 22mchange the mode of dumping. The first changes the dump
        format to a line based pairwise format rather than the default mcl ma-
        trix format. The second causes all dumped items to be  dumped  to  the
        default  stream  used  for the output clustering, which is appended at
        the end.

        The 1mite 22moption writes 1mmcl 22miterands to  file.  The  1mcls  22moption  writes
        clusterings  associated with mcl iterands to file.  These clusters are
        obtained from a particular directed acyclic graph (abbreviated as DAG)
        associated with each iterand. The 1mdag 22moption writes that DAG to  file.
        The DAG can optionally be further pruned and then again be interpreted
        as  a  clustering  using 1mclm imac22m, and 1mclm imac 22mcan also work with the
        matrices written using the 1mite 22moption.  It should be noted that  clus-
        terings  associated  with  intermediate  iterands may contain overlap,
        which is interesting in many applications. For more information  refer
        to 1mmclfaq(7) 22mand the 1mREFERENCES 22msection below.

        The 1mresult 22moption dumps the usual MCL clustering.

        The  1mchr  22moption  says,  for each iterand I, to output a matrix C with
        characteristics of I. C has the same number of columns as I. For  each
        column k in C, row entry 0 is the diagonal or 'loop' value of column k
        in  I 4mafter24m expansion and pruning, and 4mbefore24m inflation and rescaling.
        Entry 1 is the loop value 4mafter24m inflation and rescaling.  Entry  2  is
        the center of column k (the sum of its entries squared) computed 4mafter0m
        expansion  and  4mbefore24m  pruning, entry 3 is the maximum value found in
        that column at the same time. Entry 4 is the amount of mass  kept  for
        that column 4mafter24m 4mpruning24m.

        The 1m-ds 22moption sets the stem for file names of dumped objects (default
        4mmcl24m).  The  1m-di  22mand  1m-dm  22moptions allow a selection of iterands to be
        made.

      1m-digits 22m<int> (4mprinting24m 4mprecision24m)
        This has two completely different uses. It sets the number of decimals
        used for pretty-printing 1mmcl 22miterands when  using  the  1m--show  22moption
        (see  below),  and it sets the number of decimals used for writing the
        expanded matrix when using the 1m-write-expanded 22moption.

      1m--show 22m(4mprint24m 4mmatrices24m 4mto24m 4mscreen24m)
        Print matrices to screen. The  number  of  significant  digits  to  be
        printed can be tuned with 1m-digits 4m22mn24m. An 80-column screen allows graphs
        (matrices)  of size up to 12(x12) to be printed with three digits pre-
        cision (behind the comma), and of size up to 14(x14) with two  digits.
        This  can give you an idea of how 1mmcl 22moperates, and what the effect of
        pruning is.  Use e.g. 1m-S 6 22mfor such a small graph and view the MCL ma-
        trix iterands with 1m--show22m.

      1m--write-binary 22m(4moutput24m 4mformat24m)
        Write matrix dump output in binary mcl format rather than  interchange
        mcl  format (the default). Note that 1mmcxconvert 22mcan be used to convert
        each one into the other.  See 1mmcxio(5) 22mand 1mmcx(1)  22mfor  more  informa-
        tion.

      1m-sort 22m<str> (4msort24m 4mmode24m)
        4mstr24m  can  be  one of 1mlex22m, 1msize22m, 1mrevsize22m, or 1mnone22m. The default is 'rev-
        size', in which the largest  clusters  come  first.  If  the  mode  is
        'size',  smallest  clusters come first, if the mode is 'lex', clusters
        are ordered lexicographically, and if the mode is 'none', the order is
        the same as produced by the procedure used by mcl to map matrices onto
        clusterings.

      1m-overlap 22m<str> (4moverlap24m 4mmode24m)
        Mode 4mkeep24m causes mcl to retain overlap should  this  improbable  event
        occur. In theory, 1mmcl 22mmay generate a clustering that contains overlap,
        although  this  almost  never happens in practice, as it requires some
        particular type of symmetry to be present in the input graph (not just
        any symmetry will do). Mathematically speaking, this is  a  conjecture
        and  not  a  theorem,  but  the present author will eat his shoe if it
        fails to be true (for marzipan values of shoe). It is easy  though  to
        construct  an  input  graph  for  which certain mcl settings result in
        overlap - for example a line graph on an odd number of nodes. The  de-
        fault is to excise overlapping parts and introduce them as clusters in
        their  own  right.  It is possible to allocate nodes in overlap to the
        first cluster in which they occur (i.e.  rather  arbitrarily),  corre-
        sponding with mode 4mcut24m.

        In  mode  4msplit24m  mcl will put all nodes in overlap into separate clus-
        ters. These clusters are chosen such that two nodes  are  put  in  the
        same  new cluster if and only if they always occur paired in the clus-
        ters of the overlapping clustering.

        This option has no effect on the clusterings that are output when  us-
        ing  1m-dump 4m22mcls24m - the default for those is that overlap is not touched,
        and this default can not yet be overridden.

      1m--force-connected22m=<y/n> (4manalyze24m 4mcomponents24m)
      1m--check-connected22m=<y/n> (4manalyze24m 4mcomponents24m)
        If the input graph has strong bipartite characteristics, mcl may yield
        clusters that do not correspond to connected components in  the  input
        graph. Turn one of these modes on to analyze the resultant clustering.

        If loose clusters are found they will be split into subclusters corre-
        sponding  to  connected components.  With 1m--force-connected22m=4my24m mcl will
        write the corrected clustering to the normal output file, and the  old
        clustering  to  the  same  file  with  suffix orig.  With 1m--check-con-0m
        1mnected22m=4my24m mcl will write the loose  clustering  to  the  normal  output
        file, and the corrected clustering to the same file with suffix coco.

        These  options  are  not  on  by default, as the analysis is currently
        (overly) time-consuming and mcl's behaviour actually makes some  sense
        (when taking bipartite characteristics into account).

      1m--analyze22m=<y/n> (4mperformance24m 4mcriteria24m)
        With this mode turned on, 1mmcl 22mwill reread the input matrix and compute
        a  few performance criteria and attach them to the output file. Off by
        default.

      1m--show-log22m=<y/n> (4mshow24m 4mlog24m)
        Shows the log with process characteristics  on  STDOUT.   By  default,
        this mode is off.

      1m--jury-charter 22m(4mexplains24m 4mjury24m)
        Explains how the jury synopsis is computed from the jury marks.

      1m--version 22m(4mshow24m 4mversion24m)
        Show version.

      1m-how-much-ram 22m<int> (4mRAM24m 4mupper24m 4mbound24m)
        1m<int>  22mis  interpreted  as the number of nodes of an input graph.  mcl
        will print the maximum amount of RAM it needs  for  its  computations.
        The formula for this number in bytes is:

           2 * c * k * <int>

           2  :  two matrices are concurrently held in memory.
           c  :  mcl cell size (as shown by -z).
         <int>:  graph cardinality (number of nodes).
           k  :  MAX(s, r).
           s  :  select number (-S, -scheme options).
           r  :  recover number (-R, -scheme options).

        This  estimate  will usually be too pessimistic. It does assume though
        that the average node degree of the input graph does not exceed k. The
        1m-how-much-ram 22moption takes other command-line arguments  into  account
        (such  as  1m-S  22mand 1m-R22m), and it expresses the amount of RAM in megabyte
        units.

      1m-h 22m(4mshow24m 4mhelp24m)
        Shows a selection of the most important 1mmcl 22moptions.

      1m--help 22m(4mshow24m 4mhelp24m)
        Gives a one-line description for all options.

      1m-z 22m(4mshow24m 4msettings24m)
        Show current settings for tunable parameters.   1m--show-settings  22mis  a
        synonym.

  1mPRUNING OPTIONS0m
      1m-p 22m<num> (4mcutoff24m)
      1m-P 22m<int> (4m1/cutoff24m)
      1m-S 22m<int> (4mselection24m 4mnumber24m)
      1m-R 22m<int> (4mrecover24m 4mnumber24m)
      1m-pct 22m<pct> (4mrecover24m 4mpercentage24m)
        After  computing a new (column stochastic) matrix vector during expan-
        sion (which is matrix multiplication c.q.  squaring),  the  vector  is
        successively  exposed  to  different pruning strategies. The intent of
        pruning is that many small entries are removed while retaining much of
        the stochastic mass of the original vector. After pruning, vectors are
        rescaled to be stochastic again. MCL iterands are theoretically  known
        to  be  sparse in a weighted sense, and this manoever effectively per-
        turbs the MCL process a little in order to obtain  matrices  that  are
        genuinely  sparse,  thus keeping the computation tractable. An example
        of monitoring pruning can be found in the discussion of 1m-v pruning  22mat
        the end of this section.

        1mmcl  22mproceeds  as follows. First, entries that are smaller than 4mcutoff0m
        are removed, resulting in a vector with at most 4m1/cutoff24m entries.  The
        cutoff  can  be  supplied either by 1m-p22m, or as the inverse value by 1m-P22m.
        The latter is more intuitive, if your intuition is like mine (P stands
        for precision or pruning).  The cutoff just described is rigid; it  is
        the same for all vectors. The 1m--adapt 22moption causes the computation of
        a  cutoff  that depends on a vector's homogeneity properties, and this
        option may or may not speed up mcl.

        Second, if the remaining stochastic mass (i.e. the sum of all  remain-
        ing  entries)  is  less than 4m<pct>24m/100 and the number of remaining en-
        tries is less than 4m<r>24m (as specified by the 1m-R 22mflag), 1mmcl 22mwill try  to
        regain  ground  by recovering the largest discarded entries. The total
        number of entries is not allowed to grow larger than 4m<r>24m.  If recovery
        was not necessary, mcl tries to prune the vector further  down  to  at
        most  4ms24m  entries (if applicable), as specified by the 1m-S 22mflag. If this
        results in a vector that satisfies the recovery condition then  recov-
        ery  is attempted, exactly as described above. The latter will not oc-
        cur of course if 4m<r>24m <= 4m<s>24m.

        The default setting is something like 1m-P 4000 -S 500 -R 60022m. Check the
        1m-z 22mflag to be sure. There is a set of precomposed settings, which  can
        be  triggered  with  the  1m-scheme 4m22mk24m option. 4mk24m=4 is the default scheme;
        higher values for 4mk24m result in costlier and more accurate  computations
        (vice  versa  for lower, cheaper, and less accurate).  The schemes are
        listed using the 1m--show-schemes 22moption. It is  advisable  to  use  the
        1m-scheme  22moption  only in interactive mode, and to use the explicit ex-
        pressions when doing batch processing. The reason is that there is  4mno0m
        4mguarantee24m  4mwhatsoever24m that the schemes will not change between differ-
        ent releases. This is because the scheme options should  reflect  good
        general  purpose  settings,  and  it  may become appararent that other
        schemes are better.

        Note that 'less accurate' or 'more accurate'  computations  may  still
        generate  the  same output clusterings. Use 1mclm dist 22mto compare output
        clusterings for different resource parameters. Refer to 1mclm dist 22mfor a
        discussion of this issue.

      1m-warn-pct 22m<int> (4mprune24m 4mwarn24m 4mpercentage24m)
      1m-warn-factor 22m<int> (4mprune24m 4mwarn24m 4mfactor24m)
        The two options 1m-warn-pct 22mand 1m-warn-factor 22mrelate to warnings that may
        be triggered once the 4minitial24m pruning of a vector  is  completed.  The
        idea  is  to  issue  warnings if initial pruning almost completely de-
        stroys a computed vector, as this may be a sign that the pruning para-
        meters should be changed. It depends on the mass remaining after  ini-
        tial  pruning  whether  a warning will be issued. If that mass is less
        than 4mwarn-pct24m or if the number of remaining entries is  smaller  by  a
        factor 4mwarn-factor24m than both the number of entries originally computed
        4mand24m the recovery number, in that case, 1mmcl 22mwill issue a warning.

        1m-warn-pct  22mtakes an integer between 0 and 100 as parameter, 1m-warn-fac-0m
        1mtor 22mtakes a real positive number. They default to  something  like  30
        and  50.0. If you want to see less warnings, decrease 4mwarn-pct24m and in-
        crease 4mwarn-factor24m. Set 4mwarn-factor24m to zero if you want no warnings.

      1m-v pruning0m
        Pruning verbosity mode causes 1mmcl 22mto emit several  statistics  related
        to  the  pruning process, each of which is described below. Use 1m-v ex-0m
        1mplain 22mto get explanatory headers in the output as well (or simply  use
        1m-v all22m).

  1mIMPLEMENTATION OPTIONS0m
      1m-sparse 22m<int> (4msparse24m 4mmatrix24m 4mmultiplication24m 4mthreshold24m)
        This  value  (by  default  set  to 10) determines when mcl switches to
        sparse matrix/vector multiplication.  For a  given  column  stochastic
        vector  (corresponding  with  all the neighbours of a given node v ac-
        cording to the current mcl iterand) the sum S of neighbour  counts  of
        all  neighbours of v is computed, counting duplicates. This is exactly
        the number of matrix entries involved in the computation  of  the  new
        column vector for the matrix product. If S times 4m<int>24m does not exceed
        the  number of nodes in the graph (equal to both column and row dimen-
        sion of the matrices used) then a sparse implementation is used.  Oth-
        erwise  an optimized regular implementation is used. Intuitively, this
        option can be thought of as the estimated overhead per matrix floating
        point operation incurred by the sparse  implementation  compared  with
        the  regular  implementation.  MCL uses this estimated overhead to de-
        termine which implementation is likely  to  be  quicker.  Testing  has
        shown  this  strategy  works  very  well for graphs of a wide range of
        sizes, including graphs with up to 3 million  nodes  and  500  million
        edges.

        1mNOTE0m
        The  effectiveness  of  this option is influenced by hardware-specific
        properties such as the CPU L2 cache size.  The  default  value  should
        work reasonably well across a wide variety of scenarios, but it may be
        possible to squeeze faster run times out of mcl by tuning this parame-
        ter to the graphs that are specific for your application domain.

  1mEXAMPLES0m
      The following is an example of label input

      ---8<------8<------8<------8<------8<---
      cat hat  0.2
      hat bat  0.16
      bat cat  1.0
      bat bit  0.125
      bit fit  0.25
      fit hit  0.5
      hit bit  0.16
      --->8------>8------>8------>8------>8---

      It can be clustered like this:

      mcl cathat --abc -o out.cathat

      The file out.cathat should now like like this

      ---8<------8<------8<------8<------8<---
      cat hat bat
      bit fit hit
      --->8------>8------>8------>8------>8---

      A  few things to note. First, MCL will symmetrize any arrow it finds. If
      it sees bat cat 1.0 it will act as if it also saw cat bat 1.0.  You  can
      explicitly specify cat bat 1.0, mcl will in the first parse stage simply
      end  up  with duplicate entries. Second, MCL deduplicates repeated edges
      by taking the one with the maximum value. So,

      ---8<------8<------8<------8<------8<---
      cat hat  0.2
      hat cat  0.16
      hat cat  0.8
      --->8------>8------>8------>8------>8---

      Will result in two arrows cat-hat and hat-cat both with value 0.8.

  1mAPPLICABILITY0m
      1mmcl 22mwill work very well for graphs in which the diameter of the  natural
      clusters  is not too large. The presence of many edges between different
      clusters is not problematic; as long as there is cluster structure,  mcl
      will  find  it.  It is less likely to work well for graphs with clusters
      (inducing subgraphs) of large diameter, e.g.  grid-like  graphs  derived
      from  Euclidean  data. So mcl in its canonical form is certainly not fit
      for boundary detection or image segmentation. I experimented with a mod-
      ified mcl and boundary detection in the thesis  pointed  to  below  (see
      1mREFERENCES22m).  This  was fun and not entirely unsuccessful, but not some-
      thing to be pursued further.

      1mmcl 22mlikes 4mundirected24m 4minput24m 4mgraphs24m 4mbest24m, and it  really  dislikes  graphs
      with  node pairs (i,j) for which an arc going from i to j is present and
      the counter-arc from j to i is absent. Try  to  make  your  input  graph
      undirected.  Furthermore, mcl interprets edge weights in graphs as simi-
      larities. If you are used to working with dissimilarities, you will have
      to convert those to similarities using some conversion formula. The most
      important  thing  is  that  you feel confident that the similarities are
      reasonable, i.e. if X is similar to Y with weight 2, and X is similar to
      Z with weight 200, then this should mean that the similarity of Y (to X)
      is neglectible compared with the similarity of Z (to X).

      1mmcl 22mis probably not suited for clustering 4mtree24m 4mgraphs24m. This  is  because
      mcl  works  best  if there are multiple paths between different nodes in
      the natural clusters, but in tree graphs there is only one path  between
      any pair of nodes. Trees are too sparse a structure for mcl to work on.

      1mmcl  22mmay  well  be suited for clustering 4mlattices24m. It will depend on the
      density characteristics of the lattice, and the conditions  for  success
      are  the same as those for clustering graphs in general: The diameter of
      the natural clusters should not be too large.  1mNOTE  22mwhen  clustering  a
      lattice,  you  4mhave24m  to cluster the underlying undirected graph, and not
      the directed graph that represents the lattice  itself.  The  reason  is
      that one has to allow mcl (or any other cluster algorithm) to 'look back
      in  time',  so  to  speak. Clustering and directionality bite each other
      (long discussion omitted).

      1mmcl 22mhas a worst-case time complexity O(N*k^2), where N is the number  of
      nodes  in  the  graph, and k is the maximum number of neighbours tracked
      during computations. k depends on the 1m-P 22mand 1m-S 22moptions. If the  1m-S  22mop-
      tion is used (which is the default setting) then k equals the value cor-
      responding  with  this  option.  Typical  values  for k are in the range
      500..1000. The average case is much better than the worst  case  though,
      as  cluster  structure  itself  has  the effect of helping mcl's pruning
      schemes, certainly if the diameter of natural clusters is not large.

  1mFILES0m
      There are currently no resource nor configuration files.  The mcl matrix
      format is described in the 1mmcxio(5) 22msection.

  1mENVIRONMENT0m
      MCLXIODIGITS
        When writing matrices in interchange format, mcl will use  this  vari-
        able (if present) as the precision (number of digits) for printing the
        fractional part of values.

      MCLXIOVERBOSITY
        MCL  and its sibling applications will usually report about matrix in-
        put/output from/to disk. The verbosity  level  can  be  regulated  via
        MCLXIOVERBOSITY. These are the levels it can currently be set to.

        1 Silent but applications may alter this.
        2 Silent and applications can not alter this.
        4 Verbose but applications may alter this.
        8 Verbose and applications can not alter this (default).

      MCLXIOFORMAT
        MCL  and  its  sibling applications will by default output matrices in
        interchange format rather than binary format (cf. 1mmcxio(5)22m).  The  de-
        sired  format  can  be controlled via the variable MCLXIOFORMAT. These
        are the levels it can currently be set to.

        1 Interchange format but applications may alter this.
        2 Interchange format and applications can not alter this (default).
        4 Binary format but applications may alter this.
        8 Binary format and applications can not alter this.

      MCLXICFLAGS
        If matrices are output in interchange format, by default empty vectors
        will not be listed. Equivalently  (during  input  time),  vectors  for
        which no listing is present are understood to be empty - note that the
        4mpresence24m of a vector is established using the domain information found
        in  the  header part.  It is possible to enforce listing of empty vec-
        tors by setting bit '1' in the variable MCLXICFLAGS.

      MCLXIOUNCHECKED
        MCL and its sibling applications will always check a matrix  for  con-
        sistency  while it is being read. If this variable is set, the consis-
        tency check is omitted. For large graphs the speed up can be consider-
        able. However, if the input graph is not  conforming  it  will  likely
        crash the application that is using it.

  1mDIAGNOSTICS0m
      If 1mmcl 22missues a diagnostic error, it will most likely be because the in-
      put  matrix could not be parsed succesfully.  1mmcl 22mtries to be helpful in
      describing the kind of parse error.  The mcl matrix format is  described
      in the 1mmcxio(5) 22msection.

  1mBUGS0m
      No known bugs at this time.

  1mAUTHOR0m
      Stijn van Dongen.

  1mHISTORY/CREDITS0m
      The  MCL  algorithm  was conceived in spring 1996 by the present author.
      The first implementation of the MCL algorithm followed that  spring  and
      summer.  It  was  written  in Perl and proved the viability of the algo-
      rithm. The implementation described here began its life in autumn  1997.
      The  first versions of the vital matrix library were designed jointly by
      Stijn van Dongen and Annius Groenink in the period Oktober  1997  -  May
      1999.  The efficient matrix-vector multiplication routine was written by
      Annius. This routine is without significant changes  still  one  of  the
      cornerstones of this MCL implementation.

      Since May 1999 all MCL libraries have seen much development and redesign
      by  the  present author. Matrix-matrix multiplication has been rewritten
      several times to take full advantage of the sparseness properties of the
      stochastic matrices brought forth by the MCL algorithm. This mostly con-
      cerns the issue of pruning - removal of small elements in  a  stochastic
      column in order to keep matrices sparse.

      Very instructive was that around April 2001 Rob Koopman pointed out that
      selecting  the  k largest elements out of a collection of n is best done
      using a min-heap. This was the key to  the  second  major  rewrite  (now
      counting  three)  of  the  MCL pruning schemes, resulting in much faster
      code, generally  producing  a  more  accurate  computation  of  the  MCL
      process.

      In May 2001 Anton Enright initiated the parallellization of the 1mmcl 22mcode
      and  threaded  inflation.  From  this example, Stijn threaded expansion.
      This was great, as the MCL data structures and operands  (normal  matrix
      multiplication  and  Hadamard multiplication) just beg for parallelliza-
      tion.

      Onwards.   The  January  2003  03-010  release  introduced  support  for
      sparsely enumerated (i.e. indices need not be sequential) graphs and ma-
      trices,  the  result  of a major overhaul of the matrix library and most
      higher layers.  Conceptually, the library now sees matrices as  infinite
      quadrants  of  which  only finite subsections happen to have nonzero en-
      tries.

      The June 2003 03-154 release introduced unix-type pipelines for cluster-
      ing, including the BLAST parser mcxdeblast and the mclblastline  script.
      The  April  2004  04-105 release revived binary format, which has been a
      first class citizen every since.

      With the March 2005 05-090 release mcxsubs finally acquired a sane spec-
      ification syntax. The November 2005 05-314 release brought  the  ability
      to  stream  label input directly into mcl. The subsequent release intro-
      duced a transformation language shared by various mcl siblings that  al-
      lows  arbitrary  progressions of transformations to be applied to either
      stream values or matrix values.

      Joost van Baal set up the mcl CVS  tree  and  packaged  mcl  for  Debian
      GNU/Linux.  He  completely  autotooled  the  sources, so much so that at
      first I found it hard to find them back  amidst  bootstrap,  aclocal.m4,
      depcomp, and other beauties.

      Jan  van der Steen shared his elegant mempool code. Philip Lijnzaad gave
      useful comments.  Philip,  Shawn  Hoon,  Abel  Ureta-Vidal,  and  Martin
      Mokrejs sent helpful bug reports.

      Abel  Ureta-Vidal  and  Dinakarpandian  Deendayal  commented on and con-
      tributed to mcxdeblast and mcxassemble.

      Tim Hughes contributed several good bug reports for mcxassemble,  mcxde-
      blast and zoem.

  1mSEE ALSO0m
      1mmclfaq(7) 22m- Frequently Asked Questions.

      1mmcxio(5) 22m- a description of the mcl matrix format.

      There  are  many more utilities. Consult 1mmclfamily(7) 22mfor an overview of
      and links to all the documentation and the utilities in the mcl family.

      1mminimcl 22mis a 200-line perl implementation of mcl. It is shipped  in  the
      mcl distribution and can be found online at http://micans.org/mcl.

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

  1mREFERENCES0m
      [1]  Stijn  van  Dongen,  4mGraph24m  4mClustering24m  4mVia24m  4ma24m  4mDiscrete24m 4mUncoupling0m
      4mProcess24m,   SIAM   Journal   on   Matrix   Analysis   and   Applications,
      30(1):121-141, 2008.  http://link.aip.org/link/?SJMAEL/30/121/1

      [2]  Enright  A.J., Van Dongen S., Ouzounis C.A.  4mAn24m 4mefficient24m 4malgorithm0m
      4mfor24m 4mlarge-scale24m 4mdetection24m 4mof24m 4mprotein24m 4mfamilies24m,  Nucleic  Acids  Research
      30(7):1575-1584 (2002).

      [3]  Stijn van Dongen, 4mGraph24m 4mClustering24m 4mby24m 4mFlow24m 4mSimulation24m.  PhD thesis,
      University of Utrecht, May 2000.
      http://www.library.uu.nl/digiarchief/dip/diss/1895620/inhoud.htm

      [4] Stijn van Dongen and Cei Abreu-Goodger, 4mUsing24m 4mmcl24m 4mto24m  4mextract24m  4mclus-0m
      4mters24m  4mfrom24m 4mnetworks24m, in 4mBacterial24m 4mMolecular24m 4mNetworks:24m 4mMethods24m 4mand24m 4mProto-0m
      4mcols24m, Methods in Molecular  Biology,  Vol  804,  pages  281-295  (2012).
      PMID 22144159.
      http://www.ncbi.nlm.nih.gov/pubmed/22144159

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

  mcl 22-282                        9 Oct 2022                            4mmcl24m(1)
