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
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.
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.
- 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.
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.
Download software release here
The reference manual can be downloaded
The theory is described in a paper submitted for publication. Download
the paper arXiv:1210,8184 [cs.SI] here.
- 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
- 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.