Darwini: Scaling Realistic Social Graphs to 3 Trillion Edges

TL;DR

Darwini is a high-performance, distributed graph generator developed by researchers at Facebook and the University of Houston. Unlike prior models that focus solely on power-law degree distributions, Darwini captures the nuanced structural properties of real-world networks—specifically the local clustering coefficient and degree skew. By leveraging the Apache Giraph framework, it can generate synthetic graphs with trillions of edges that are indistinguishable from real social networks in terms of system performance benchmarks.

Problem & Motivation: The Realism-Scale Tradeoff

In graph processing research, there is a constant tension between Data Privacy and System Fidelity. While synthetic graphs protect user identity, they often fail to mimic the "topological bottlenecks" of real-world data.

Existing models have three fatal flaws:

1. Restrictive Distributions: Models like Kronecker are hard-coded for power-law distributions, failing for networks like Facebook which have "friend caps."
2. Coarse Clustering: Models like BTER assume all nodes with the same degree have the same clustering coefficient, which is false in practice.
3. Scalability: Fitting models to massive graphs often requires manual tuning or incurs prohibitive computational overhead.

Darwini’s insight: To match the clustering coefficient distribution, you must first match the triangle count.

Methodology: The Three-Stage Evolution

Darwini operates on a "Decompose and Interconnect" philosophy.

1. Target Attribution

Darwini extracts the degree distribution $F_{deg}$ and the per-degree clustering coefficient distribution $F_{cc}(d)$ from a source graph. Each synthetic vertex is assigned a target $d_i$ and $c_i$.

2. Intra-Community Edge Creation

The algorithm calculates the number of triangles $N_{riangle,i}$ each vertex needs. It groups vertices into "buckets" where $N_{riangle,i}$ is similar. Using the Erdos-Renyi model, it adds edges within these buckets with a probability $P_e$ calculated to meet the expected triangle count.

3. Inter-Community Connectivity

The "residual degree" (the degree still needed after bucket edges) is filled by connecting vertices across different buckets. Crucially, this stage uses a degree-similarity heuristic to maintain assortativity (the tendency of similar nodes to connect), ensuring the joint-degree distribution remains realistic.

Experimental Results: Precision at Scale

The researchers evaluated Darwini against BTER, Kronecker, and several others using Facebook subgraphs, DBLP, and Twitter data.

Metric Accuracy

As shown in the clustering coefficient comparison, Darwini follows the source distribution across the entire spectrum, whereas BTER diverges significantly for high-degree nodes.

System Performance Fidelity

The true test of a synthetic graph is whether a system (like Apache Giraph) behaves $X$ same on the synthetic data as it does on the real data. For "Friends-of-Friends" (FoF) counting, Kronecker graphs ran 3.5x faster due to low clustering, making them useless for benchmarking. Darwini’s runtime was nearly identical to the real graph.

Critical Analysis & Conclusion

Darwini’s primary contribution is the shift from "Global Growth Models" to "Local Metric Matching." By focusing on triangles and assortativity, it captures the density and connectivity patterns that actually stress hardware.

Takeaway: If you are benchmarking distributed graph systems, the clustering coefficient distribution is as important as the degree distribution. Darwini provides the first open-source tool capable of generating these "stress-test" graphs at a 3-trillion-edge scale.

Limitations:

• Single Community Assignment: Darwini assigns nodes to one community, whereas real users inhabit overlapping circles (Work, Family, Hobbies). This causes a slight "dip" in PageRank distributions.
• Metadata: It currently generates structure only, not vertex/edge attributes which are essential for modern Graph ML tasks.