+==================================+
| Random Graph Generation Software |
+==================================+
This source code is (c) Copyright 2001 by Christopher R. Palmer
and J. Gregory Steffan. It may be freely redistributed and
included in other packages provided this copyright notice is
included.
Version 1.0
January 12, 2001 - Initial public release
=============================================================================
Using the 'PLODD' generator:
====================
This file is the entire distribution. Compile it with your favorite
C compiler and you can then run the program as follows:
plodd
where n is the number of nodes in the graph, and alpha and beta are as
defined in the paper (cited below). Example values are
alpha=0.811392, beta=n
Our experience is that beta should be in the neighbourhood of .
Note that the authors did not do an extensive study on the impact of
different values of alpha and beta. You likely want to choose them to
produce a desired slope for your log-log plots.
For more information please see the paper that describes this
graph generation algorithm. A citation appears at the end of
this document.
Output format:
==============
The output is an n x n adjacency matrix where a '1' indicates the
existence of an edge, and a '0' indicates the absence of an edge.
=============================================================================
Using the 'Recursive' generator:
====================
This file is the entire distribution. Compile it with your favorite
C compiler and you can then run the program as follows:
./gen [-pgm fname | -pgm2 fname] logn m alpha beta gamma epsilon
which will then randomly generate a graph with 2**logn nodes.
There will be exactly m distinct edges in the graph (each edge
is weighted). The recursive probability parameters are
alpha + beta + gamma + epsilon = 1
For more information please see the paper that describes this
graph generation algorithm. A citation appears at the end of
this document.
The two optional arguments
-pgm fname
-pgm2 fname
will create the named file in pgm format. Using the first option
will visualize the probabilities for the adjacency matrix (darker
is less probable) and the second form will visualize the actual
adjacency matrix created (darker is fewer links). These options
are mostly useful for debugging.
Output format:
==============
The output format is a simple ascii representation of the graph.
The first line contains a single integer that is the number of
nodes in the graph (2**logn). Each subsequent line contains three
integers:
u v w
which represents an edge from node u to node v with weight w.
=============================================================================
More Information / Etc:
=======================
The paper that describes this work is:
Christopher R. Palmer and J. Gregory Steffan, Generating
Network Topologies that Obey Power Laws, IEEE Globecom 2000,
San Francisco, CA, November 2000.
http://www.cs.cmu.edu/~crpalmer/pubs.html/globecom2000.ps
please cite it when referring to this graph generation software.
Further information, bug reports, etc. may be sent to:
steffan@eecg.toronto.edu
crpalmer@cs.cmu.edu