# A Scalable Generative Graph Model with Community Structure

Source: [A Scalable Generative Graph Model with Community Structure](<https://www.sota2.com/research/paper/68fa2dc21e209131ce85c67c>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-24T16:28:24.624Z

Authors: Tamara G. Kolda, Ali Pinar, Todd Plantenga, C. Seshadhri

Published: 2013-02-27T00:53:12.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Synthetic Network Generation on DBLP](<https://www.sota2.com/research/sota/synthetic-network-generation-on-dblp.md>): Synthetic Network Generation; DBLP; Transitivity: 6.09.

- [Synthetic Network Generation on PolBlogs (Triangle, Clustering, Eigenvalue, Degree Centrality)](<https://www.sota2.com/research/sota/synthetic-network-generation-on-polblogs-triangle-clustering-eigenvalue-degree-centrality.md>): Synthetic Network Generation; PolBlogs; Triangle Similarity (MMD): 0.88.

- [Synthetic Network Generation on Yelp friendship network](<https://www.sota2.com/research/sota/synthetic-network-generation-on-yelp-friendship-network.md>): Synthetic Network Generation; Yelp friendship network; Triangle Ratio (10^-4): 2.27.

- [Synthetic Network Generation on DBLP (GFDL Metrics)](<https://www.sota2.com/research/sota/synthetic-network-generation-on-dblp-gfdl-metrics.md>): Synthetic Network Generation; DBLP; GFDL1: 13.84.

- [Synthetic Network Generation on YouTube](<https://www.sota2.com/research/sota/synthetic-network-generation-on-youtube.md>): Synthetic Network Generation; YouTube; Eigenvalue MMD: 6.42.

- [Synthetic Network Generation on Yelp](<https://www.sota2.com/research/sota/synthetic-network-generation-on-yelp.md>): Synthetic Network Generation; Yelp; GFDL1 Link Prediction Accuracy: 0.73.

- [Synthetic Network Generation on DBLP (Link Prediction Utility)](<https://www.sota2.com/research/sota/synthetic-network-generation-on-dblp-link-prediction-utility.md>): Synthetic Network Generation; DBLP; Link Prediction Accuracy: 85.

- [Synthetic Network Generation on YouTube (Link Prediction Accuracy)](<https://www.sota2.com/research/sota/synthetic-network-generation-on-youtube-link-prediction-accuracy.md>): Synthetic Network Generation; YouTube; Link Prediction Accuracy Ratio: 91.

- [Synthetic Network Generation on YouTube (GFDL1, GFDL2)](<https://www.sota2.com/research/sota/synthetic-network-generation-on-youtube-gfdl1-gfdl2.md>): Synthetic Network Generation; YouTube; GFDL1 Score: 2.24.

- [Synthetic Network Generation on PolBlogs](<https://www.sota2.com/research/sota/synthetic-network-generation-on-polblogs.md>): Synthetic Network Generation; PolBlogs; GFDL1 Score: 2.09.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1302.6636>)

[PDF](<https://arxiv.org/pdf/1302.6636.pdf>)