ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks

Summary: ROLL-tree uses an in-memory roulette-wheel data structure to enable exact Barabási–Albert preferential attachment for scale-free graph generation. ≈1000× faster than state-of-the-art on a single PC; generates 1.1B nodes and 6.6B edges in 62 minutes, and generalizes to other rich-get-richer growth models. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h9b364413fc2fbb0a
Venue: SIGMOD
Year: 2016
Pagerank: 5.6183097e-05
Overall Rank: 6,960 | 53.35%
DOI: 10.1145/2882903.2882964

Incoming Non-self Citations Over Time

Authors

1. Ali Hadian (Iran University of Science and Technology)
2. Sadegh Nobari (Innopolis University)
3. Behrooz Minaei-Bidgoli (Iran University of Science and Technology)
4. Qiang Qu (Innopolis University)

BibTeX Citation

@inproceedings{hadian_sigmod16,
        title = {{ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks}},
        author = {Hadian, Ali and Nobari, Sadegh and Minaei-Bidgoli, Behrooz and Qu, Qiang},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2882964},
        url = {https://dl.acm.org/doi/10.1145/2882903.2882964},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,097	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.7946571e-05
4,922	TrillionG: A Trillion-scale Synthetic Graph Generator using a Recursive Vector Model	2017	SIGMOD	6.3430793e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
331	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00020800828
4,093	SharkDB: An In-Memory Storage System for Massive Trajectory Data	2015	SIGMOD	6.7956344e-05
4,980	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	6.3167773e-05
7,382	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.5223652e-05
12,581	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD	4.9605343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,486	An Efficient Streaming Algorithm for Approximating Graphlet Distributions	2026	SIGMOD
2	10,414	Tree+DAG: An Efficient Index for Resistance Distance Computation on Core-Periphery Graphs	2027	SIGMOD
3	7,279	An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs	2022	VLDB
4	1,843	Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank	2020	VLDB
5	555	Fast Incremental and Personalized PageRank	2011	VLDB
6	2,171	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD
7	4,576	Leveraging History for Faster Sampling of Online Social Networks	2015	VLDB
8	1,303	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
9	6,315	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD
10	4,922	TrillionG: A Trillion-scale Synthetic Graph Generator using a Recursive Vector Model	2017	SIGMOD