Programs in Physics & Physical Chemistry
|
|
Programs in Physics & Physical Chemistry |
|
| PROGRAM SUMMARY | ||
|---|---|---|
| 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 | ||
| 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. |
| Disclaimer | ScienceDirect | ElsevierPhysics | CPC | QUB |