This is a fast implementation of the scale-free network model described by Krapivsky, Rodgers, and Redner in Degree Distributions of Growing Networks [fn:1].

The complexity of the simulation is O(n * log n), where n is the number of nodes in the simulated network. 10**6 nodes can be simulated in about 5 seconds on a modern laptop.

If using unix/linux/osx, simply type ‘make’ in this directory.

If using windows, download and install cygwin (http://www.cygwin.com), then type ‘make’ in this directory within the cygwin terminal.

After compilation the ‘krapivsky’ binary will be available in this directory.

Usage: krapivsky [options] nnodes

nnodes: number of nodes to simulate

options:

• –p: model parameter p, the probability of taking a node step. (default: p=0.5)
• –lambda: model parameter lambda, the in-degree fitness of nodes. (default: lambda=0.2)
• –mu: model parameter mu, the out-degree fitness of nodes. (default: mu=0.2)
• –nsamples: number of out-degree,in-degree samples to take. (default: nsamples=100)
• –samplefile: filename for sample out-degree,in-degree output. (default: samplefile=”samples.csv”)
• –allfile: filename for all out-degree,in-degree pairs. (default: allfile=”allsamples.csv”)
• –nodefile: filename for nodes. (default: nodefile=”nodes.csv”)
• –edgefile: filename for edges. (default: edgefile=”edges.csv”
• –variable-fitness: if this flag is present, sample mu and lambda from a standard lognormal with means defined by the mu and lambda parameters.

./generate-sample-plot.sh tag p lambda mu target_n_nodes n_samples

Simulate a model with target_n_nodes nodes, then produce diagnostic plots.

• tag : string identifier for this simulation’s results
• p : probability of a node-creation step
• lambda : in-degree probability offset
• mu : out-degree probability offset
• target_n_nodes : number of nodes in the simulated network
• n_samples : number of nodes to sample from the simulated network

Executing this script creates the directory results/tag_p_lambda_mu_target_n_nodes/. Within this directory, one will find

• command.txt : the ‘krapivsky’ command used to generate these results
• sample.csv : sampled nodes (format: out-degree,in-degree)
• all.csv : all nodes (same format as sample.csv)
• log-ccdf_…_.png : log-log plot of the degree ccdfs with comparisons to predicted values.

A C compiler with the standard libraries.

A C compiler with the standard libraries.

Python 2.7X with the numpy, matplotlib, and statsmodels libraries.

[fn:1] http://arxiv.org/abs/cond-mat/0012181