Source-linked AI summary
A Scalable Generative Graph Model with Community Structure
Tamara G. Kolda, Ali Pinar, Todd Plantenga, C. Seshadhri
TL;DR
Realistic, scalable graph generators must match both degree distributions and clustering coefficients, but existing models often fail to reproduce real-world clustering. The paper develops and evaluates an implementable BTER generator, finding close matches to real clustering behavior while supporting massive graphs and benchmarking.
Problem
Many generative models fail to match the clustering coefficients of real-world graphs, whose degree distributions and clustering differ from random graphs.
Method
The paper provides a directly parameterized, scalable BTER implementation that uses degree distributions and degree-wise clustering coefficients to generate graphs through affinity blocks and independently generated edges.
Results
BTER provides a very close match to clustering coefficients in large real data and models a graph with 120M nodes and 4.4B edges in less than 25 minutes on a 32-node Hadoop cluster.
Takeaways & Limitations
BTER and its proposed degree and clustering profiles can support graph-processing benchmarks with realistic large-scale degree and triangle structure.
Takeaways & Limitations
BTER is limited to simple graphs and does not model complex community structures such as bipartite or hierarchical organization.
Abstract
from arXiv · showhide
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.
1. Introduction.
The paper addresses the need for scalable generative graph models that reproduce degree distributions and clustering coefficients, properties that many existing models fail to match simultaneously. It details BTER’s implementation, scalability, empirical comparisons, and benchmarking use.
- Real-world networks commonly have heavy-tailed degree distributions and higher clustering coefficients than random graphs with the same degree distribution.
- BTER uses degree distributions and degree-wise clustering coefficients as inputs to generate graphs with similar behavior.Nodes are divided into affinity blocks to capture community structure from local clustering measurements.
- The paper provides a reference implementation that directly calculates BTER parameters without iterative optimization, while independently generated edges can support streaming scenarios.
- The scalable implementation requires O(dmax) storage and O(log dmax) operations per edge, and independent edge generation enables parallelization.Here dmax is the maximum degree.
- BTER approximates degree distributions and clustering behavior in large heavy-tailed graphs, including a graph with over 130 million nodes and 4.6 billion edges.
- For benchmarking without a target graph, the paper recommends generalized log-normal degree distributions as an alternative to standard power laws.
2. Notation and background.
This section defines graph degree and clustering terminology, then explains the independent-edge Chung–Lu mechanism used for global links and its practical caveats.
- The degree distribution is the sequence {n_d}, where n_d counts nodes of degree d and determines the graph’s total node and edge counts.
- A wedge is a length-2 path, and it is closed when its endpoints are connected, forming a triangle.
- Clustering coefficients measure the proportion of closed wedges, with BTER focusing on clustering coefficients by degree.
- BTER models affinity blocks with Erdős–Rényi graphs and uses a Chung–Lu variation for global links spanning those blocks.
- Fast Chung–Lu generates 2m endpoint selections independently instead of testing all n^2 possible edges, with node i selected at probability d_i/2m.
- The resulting expected degree of node i is d_i, although individual degrees follow a Poisson distribution and may vary around that target.
- Degree-1 nodes can be misrepresented because approximately 36% of potential degree-1 nodes are unselected and another 28% reach degree 2 or larger.The implementation can counter this with a blowup factor β.
- Independent endpoint selection can create self-edges and repeat edges, which the implementation discards and whose practical impact was small in experiments.
3. BTER Generative Graph Model.
BTER generates graphs by combining dense intra-block Erdős–Rényi edges with inter-block Chung–Lu edges, using degree distribution and degree-wise clustering as inputs. Its implementation organizes nodes and blocks with compact data structures to support scalable independent edge generation.
- Model structure: BTER organizes nodes into affinity blocks and groups so dense local connectivity can reproduce clustering while preserving the target degree distribution.Blocks ideally contain d + 1 vertices, and groups compress blocks with shared size and weight.
- Inputs: The model accepts the desired degree distribution {n_d} and clustering coefficients by degree {c_d} as its two user-specified inputs.These quantities may be measured from an existing graph or set for benchmarking.
- Generation phases: Phase 1 adds dense Erdős–Rényi edges within affinity blocks, with block density chosen from the target clustering coefficient.This phase is designed to achieve each vertex’s desired clustering coefficient without exceeding its desired degree in expectation.
- Generation phases: Phase 2 adds inter-block edges by constructing a Chung–Lu graph over vertices’ excess degrees after Phase 1.The excess degree is the remaining degree requirement, and the resulting Chung–Lu graph completes the construction.
- Scalable implementation: The implementation targets independent edge insertions so edge generation can be parallelized, while compact affinity-block structures avoid storing per-node preprocessing state.The design addresses preprocessing storage, repeated Phase 1 edges, and scalable edge generation.
3.4. Preprocessing Algorithm.
The preprocessing algorithm converts degree and clustering targets into compact block, group, and excess-degree information. It calibrates Phase 1 connectivity and expected repeated draws so later sampling can generate the desired edge structure efficiently.
- Preprocessing state: Preprocessing computes degree indices, counts of higher-degree nodes, fill-node requirements, group weights, and sampling parameters for the generation phases.Several quantities are derived rather than stored explicitly to reduce space.
- Affinity-block assignment: Homogeneous blocks contain d + 1 degree-d nodes, while incomplete blocks use fill nodes and remaining nodes become bulk nodes in new groups.The algorithm processes degrees in order and handles the final group specially when too few nodes remain.
- Connectivity calibration: For a block with minimum degree d_b and target clustering c_d_b, the Phase 1 connectivity is set to ρ_b = 3√c_d_b.The choice compensates for Phase 2 edges, which add wedges and likely contribute few triangles.
- Repeated edges: Phase 1 uses extra draws to account for repeated independently generated edges, treating the target number of unique edges as a coupon-collector problem.The weighting formula determines how many draws are needed in expectation for the desired unique-edge count.
- Validation: 10,000 random trials produced an average number of unique edges exactly equal to the desired value.The experiment illustrates the expected behavior of the repetition-correction formula.
- Phase 1 sampling: Phase 1 sampling selects a weighted affinity group, a uniform block within it, and two distinct nodes from that block.Weighted sampling costs O(log g_max) work, with g_max ≤ d_max.
3.6. Phase 2.
Phase 2 completes vertices’ degree requirements by sampling edges from their expected excess degrees. It uses weighted degree selection, filler-versus-bulk selection, and a blowup factor to address degree-1 nodes.
- Excess-degree model: Phase 2 inserts edges using a Chung–Lu model over expected excess degrees, with the number of inserted edges determined by the total excess-degree weight.Ignoring relatively rare duplicate edges, the number of Phase 2 edges equals this total weight.
- Sampling: Each Phase 2 edge selects a degree proportional to w_d, chooses filler or bulk nodes using r_d, then samples a node uniformly from that category.The weighted selection costs O(log d_max), while the remaining operations are constant time.
- Degree-1 handling: The degree-1 pool is difficult to calibrate because approximately 36% of potential degree-1 nodes are unselected and another 28% receive degree 2 or larger.A blowup factor β ≥ 1 enlarges the candidate pool without changing the expected number of attached edges.
3.7. Independent Edge Generation.
BTER generates each edge independently by choosing between its two phases, enabling parallel and vectorized implementations. Deduplication then removes repeated undirected edges, including in the Hadoop MapReduce implementation.
- Cost and deduplication: Edge generation costs O(log(d_max)) per edge, but deduplication is the expensive step because independent sampling creates repeated edges.Hashing both endpoint orders to the same key supports removal of duplicate undirected edges.
- Sampling procedures: Each Phase 1 edge samples a weighted group, block, and two distinct nodes, while each Phase 2 edge independently samples two excess-degree-weighted nodes.The procedures are specified as separate phase and node samplers.
- Optimization: The procedure can be bulked or vectorized by processing phase totals separately, improving runtime performance without changing the sampling design.The text specifically notes vectorization in MATLAB as an example.
- Parallel implementation: Hadoop MapReduce assigns edge creation to map tasks and duplicate removal to reducers that collect equal edge hashes.The implementation uses a custom input format and compression between map and reduce phases.
- Evaluation: The evaluation considers BTER on multiple real-world datasets, including the largest publicly available graph modeled to match degree distribution at the time.Additional log-binned and cumulative degree-distribution plots are provided in the appendices.
4. Numerical Comparisons.
On small graphs, BTER matches real degree distributions comparably to Chung–Lu while better matching clustering coefficients and leading eigenvalues than SKG and Chung–Lu. Large-scale experiments show close characteristic matches, scalable Hadoop execution, smoothing of discontinuous degree distributions, and very close clustering-coefficient matches.
- Small data: BTER and Chung–Lu closely match the real degree distributions, while SKG exhibits visible oscillations and misses the highest-degree nodes.Even with noise correction, SKG tends to overestimate low-degree nodes and miss the highest-degree nodes.
- Small data: BTER provides a much closer match to real clustering coefficients than SKG and Chung–Lu, which lack mechanisms for reliably closing wedges into triangles.The comparison links BTER’s advantage to its ability to reproduce community structure.
- Small data: BTER provides a much closer match to the real graph’s leading adjacency-matrix eigenvalues, especially the first few.The paper conjectures that matching triangle structure is needed alongside degree distribution to fit eigenvalues in graphs with community structure.
- Large data: BTER matches large real-world graphs closely in node count, edge count, maximum degree, average degree, and global clustering coefficient.The large-data experiments use real-world graph collections and BTER-generated graphs.
- Large data: On a 32-node Hadoop cluster, twitter-2010 has 10 times more edges than hollywood-2011 but takes less than half the computation time.Hadoop parallelism yields a substantial timing advantage for the larger graph.
- Large data: BTER smooths discontinuities in degree distributions because realized node degrees can deviate by one or two from their expected degrees.The smoothing effect is visible near degree 10 in amazon-2008, whereas clustering coefficients show a very close match.
5. Proposed Benchmark Parameters and Scalability.
The paper proposes tunable degree and clustering-coefficient distributions for BTER benchmarking, then evaluates generated graphs and a Hadoop implementation for scalability. The implementation achieves scalable edge generation while duplicate-edge removal remains the main bottleneck.
- 5.1. Idealized Degree Distribution: The target degree distribution is specified by average degree and maximum degree, with parameters selected by a search over discrete PL or GLN distributions.The fitting procedure searches distribution parameters for user-specified d̄ and dmax, while the benchmark construction requires the tail probability to be sufficiently small.
- 5.1. Idealized Degree Distribution: The proposed benchmark uses discrete generalized log-normal degree distributions because power laws can impose an abrupt cutoff near the maximum degree.For d̄ = 64 and d* = 10^5, discrete PL gives Pr(D = d*) = 2.16×10^-9, whereas discrete GLN gives 8.35×10^-12 and fades more naturally.
- 5.2. Idealized Clustering Coefficients: Clustering coefficients are modeled with a parameterized curve whose decay parameter is fitted to a target global clustering coefficient.The example setups use cmax = 0.9 with target GCC 0.15, and cmax = 0.5 with target GCC 0.10.
- 5.3. Example Graphs: BTER-generated graphs are fairly close to their intended degree distributions and clustering-coefficient-by-degree profiles.The example shown has 256M vertices and 4B edges, with log-binned results.
- 5.4. Scalability Test: The MapReduce implementation generates edges in parallel, but reduce-phase deduplication loses scalability because sorting, shuffling, merging, and disk spillover constrain performance.Map-task scalability remains excellent through 128 tasks, while overall parallel performance drops after 32 million vertices.
- 5.4. Scalability Test: The implementation demonstrates massive-graph modeling by constructing a graph with 120M nodes and 4.4B edges in less than 25 minutes on a 32-node Hadoop cluster.The scalability study uses generated graphs with controlled degree-distribution and clustering-coefficient inputs.
6. Conclusions and Future Work.
The paper presents BTER and its tunable distributions as tools for large-scale graph modeling and benchmarking. It also identifies important scope boundaries, including missing directed, weighted, typed, and richer community structures.
- Limitations and Future Work: The model captures affinity-block communities but does not represent larger hierarchical or otherwise richer community structures.The paper notes that real-world graphs may contain hierarchy or other complex behavior beyond the model’s affinity blocks.
- Conclusions: BTER and its proposed degree and clustering-coefficient distributions are intended to support graph-processing benchmarks at very large scales.The degree distributions allow average and maximum degree to be modified, while clustering curves embed triangle structure and the generation algorithm parallelizes edge creation.
- Limitations and Future Work: BTER is limited to simple graphs and does not currently support directed, weighted, or node- and edge-typed graphs.The paper also identifies bipartite and near-bipartite structures as outside the current model.
- Limitations and Future Work: The paper sketches extensions that could pair or hierarchically arrange affinity blocks to model bipartite or hierarchical structure.These possibilities are presented as potential modifications rather than implemented capabilities.
Appendix A. Coupon Collector Derivation.
The appendix derives a coupon-collector bound for independently sampling distinct pairs within an affinity block. The result quantifies how many draws are expected to obtain a specified fraction of distinct pairs.
- Setup: The derivation models possible pairs in an affinity block as coupons sampled uniformly with replacement.The theorem applies when the universe U is the set of possible pairs in an affinity block.
- Theorem: The expected number of draws needed to obtain ρ|U| distinct coupons is |U| ln(1/(1 − ρ)) + O(1).The bound holds for ρ ∈ (0, 1).
- Proof: The proof decomposes collection into waiting times for successive new coupons, whose means are |U|/(|U| − i).When i distinct coupons have been collected, a new coupon appears with probability 1 − i/|U|.
- Proof: Summing the waiting-time bounds produces the logarithmic expression using a standard harmonic-sum approximation.The appendix invokes the harmonic bound involving ln r, Euler–Mascheroni constant γ, and O(1/r).
Appendix B. Plots with Log-Binned Data.
Appendix B reproduces degree-distribution and clustering-coefficient plots using logarithmic degree bins. The bins grow geometrically, with degree-distribution values summed and clustering coefficients averaged within each bin.
- Figures B.1–B.4 use logarithmic binning for degree-distribution and clustering-coefficient plots.
- Each degree bin covers consecutive degrees from b_k through b_{k+1} − 1.
- ω = 1.5 makes each successive bin 50% larger than the previous one.
- Degree-distribution data are summed within bins, while clustering coefficients by degree are averaged.
Appendix C. Cumulative Degree Distributions.
Appendix C reproduces the paper’s degree-distribution plots using cumulative data.
- Figures C.1–C.3 reproduce degree-distribution plots using cumulative data.
Appendix D. Parameter Study for Generalized Log-Normal Distribution.
Appendix D illustrates degree distributions generated from different parameters of the generalized log-normal distribution.
- Figure D.1 shows example degree distributions generated with different generalized log-normal distribution parameters.
- The examples use maximum degree d* = 10^6 and node count n = 10^7.