Graph generation software : Efficient and simple generation of random simple connected graphs with prescribed degree sequence

Graph generation software

Description

The algorithm we implemented here generates random simple connected graphs with prescribed degree sequence.
This algorithm is described in the paper Efficient and simple generation of random simple connected graphs with prescribed degree sequence, by Fabien Viger and Matthieu Latapy.
The implementation was written by Fabien Viger.

Disclaimer

The software provided here is for demonstration purposes. Use it at your own risk. However, we did not encounter any trouble on Linux (32-bit and 64-bit configurations), Cygwin, Windows 98 SE or Windows XP, so it should work fine for most configurations.

Download

Sources (compilables with g++): tar.gz(50Kb), rar(39Kb), zip(59Kb).
Windows executables (in command prompt environment): .zip(140Kb), .rar(80Kb).

Documentation and Bibliography

The algorithm is fully described in the paper cited above. For a brief desciption of the software, see the README file.
For more information about the uniform random generation of graphs with prescribed degree sequence, see the following papers:

Stauffer, Barbosa: A study of the edge-switching markov-chain method for the generation of random graphs (2006)
Aiello, Chung and Lu, A Random Model for Massive Graphs (2001)
Gkantsidis, Mihail and Zegura, The Markov Chain Simulation Method for Generating Connected Power-Law Random Graphs (2003)
Milo, Kashtan, Itzkovitz, Newman and Alon, On the uniform generation of random graphs with prescribed degree sequences (2001)

Copyright

This software is published under the GNU General Public License .

Back to home page