README.md

What is this?

This is a simple Markov graph cluster algorithm implementation. For more information about the algorithm, see http://micans.org/mcl/.

Installation

npm install markov-clustering

Usage

The main entry point is the cluster function. It takes two arguments, an adjacency matrix graph representation and an optional options parameter.

Here's an example options object with default values:

const options = {
  expandFactor: 2,
  inflateFactor: 2,
  maxLoops: 10,
  multFactor: 1
}

Example

The undirected graph below is used in this example.

Create an adjacency matrix representation of your graph, this will be the input for the clustering algorithm.

Here's the adjacency matrix for the graph above:

[[0, 1, 1, 0, 0, 0],
 [1, 0, 1, 0, 0, 0],
 [1, 1, 0, 1, 0, 0],
 [0, 0, 1, 0, 1, 1],
 [0, 0, 0, 1, 0, 1],
 [0, 0, 0, 1, 1, 0]]

The following snippet clusters the adjacency matrix:

const mc = require('markov-clustering');
const math = require('mathjs');

const A = math.matrix([[0, 1, 1, 0, 0, 0],
                       [1, 0, 1, 0, 0, 0],
                       [1, 1, 0, 1, 0, 0],
                       [0, 0, 1, 0, 1, 1],
                       [0, 0, 0, 1, 0, 1],
                       [0, 0, 0, 1, 1, 0]]);
console.log(mc.cluster(A));

$ node snippet.js
[ [ 0, 1, 2 ], [ 3, 4, 5 ] ]

Tests

Some basic tests are included:

npm run test

Performance

The computational complexity is not encouraging, the graph below shows execution time for different number of nodes with a fitted third order polynomial. By the way I did not see a significant difference when the graphs were very sparse and represented with sparse mathjs matrices, I didn't look into why, it is not likely that improving the representation would make enough difference for my intended application.

Dependencies

The implementation relies on http://mathjs.org/ for matrix implementation.

Credits

The implementation is largely based on Python MCL https://github.com/koteth/python_mcl.

License

MIT