Edinburgh Research Explorer

A program generating homogenous random graphs with given weights

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Original languageEnglish
Pages (from-to)162-174
Number of pages13
JournalComputer Physics Communications
Volume173
Issue number3
DOIs
Publication statusPublished - 15 Dec 2005

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

Unusual features of the program:None. (C) 2005 Elsevier B.V. All rights reserved.

    Research areas

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

ID: 1217676