Institute of Theoretical Informatics, Algorithmics

A Generator for Dynamic Clustered Random Graphs

This page offers supplementary information on our random generator for graphs which are both dynamic and have an implanted clustering. Two versions of this generator exist, a full description of the original version including data structures, usage and background can be found in our technical report.

As this implementation suffers from a space complexity in O(n^2), Roland Kluge reimplemented the generator in his bachelor thesis optimizing the data structures used. The qualitative behaviour of the generator is the same as in the old version, but the syntax in which the input parameters are expected differs slightly. For details, see the report on his thesis. As the new implementation is both faster and more space efficient than the original version, we strongly recommend to use it instead of the old implementation, although the latter is still available for download.

Download

Downloading and using both versions of our generator is free.

New Version

The current implementation of the generator can be downloaded using this link. The program can be called from the command line by either using the jar-File (java -jar dcrgenerator.jar) or by calling the shell script ldcrgen.sh. If only the parameter -h is given, the program will print a list of available parameters and examples. For more details, we refer to the bachelor thesis of Roland Kluge.

Old Version

Please use this link to obtain the command-line version of the generator in this jar-file: dcrgenerator.jar

Using the generator is thus done by calling java -jar dcrgenerator.jar . Although all command-line parameters are supplied with reasonable default values, you will have to look them up in our documentation if you intend to use the generator. This document is also listed in the electronic archive of KIT: technical report.


We are currently negotiating under which license the source code will be published, which will be decided soon.

The version of our generator which is to be included in visone will be available as soon as visone fully incorporates dynamics in a future release. Unfortunately we cannot tell when the developers of visone will have such a release ready.

Change-Log

  • (09.07.24) Parameter beta (β) is now also used for dynamic node insertions, in order to continuously work towards the inital biased cluster size distribution.

Todo-List

  • To speed up conformity with the expected biased distribution after some cluster event, new clusters should be inserted into the array of existing clusters by size.