ROLL

Here we publish the codes used by our papers. You could freely use them in your academic research with proper citation to the original papers. We reserve the rights of any commercial use.

Tool Introduction and Download

ROLL [ref] is a tool for fast generation of gigantic Barabasi-Albert graphs. Barabasi-Albert is a model for generating synthetic graphs that exhibit the properties of large real-world networks, such as the World-Wide-Web, Citation networks and social networks. Networks generated by the Barabasi-Albert model exhibit the scale-free property, i.e. their degree distribution follows a power-law.

The following image illustrates how a BA-graph is incrementally generated. The BA model starts with an initial network with size m_0. Each new node is added to m existing nodes with probabilities proportional to the degree of each existing node. In other words, the more connections a node has, the more frequently the node will receive new connection.

roll

This package contains various implementations for the Barabasi-Albert model, as discussed [ref]. The difference between these implementations is in their algorithmic approach for roulette wheel selection from a dynamic distribution. These algorithms are listed below:

The ROLL roulette wheel methods, specifically the ROLL-tree algorithm, are specifically designed to enable fast generation of scale-free networks with the Barabasi-Albert model. Details are explained in the ROLL paper [ref].

How to Use ROLL

  • Clone ROLL: git clone https://github.com/alihadian/ROLL.git
  • ROLL is using Maven for building the package, ensure maven is installed on the system. To build the package, type: cd ROLL mvn package
  • Execute the jar file: java -jar target/ROLL-0.3-SNAPSHOT-jar-with-dependencies.jar -n 1000 [other params]

parameters:

  • -n number of nodes
  • -m number of edges per node, i.e. the average degree (default = 2)
  • -o output file name (default: no output)
  • -s sampling mode (simple, roll-bucket, roll-tree, SA)

output:

The saves resulting graph is saved in a text file. Also, the performance measures (execution speed and time taken by various components) is printed in the standard output.

You should explicitly define the output file (using -o switch), or otherwise no output file is created. The output file contains the edge list of the graph, where each line contains a single edge: source_node_id target_node_id (tab-delimtited). for example: 0 1 0 2 1 2 ...

More details can be found at https://github.com/alihadian/ROLL.

Citing the Paper

If you find the usefullness of our code, please cite the following work in your papers. Thanks.

Ali Hadian, Sadegh Nobari, Behrouz Minaei-Bidgoli, Qiang Qu: ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks. SIGMOD Conference 2016: 1829-1842

BibTex: Link ref
@inproceedings{DBLP:conf/sigmod16/roll,
author = {Ali Hadian and
Sadegh Nobari and
Behrouz Minaei{-}Bidgoli and
Qiang Qu},
title = {{ROLL:} Fast In-Memory Generation of Gigantic Scale-free Networks},
booktitle = {{SIGMOD}},
pages = {1829–1842},
year = {2016}
}