Quicknet: Scalable Network Generator

quicknet generates scale-free networks via preferential attachment (PA) models. It is very fast; generating a network with n nodes is O(n log n), and networks with many millions of nodes can be generated in a few seconds on commodity hardware.

Components

quicknet/

Use quicknet/ to generate networks from PA models. There are a few example models already implemented (see price.c, pricerecip.c, krapivsky.c). See Extending quicknet for a description of how to implement your own models.

research/

This directory contains the implementation for the paper “Efficient Network Generation under General Preferential Attachment” [1]. This codebase made use of a lot of indirection to enable different central data structures; it is quite a bit more difficult to work with than quicknet/. It is available for reference purposes.

quicknet/

Implemented Models

• Price’s model

• Price’s model with reciprocation
  • Krapivsky’s model
• Krapivsky’s model with reciprocation
• Krapivsky’s model with strongly connected component analysis

Compiling quicknet

cd quicknet
make

This will produce several executables.

Running quicknet

./price

or

./krapivsky

or, run one of the other binaries.

Command-line options

• -n: number of nodes to simulate
• -p: probability of taking a node step (krapivsky only)

• -r: probability of reciprocating an edge
  • -l: lambda (in-degree fitness) value
  • -m: mu (out-degree fitness) value [krapivsky only]
  • -e: output edge list file name

Examples

• Generate one network from price’s model with 10^6 nodes.

  ./price -n 1000000 -l 1.0 -e "price_10_6.csv"
      

• Generate ten networks from krapivsky’s model with 10^5 nodes.

  for ((i=1;i<=10;i++)); do ./krapivsky -n 100000 -l 3.5 -m 1.8 -e "krapivsky_10_5_${i}.csv"; done
      

Extending quicknet

Let modelx be the model you wish to implement. In the quicknet/ directery, create a file modelx.c which follows the same format as price.c and krapivsky.c. Make the following changes to the Makefile:

1. Append modelx.c to SRCS
2. Append modelx.o to OBJS
3. append modelx to EXE

Then run

make depend
make modelx
chmod 755 modelx

You should now have the executable modelx in the current directory.

See the paper [1] for a more detailed description of the data structures used in quicknet.

Footnotes

[1] James Atwood, Bruno Ribeiro, and Don Towsley. “Efficient Network Generation under General Preferential Attachment”. WWW Simplex Workshop, 2014.