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

Description

The algorithm we implemented here generates random simple connected graphs with prescribed degree sequence.
This algorithm is described in the article: 'Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence', in proc. of the 11th Conference of Computing & Combinatoric (COCOON 2005), LNCS 3595, pp 440-449. You may download a preprint here: Efficient and simple generation of random simple connected graphs with prescribed degree sequence
Note that a full version, containing approximately twice as much material, is currently submitted to an international journal.

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

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