GraphGen: Monte Carlo Equilibrated Graph Generation Template Library

1

Introduction

This template library provides classes and functions to sample from equilibrated graph ensembles and growing graph ensembles. The statistical ensemble can be defined by global restrictions to the graphs contained, such as to forbid graphs with multiple links or non tree graphs. For introduction on usage, see the usage section or the example programs minimal.cpp and example.cpp.

Installation and Compilation

Download and unpack the graphgen tarball to a directory convenient for include files. You then need to specify the include path and - as I do not know better - the object files to link with your program. Suggest you have a graphgen directory directly in your program source directory, then this would look like

  g++ -I graphgen graphgen/graph.o graphgen/estimate.o -o program program.cpp

using the GNU C++ compiler. A Makefile is provided to compile example programs and library object files.

Documentation Usage

The documentation currently mostly focuses on specific interface documentation without covering much of the bigger picture issues. So to get a hint how things are organized and meant to be used, see the minimal.cpp and example.cpp programs. The latter tries to cover most of the parts of package, but only aspects.

Usage

The usage boils down to instiating an ensemble object with appropriate template parameters. Currently there are three ensemble classes representing statistical graph ensembles with different global properties, named in analogy to the thermodynamical ensembles:

The biggest graph set available contains graphs with fixed number of vertices but variable number of links, it is named the grandcanonical. A subset, canonical, contains graphs with fixed numbers of vertices and links. Another subset also has constant numbers of vertices and links and also fixes the degree sequence (i.e. which degrees must be present how often in a graph).

Through template parameters the ensemble classes are further specialized. The first template parameter is the type to be used as weight calculation class. The second parameter is used for restricting the updates proposed for Metropolis sampling. For example

  link_weight<value_type::logweight> weight(f);
  undirected_graph graph(1000,2000);
  canonical<link_weight<logweight>, shape::simple> E(graph,weight);
  E.update();

creates graph, weight and an ensemble object restricted to simple graphs, using a logarithmic per-link degree weight to calculate acceptance probabilities. The graph is initialized with 1000 sites and 200 links, the weight with some function f to compute values and the ensemble ties it all together. Finally a local graph update is done.

Calculation of quantities can be done in two ways - create and manage histograms yourself and use function calls to accumulate data to them. Provided functions include estimation of degree distributions, distance distributions, clustering, degree-degree correlations, average neighbor degrees, assortativity. Another way are classes encapsulating the accumulating functions, managing histograms, normalization and output.

Sampling of growing graph ensembles is also possible using graph generator functions. Currently these are integrated into the central graph class but should be supplemented by generator classes outside.

Other Things

If you actually use this kit, probably you have suggestions or found problems, maybe you don't. However we would appreciate feedback. There are certainly things to be enhanced, but when there is time to do them, I will probably do them without impact on compatibility.