CLMDIST(1)

📦
version 22-282 · 2 versions
  • 22-282 · debian bookworm, debian trixie, ubuntu noble, ubuntu questing, ubuntu resolute, ubuntu stonking (latest)
  • 14-137 · ubuntu jammy
, in debian bookworm, debian trixie, ubuntu noble, ubuntu questing, ubuntu resolute, ubuntu stonking

💖 clm dist(1) — USER COMMANDS 💖

okay bestie, buckle up, we're doing clm dist today. this is the clm dist(1) page and it's lowkey a whole journey. it's long, so we're doing it in parts — this is part 1, don't go anywhere 🌸

✨ NAME ✨

clm_dist — compute the distance between two or more partitions (clusterings).

the distance that gets computed can be any of: split/join distance, variance of information, or Mirkin metric. take your pick 💅

real talk though: clmdist is not in actual fact a program. this manual page documents the behaviour and options of the clm program when invoked in mode dist. the options -h, --apropos, --version, -set, --nop are accessible in all clm modes. they are described in the clm manual page. iykyk 🫶

🌈 SYNOPSIS 🌈

clm dist [options] <file name> <file name>+
clm dist [-mode <sj|vi|mk|sc> (distance type)] [-o fname (output file)]
[--chain (only compare consecutive clusterings)] [--one-to-many (compare
first clustering to all others)] [--sort (sort clusterings based on
coarseness)] [--index (output Rand, adjusted Rand and Jaccard indices)]
[-digits k (output decimals)] [-h (print synopsis, exit)] [--apropos
(print synopsis, exit)] [--version (print version, exit)] <file name>
<file name>+

💫 DESCRIPTION 💫

clm dist computes distances between clusterings. it can do the split/join distance (explained further down, bestie, we get there), the variance of information measure, and the Mirkin metric. by default it computes the chosen distance for all pairs of distances in the clusterings you hand it.

clusterings have to be in the mcl matrix format (cf. mcxio(5)), and you supply them on the command line as the names of the files in which they're stored. and if you already know they're nested? you can compare only consecutive clusterings with the --chain option. iconic behavior honestly ✨

heads up: currently, clm dist cannot compute different distance types simultaneously. one vibe per run, sorry 🎀

📝 the output format 📝

the output is linewise, each line giving info about the distance between a pair of clusterings. a line looks like this:

d  d1  d2  N  name1  name2

where:

  • d — the distance between the two clusterings
  • d1 — the distance from the first clustering to the greatest common subclustering (aka GCS, intersection, or meet) of the two clusterings
  • d2 — same deal, but the distance from the second clustering to the GCS
  • N — the number of nodes in the set over which the clusterings are defined
  • name1 and name2 — the names of the files the clusterings came from

✨ OPTIONS ✨

  • -mode <sj|vi|mk> (distance type) — use sj for the split/join distance (described below), vi for the variance of information measure, and mk for the Mirkin metric.
  • --chain (only compare consecutive clusterings) — use this when you know the clusterings are nested clusterings (or approximately so — "appoximately" is what the original says, we keep it 💀) and ordered from coarse to fine-grained or vice versa. a classic example: the set of clusterings you get from running mcl with a range of inflation parameters.
  • --one-to-many (compare first clustering to all others) — use this, for example, to compare a gold standard classification to a collection of clusterings. but bear in mind: sub-clustering and super-clustering are also ways for a clustering to be compatible with a gold standard. which means the simple numerical criterion of distance between clusters (by whatever method) is only partially informative. for the Mirkin, variation of information and split/join metrics it pays to take into account the constituent distances d1 and d2 (see above). assuming the first clustering given as argument represents a gold standard: a small value for d1 implies the second clustering is (nearly) a superclustering, and similarly a small value for d2 implies it's (nearly) a subclustering. 🦋
  • --sort (sort clusterings based on coarseness) — super useful alongside the --chain option, in case the list of clusterings you supplied isn't necessarily ordered by granularity.
  • --index (output Rand, adjusted Rand and Jaccard indices) — as described. 💅
  • -o fname (output file) — writes the output to fname.
  • -digits k (output decimals) — the number of decimals printed when using the variance of information measure.

🎀 SPLIT/JOIN DISTANCE 🎀

for each pair of clusterings C1, C2, two numbers get given, say d1 and d2. then d1 + d2 equals the number of nodes that have to be exchanged in order to transform any of the two clusterings into the other, and you can think of (d1+d2)/2N as the percentage that the two clusterings differ. the split/join distance has a linearity property with respect to the meet of C1 and C2, see below. ✨

the split/join distance sjd is very handy for computing the consistency of two or more clusterings of the same graph, or for comparing clusterings made with different resource (but otherwise identical) parameters. the latter is for finding out whether you can settle for cheaper mcl settings, or whether you need to switch to more expensive ones. the former is for finding out whether clusterings are identical, conflicting, or whether one is (almost) a subclustering of the other — mostly for comparing a set of clusterings of different granularity, made by letting the mcl parameter -I vary. the EXAMPLES section has examples of all these clm dist uses, and the use of clm info and clm meet is discussed there too. no cap 👑

sjd is a metric distance on the space of partitions of a set of a given fixed cardinality. it has the following linearity property (shared with the Variation of Information metric and the Mirkin distance). let P1 and P2 be partitions, then:

sjd(P1, P2) = sjd(P1, D) + sjd(P2, D)

where D (for Dutch Doorsnede) is the intersection of P1 and P2, i.e. the unique clustering that is both a subclustering of P1 and P2 and a superclustering of all other subclusterings of P1 and P2. sloppily worded: D is the largest subclustering of both P1 and P2. see the REFERENCES section for a pointer to the technical report in which sjd was first defined (and in which the non-trivial triangle inequality is proven). 📚

since it's useful to know whether one partition (or clustering) is almost a subclustering of the other, clm dist returns the two constituents sjd(P1,D) and sjd(P2,D). 🫶

let P1 and P2 be two clusterings of a graph of cardinality N, and suppose clm dist returns the integers d1 and d2. you can think of 100 * (d1 + d2) / N as the percentage that P1 and P2 differ. this interpretation is in fact slightly conservative. the numerator is the number of nodes that need to be exchanged in order to transform one into the other. this number may grow as large as 2*N - 2*sqrt(N), so it would be justified to take 50 as a scaling factor rather than 100. 👀

for example, if A and B are both clusterings of a graph on a set of 9058 nodes and clm dist returns [38, 2096], this conveys that A is almost a subclustering of B (by splitting 38 nodes in A we obtain a clustering D that is a subclustering of B), and that B is much less granular than A. the latter is because we can obtain B from D by joining 2096 nodes in some way. 💀✨

🌸 EXAMPLES 🌸

the following is an example of several mcl validation tools applied to a set of clusterings on a protein graph of 9058 nodes. in the first experiment, six different clusterings were generated for different values of the inflation parameter, which was respectively set to 1.2, 1.6, 2.0, 2.4, 2.8, and 3.2. it should be noted that protein graphs seem somewhat special in that an inflation parameter setting as low as 1.2 still produces a very acceptable clustering. the six clusterings are scrutinized using clm dist, clm info, and clm meet. in the second experiment, four different clusterings were generated with identical flow (i.e. inflation) parameter, but with different resource parameters. clm dist is used to choose a sufficient resource level. 🧚

high -P/-S/-R values make mcl more accurate but also more time and memory consuming. run mcl with different settings for these parameters, holding other parameters fixed. if the expensive and supposedly more accurate clusterings are very similar to the clusterings resulting from cheaper settings, the cheaper setting is sufficient. if the distances between cheaper clusterings and more expensive clusterings are large, this is an indication that you need the expensive settings. in that case, you may want to increase the -P/-S/-R parameters (or simply the -scheme parameter) until associated clusterings at nearby resource levels are very similar. 🔥

in this particular example, the validation tools do not reveal that one clustering in particular can be chosen as 'best', because all clusterings seem at least acceptable. they do aid however in showing the relative merits of each clusterings. the most important issue in this respect is cluster granularity. the table below shows the output of clm info.

     Efficiency  Mass frac  Area frac  Cl weight  Mx link weight
1.2   0.42364     0.98690    0.02616    52.06002    50.82800
1.6   0.58297     0.95441    0.01353    55.40282    50.82800
2.0   0.63279     0.92386    0.01171    58.09409    50.82800
2.4   0.65532     0.90702    0.01091    59.58283    50.82800
2.8   0.66854     0.84954    0.00940    63.19183    50.82800
3.2   0.67674     0.82275    0.00845    66.10831    50.82800

this data shows that there is exceptionally strong cluster structure present in the input graph. the 1.2 clustering captures almost all edge mass using only 2.5 percent of 'area'. the 3.2 clustering still captures 82 percent of the mass using less than 1 percent of area. we continue with looking at the mutual consistency of the six clusterings. below is a table that shows all pairwise distances between the clusterings. 💅

    |   1.6  |   2.0  |   2.4  |   2.8  |   3.2  |   3.6
-----------------------------------------------------------.
1.2 |2096,38 |2728,41 |3045,48 |3404,45 |3621,43 |3800, 42 |
-----------------------------------------------------------|
1.6 |        | 797,72 |1204,76 |1638,78 |1919,70 |2167, 69 |
-----------------------------------------------------------|
2.0 |        |        | 477,68 | 936,78 |1235,85 |1504, 88 |
-----------------------------------------------------------|
2.4 |        |        |        | 498,64 | 836,91 |1124,103 |
-----------------------------------------------------------|
2.8 |        |        |        |        | 384,95 | 688,119 |
-----------------------------------------------------------|
3.2 |        |        |        |        |        | 350,110 |
-----------------------------------------------------------.

the table shows that the different clusterings are pretty consistent with each other, because for two different clusterings it is generally true that one is almost a subclustering of the other. the interpretation for the distance between the 1.6 and the 3.2 clustering for example, is that by rearranging 43 nodes in the 3.2 clustering, we obtain a subclustering of the 1.6 clustering. the table shows that for any pair of clusterings, at most 119 entries need to be rearranged in order to make one a subclustering of the other. 🌈

the overall consistency becomes all the more clear by looking at the meet of all the clusterings: 👑

...and that's where part 1 leaves us, bestie — part 2 is right there waiting 💖

okay bestie, so for this bit you literally run these two lines:

      clm meet -o meet out12 out16 out20 out24 out28 out32
      clm dist meet out12 out16 out20 out24 out28 out32

and that gives you the distances between the respective clusterings and their meet. like, look:

          |   1.2  |    1.6 |  2.0   |   2.4  |  2.8   |  3.2    |
      -------------- --------------------------------------------.
      meet|  0,3663|  0,1972| 0,1321 |  0,958 | 0,559  | 0,283   |
      -------------- --------------------------------------------.

so this shows that by rearranging only 283 nodes in the 3.2 clustering, one obtains a subclustering of all other clusterings. slay.

then in the last experiment, mcl was run with inflation parameter 1.4, for each of the four different preset pruning schemes k=1,2,3,4. the clm dist distances between the different clusterings are shown below:

          |  k=2   |   k=3  |   k=4  |
      -------------------------------.
      k=1 |  17,17 |  16,16 |  16,16 |
      -------------------------------.
      k=2 |        |   3,3  |   5,5  |
      -------------------------------.
      k=3 |        |        |   4,4  |
      -------------------------------.

this example is a little boring in that the cheapest scheme seems adequate. if anything, the gaps between the k=1 scheme and the rest are a little larger than the three gaps between the k=2, the k=3, and the k=4 clusterings. had all distances been much larger, then such an observation would be reason to choose the k=2 setting.

it is not an issue if clusterings still change even at high resource levels. in all likelihood, there are anyway nodes which are not in any core of attraction, and that are on the boundary between two or more clusters. they may go one way or another, and these are the nodes which will go different ways even at high resource levels. such nodes may be stable in clusterings obtained for lower inflation values (i.e. coarser clusterings), in which the different clusters to which they are attracted are merged.

👑 AUTHOR 👑

Stijn van Dongen. 💖

🦋 SEE ALSO 🦋

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

💖 REFERENCES 💖

and that's the whole vibe, bestie — this page is clm dist 22-282, dated 9 Oct 2022, from clm dist(1). periodt 💅✨

📦 where this page comes from