graphMC: A package for testing the independence of graphs

J. Ray, A. Pinar and C. Safta

This page is the download page for graphMC, a package that allows one to test the independence of graphs. The graphs are generated by a Markov chain procedure driving a scheme to rewire graphs in a particular manner e.g., to preserve the degree- or the joint-degree distribution. The rewiring scheme creates new graph realizations, but successive realizations are correlated. This package helps one to identify how may steps the Markov chain has to run before the graphs can be considered independent (or the Markov chain has "forgotten" its initial condition or it has fully mixed.

Acknowledgements

This work was funded by the Applied Mathematics program of the United States Department of Energy, Office of Science. Sandia National Laboratories is a multiprogram laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the United States Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000.

We also acknowledge the FORTRAN package gibbsit by Raftery and Lewis, which was used as a model for the C++ implementations of the tests of independence. The package was obtained from StatLib.

License

Copyright 2013, Sandia Corporation. Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government retains certain rights in this software.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  • Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
  • Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
  • Neither the name of the Sandia Corporation nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Releases

Releases are available as a zip file. The software package is distributed under a BSD license. The release comes with examples and a reference manual. Compilation and installation instructions are in a README file. The library is best used with C++ codes, but can be interfaced with C and Fortran.

Step into the new directory created and read the README.txt file. Read the BSD license info in LICENSE.txt if you plan to distribute this software as part of a larger package. Also, read it if you plan to use this in a commercial setting.

Release 1.0

Download the software release.

Download the reference manual.

The theory is described in a paper submitted for publication. Download the paper arXiv:1210,8184 [cs.SI] here.

Publications