markov-clustering

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

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