# A Scalable Generative Graph Model with Community Structure

arXiv: https://arxiv.org/abs/1302.6636 · HTML: https://mlsanity.com/paper/1302.6636/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2013.

## Built on by (most cited first, 10 of 10)

- [Properties and Performance of the ABCDe Random Graph Model with Community Structure](https://mlsanity.com/paper/2203.14899/) (2022)
- [Using Motif Transitions for Temporal Graph Generation](https://mlsanity.com/paper/2306.11190/) (2023)
- [Efficient Dynamic Attributed Graph Generation](https://mlsanity.com/paper/2412.08810/) (2024)
- [MG-GCN: Scalable Multi-GPU GCN Training Framework](https://mlsanity.com/paper/2110.08688/) (2021)
- [GraphTune: A Learning-based Graph Generative Model with Tunable Structural Features](https://mlsanity.com/paper/2201.11494/) (2022)
- [SANGEA: Scalable and Attributed Network Generation](https://mlsanity.com/paper/2309.15648/) (2023)
- [A Sparse Tensor Generator with Efficient Feature Extraction](https://mlsanity.com/paper/2405.04944/) (2024)
- [Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms](https://mlsanity.com/paper/2405.16726/) (2024)
- [Efficient Discovery of Motif Transition Process for Large-Scale Temporal Graphs](https://mlsanity.com/paper/2504.15979/) (2025)
- [Efficient Synthetic Network Generation via Latent Embedding Reconstruction](https://mlsanity.com/paper/2606.00934/) (2026)

## Abstract (arXiv)

Network data is ubiquitous and growing, yet we lack realistic generative network models that can be calibrated to match real-world data. The recently proposed Block Two-Level Erdss-Renyi (BTER) model can be tuned to capture two fundamental properties: degree distribution and clustering coefficients. The latter is particularly important for reproducing graphs with community structure, such as social networks. In this paper, we compare BTER to other scalable models and show that it gives a better fit to real data. We provide a scalable implementation that requires only O(d_max) storage where d_max is the maximum number of neighbors for a single node. The generator is trivially parallelizable, and we show results for a Hadoop MapReduce implementation for a modeling a real-world web graph with over 4.6 billion edges. We propose that the BTER model can be used as a graph generator for benchmarking purposes and provide idealized degree distributions and clustering coefficient profiles that can be tuned for user specifications.