A program generating homogenous random graphs with given weights

L  Bogacz; Z  Burda; W  Janke; B  Waclaw

doi:10.1016/j.cpc.2005.07.010

A program generating homogenous random graphs with given weights

L Bogacz, Z Burda, W Janke, B Waclaw

School of Physics and Astronomy

Research output: Contribution to journal › Article › peer-review

Abstract / Description of output

We present a program package to generate homogeneous random graphs with probabilities prescribed by the user. The statistical weight of a labeled graph alpha is given in the form W(alpha) = PI(i=1)(N)p(qi), where p(q) is an arbitrary user function and qi are the degrees of the graph nodes. The program can be used to generate two types of graphs (simple graphs and pseudo-graphs) from three types of ensembles (micro-canonical, canonical and grand-canonical).

Program summary

Title of the program:GraphGen

Catalogue identifier:ADWL

Program summary URL: http://cpc.cs.qub.ac.uk/summaries/ADWL

Program obtainable from:CPC Program Library, Queen's University of Belfast, N. Ireland

Computer for which the program is designed and others on which it has been tested: PC, Alpha workstation

Operating systems or monitors under which the program has been tested:Linux, Unix, MS Windows XP

Programing language used:C

Memory required to execute with typical data:300 k words for a graph with 1000 nodes and up to 50 000 links

No. of bits in a word:32

No. of processor used:1

Has the code been vectorized or parallelized:No

No. of lines in distributed program, including test data, etc.:2253

No. of bytes in distributed program, including test data, etc.:14 330

Distribution format:tar.gz

Keywords:Random graphs, complex networks, Markov process, Monte Carlo method

Nature of the 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

Method of solution:The starting graph is taken arbitrary 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

Restrictions on the complexity of the problem:None

Typical running time:Less than two minutes to generate 10(5) graphs of size 10 000 nodes and 30 000 links on a typical PC

Original language	English
Pages (from-to)	162-174
Number of pages	13
Journal	Computer Physics Communications
Volume	173
Issue number	3
DOIs	https://doi.org/10.1016/j.cpc.2005.07.010
Publication status	Published - 15 Dec 2005

Keywords / Materials (for Non-textual outputs)

random graphs
complex networks
Markov process
Monte Carlo method
STATISTICAL-MECHANICS
COMPLEX NETWORKS
EVOLUTION

Access to Document

10.1016/j.cpc.2005.07.010

Cite this

@article{7fc2b7c5c45f452291204cc4f5021082,

title = "A program generating homogenous random graphs with given weights",

abstract = "We present a program package to generate homogeneous random graphs with probabilities prescribed by the user. The statistical weight of a labeled graph alpha is given in the form W(alpha) = PI(i=1)(N)p(qi), where p(q) is an arbitrary user function and qi are the degrees of the graph nodes. The program can be used to generate two types of graphs (simple graphs and pseudo-graphs) from three types of ensembles (micro-canonical, canonical and grand-canonical).Program summaryTitle of the program:GraphGenCatalogue identifier:ADWLProgram summary URL: http://cpc.cs.qub.ac.uk/summaries/ADWLProgram obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandComputer for which the program is designed and others on which it has been tested: PC, Alpha workstationOperating systems or monitors under which the program has been tested:Linux, Unix, MS Windows XPPrograming language used:CMemory required to execute with typical data:300 k words for a graph with 1000 nodes and up to 50 000 linksNo. of bits in a word:32No. of processor used:1Has the code been vectorized or parallelized:NoNo. of lines in distributed program, including test data, etc.:2253No. of bytes in distributed program, including test data, etc.:14 330Distribution format:tar.gzKeywords:Random graphs, complex networks, Markov process, Monte Carlo methodNature of the problem:The program generates random graphs. The probabilities of graph occurrence are proportional to their statistical weight, dependent on node degrees defined by arbitrary distributionsMethod of solution:The starting graph is taken arbitrary 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 graphsRestrictions on the complexity of the problem:NoneTypical running time:Less than two minutes to generate 10(5) graphs of size 10 000 nodes and 30 000 links on a typical PCUnusual features of the program:None. (C) 2005 Elsevier B.V. All rights reserved.",

keywords = "random graphs, complex networks, Markov process, Monte Carlo method, STATISTICAL-MECHANICS, COMPLEX NETWORKS, EVOLUTION",

author = "L Bogacz and Z Burda and W Janke and B Waclaw",

year = "2005",

month = dec,

day = "15",

doi = "10.1016/j.cpc.2005.07.010",

language = "English",

volume = "173",

pages = "162--174",

journal = "Computer Physics Communications",

issn = "0010-4655",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - A program generating homogenous random graphs with given weights

AU - Bogacz, L

AU - Burda, Z

AU - Janke, W

AU - Waclaw, B

PY - 2005/12/15

Y1 - 2005/12/15

N2 - We present a program package to generate homogeneous random graphs with probabilities prescribed by the user. The statistical weight of a labeled graph alpha is given in the form W(alpha) = PI(i=1)(N)p(qi), where p(q) is an arbitrary user function and qi are the degrees of the graph nodes. The program can be used to generate two types of graphs (simple graphs and pseudo-graphs) from three types of ensembles (micro-canonical, canonical and grand-canonical).Program summaryTitle of the program:GraphGenCatalogue identifier:ADWLProgram summary URL: http://cpc.cs.qub.ac.uk/summaries/ADWLProgram obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandComputer for which the program is designed and others on which it has been tested: PC, Alpha workstationOperating systems or monitors under which the program has been tested:Linux, Unix, MS Windows XPPrograming language used:CMemory required to execute with typical data:300 k words for a graph with 1000 nodes and up to 50 000 linksNo. of bits in a word:32No. of processor used:1Has the code been vectorized or parallelized:NoNo. of lines in distributed program, including test data, etc.:2253No. of bytes in distributed program, including test data, etc.:14 330Distribution format:tar.gzKeywords:Random graphs, complex networks, Markov process, Monte Carlo methodNature of the problem:The program generates random graphs. The probabilities of graph occurrence are proportional to their statistical weight, dependent on node degrees defined by arbitrary distributionsMethod of solution:The starting graph is taken arbitrary 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 graphsRestrictions on the complexity of the problem:NoneTypical running time:Less than two minutes to generate 10(5) graphs of size 10 000 nodes and 30 000 links on a typical PCUnusual features of the program:None. (C) 2005 Elsevier B.V. All rights reserved.

AB - We present a program package to generate homogeneous random graphs with probabilities prescribed by the user. The statistical weight of a labeled graph alpha is given in the form W(alpha) = PI(i=1)(N)p(qi), where p(q) is an arbitrary user function and qi are the degrees of the graph nodes. The program can be used to generate two types of graphs (simple graphs and pseudo-graphs) from three types of ensembles (micro-canonical, canonical and grand-canonical).Program summaryTitle of the program:GraphGenCatalogue identifier:ADWLProgram summary URL: http://cpc.cs.qub.ac.uk/summaries/ADWLProgram obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandComputer for which the program is designed and others on which it has been tested: PC, Alpha workstationOperating systems or monitors under which the program has been tested:Linux, Unix, MS Windows XPPrograming language used:CMemory required to execute with typical data:300 k words for a graph with 1000 nodes and up to 50 000 linksNo. of bits in a word:32No. of processor used:1Has the code been vectorized or parallelized:NoNo. of lines in distributed program, including test data, etc.:2253No. of bytes in distributed program, including test data, etc.:14 330Distribution format:tar.gzKeywords:Random graphs, complex networks, Markov process, Monte Carlo methodNature of the problem:The program generates random graphs. The probabilities of graph occurrence are proportional to their statistical weight, dependent on node degrees defined by arbitrary distributionsMethod of solution:The starting graph is taken arbitrary 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 graphsRestrictions on the complexity of the problem:NoneTypical running time:Less than two minutes to generate 10(5) graphs of size 10 000 nodes and 30 000 links on a typical PCUnusual features of the program:None. (C) 2005 Elsevier B.V. All rights reserved.

KW - random graphs

KW - complex networks

KW - Markov process

KW - Monte Carlo method

KW - STATISTICAL-MECHANICS

KW - COMPLEX NETWORKS

KW - EVOLUTION

U2 - 10.1016/j.cpc.2005.07.010

DO - 10.1016/j.cpc.2005.07.010

M3 - Article

SN - 0010-4655

VL - 173

SP - 162

EP - 174

JO - Computer Physics Communications

JF - Computer Physics Communications

IS - 3

ER -

A program generating homogenous random graphs with given weights

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this