Programs in Physics & Physical Chemistry
|[Licence| Download | New Version Template] adwl_v1_0.tar.gz(13 Kbytes)|
|Manuscript Title: A program generating homogeneous random graphs with given weights|
|Authors: L. Bogacz, Z. Burda, W. Janke, B. Waclaw|
|Program title: GraphGen|
|Catalogue identifier: ADWL_v1_0|
Distribution format: tar.gz
|Journal reference: Comput. Phys. Commun. 173(2005)162|
|Programming language: C.|
|Computer: PC, Alpha workstation.|
|Operating system: Linux, Unix, MS Windows XP.|
|RAM: 300k words for a graph with 1000 nodes and up to 50000 links.|
|Word size: 32|
|Keywords: random graphs, complex networks, Markov process, Monte Carlo method.|
|PACS: 89.65.-s, 89.75.Fb, 89.75.Hc.|
|Classification: 6.3, 4.13, 23.|
Nature of problem:
The program generates random graphs. The probabilities of graph occurrence are proportional to their statistical weight, dependent on node degrees defined by arbitrary distributions.
The starting graph is taken arbitrarily and then a sequence of graphs is generated. Each graph is obtained from the previous one by means of a simple modification. The probability of accepting or rejecting the new graph results from a detailed balance condition realized as Metropolis algorithm. When the length of the generated Markov chain increases, the probabilities of graph occurrence approach the stationary distribution given by the user-defined weights ascribed to the graphs.
Less than two minutes to generate 105 graphs of size 10000 nodes and 30000 links on a typical PC.
|Disclaimer | ScienceDirect | CPC Journal | CPC | QUB|