mcmc

markov chain monte carlo

Introduction

This project is an implementation of Metropolis-Hastings algorithm to find the most probable graphs based on user input. User can specify the number of nodes, the coordination of the nodes, the source node, r, t factors and the number of iterations. The relative probability of the graphs are given by the following function:

where,

In this equation, the first sum is the total weight of the graph (weight of an edge is the distance between the two nodes). The second sum is the total weight of source node to other nodes.

The proposal distribution is defined such that in case of adding an edge:

where the M is the number of nodes and the M term is the maximum number of edges. E is the number of edges in current state.

In case of deleting an edge:

where B is the number of bridge. Bridge is an edge which will make the graph disconnected if being deleted.

The acceptance rate is defined as following:

Installation

$ git clone https://github.com/tttianhao/mcmc.git
$ npm install --save mcmc

Usage

$ node lib/index.js

Arguments

• --t: the T factor in relative probability equation. Default is 100
• --r: the r facotr in theta equation. Default is 1
• --number: the number of nodes. Default is 4
• --coordinate: the coordinate of nodes. Input format: x_1,y_1,x_2,y_2,x_3,y_3.... Default is 0,0,1,1,-1,1,1,-1
• --iterate: the number of iterations. Default is 1000
• --center: the source node. Default is node 0

License

MIT © Tianhao Yu