Computer Physics Communications Program LibraryPrograms 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_0Distribution 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 10 ^{5} graphs of size 10000 nodes and 30000 links on a typical PC. |

Disclaimer | ScienceDirect | CPC Journal | CPC | QUB |