Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[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.

Solution method:
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.

Running time:
Less than two minutes to generate 105 graphs of size 10000 nodes and 30000 links on a typical PC.