Markov Chain Monte-Carlo
Last updated 2 years ago by wfunkenbusch .
MIT · Repository · Bugs · Original npm · Tarball · package.json
$ cnpm install wfunkenbusch-markov-chain-monte-carlo 
SYNC missed versions from official npm registry.

Coverage Status


Performs a Markov Chain Monte-Carlo simulation on a set of nodes to determine the best graphs for a particular weight function.

The relative probability of accepting a graph, $j$, from a graph $i$ is given by

$$f({X_i},{X_j}) = e^{-(\Theta(X_j) - \Theta(X_i))/T}$$


$$\Theta(X_i) = r \sum_e w_e + \sum_k^M \sum_{e \in p_{0k}} w_e$$

where $e$ is an edge, $w_e$ is the weight of an edge (the distance between the two nodes it connects), $k$ is a node, $M$ is the total number of nodes, and $p_{0k}$ is the shortest path length between the source node (index 0) and node $k$. r is a constant which determines the importance of total edge weight versus shortest path length. A larger r value gives more importance to total graph edge weight. T represents the ease of accepting the proposal distribution. A larger T makes it easier to accept the proposal distribution.


  • Run using Javascript, node.js (v8 or above)
  • Needs the following modules installed: jsnetworkx, lodash-clonedeep, command-line-args, mocha (for testing), assert (for testing), istanbul (for coverage), and coveralls mocha-lcov-reporter (for coverage)
  1. npm install wfunkenbusch-markov-chain-monte-carlo
  2. Create a .js file which calls the main function and sets inputs
  3. node file name.js


  1. git clone
  2. Enter repository
  3. node ./lib/index.js/ --nodes nodes --T T --r r --N N

Ex. .js file

const mcmc = require('wfunkenbusch-markov-chain-monte-carlo') var options = {}; options.nodes = '0, 0, 1, 1, 1, -1, -1, 1'; options.T = 1; options.r = 1; options.N = 100; mcmc.main(options);


  • nodes

    • type: string
    • Node coordinates given as comma separated values in a string. The format is 'x1, y1, x2, y2, x3, y3, ..., xM, yM', where xi is the x coordinate of node i, and yi is the y coordinate of node i.
  • T

    • type: float
    • Scaling factor for the ease of acceptance of a new proposal distribution. A larger T makes it easier to accept a proposal distribution. Must be positive.
  • r

    • type: float
    • Scaling factor for the relative importance of total edge weight versus shortest path length. A larger r gives more importance to total edge weight.
  • N

    • type: integer
    • Total number of times to run the Markov Chain Monte-Carlo simulation. As the number of nodes increase, this value should also increase. The value should be large enough that the effect of the initial distribution is small.


All outputs are printed to the console.

  • Current iteration number, for keeping track of code progress. To suppress, comment out console.log(i + 1) in main(). To reduce the number of outputs, console.log(i + 1) may be replaced with:

if ((i + 1) % n === 0) { console.log(i + 1) }

where n is the fraction of outputs to print.

  • The top 1% of adjacency matrices, followed by the number of times they appeared. Prioritizes graphs which appeared earlier. To change the percentage of top graphs printed, replace the line

var nBestGraphs = Math.floor(Fun.AList.length / 100 + 1);


var nBestGraphs = Math.floor(Fun.AList.length * (fraction to print) + 1);

  • The expected number of edges connected to the source node.
  • The expected number of edges in the graph.
  • The expected value of the maximum shortest path from the source node to all other nodes.

Note: the total number of adjacency matrices is N + 1.

Current Tags

  • 0.0.2                                ...           latest (2 years ago)

3 Versions

  • 0.0.2                                ...           2 years ago
  • 0.0.1                                ...           2 years ago
  • 0.0.0                                ...           2 years ago
Maintainers (1)
Today 0
This Week 0
This Month 0
Last Day 0
Last Week 0
Last Month 0
Dependencies (6)
Dev Dependencies (12)
Dependents (0)

Copyright 2014 - 2016 © |