graphMC: A package for testing the independence of graphs

J. Ray, A. Pinar and C. Safta

Contact: J. Ray, j-a-i-r-a-y [at] sandia [dot] gov

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.

The page has two sections : Publications and Releases .

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:

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.

In order to download and compile the release, do

[jaray ]% unzip filename.zip

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 software release here

The reference manual can be downloaded here .

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

Publications

  1. Jaideep Ray, Ali Pinar and C. Seshadhri, "Are we there yet? When to stop a Markov chain while generating random graphs", 9th Workshop on Algorithms and Models for the Web Graph, Halifax, Nova Scotia, Canada, June 22-23, 2012. Also, in 9th International Workshop for Algorithms and Models for the Web Graph, A. Bonato and J. Janssen, eds, Lecture Notes in Computer Science (LNCS 7323), 2012. Download paper SAND2012-1169C here.

  2. J. Ray, A. Pinar and C. Seshadhri, "A stopping criterion for Markov chains when generating independent graphs", SAND2012-9390P, arXiv:1210.8184[cs.SI]. Download here.