A program generating homogenous random graphs with given weights

doi:10.1016/j.cpc.2005.07.010

A program generating homogenous random graphs with given weights

2005-12-01

5

OA

AI

DOI：10.1016/j.cpc.2005.07.010

原文链接

查看原文

摘要

En 中文

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.

Keyword:

random graphs

complex networks

Markov process

Monte Carlo method

A program generating homogenous random graphs with given weights

摘要

AI总结

期刊

机构

引用论文