TCL: Bridging the Gap Between Scalability and High-Clustering in Social Network Generation

TL;DR

The Transitive Chung Lu (TCL) model is a breakthrough in synthetic network generation. It manages to do what previous models couldn't: maintain the extreme scalability of the Chung Lu model while accurately capturing the high levels of clustering (transitivity) found in real-world social networks. By introducing a single learnable parameter $\rho$ via an EM algorithm, TCL generates millions of edges in seconds, matching degree distributions and local structures simultaneously.

Problem: The "Scalability vs. Realism" Trade-off

For years, the social network community has struggled with a fundamental trade-off. Simple models like Erdos-Renyi are fast but don't look like real networks. Kronecker Product Graph Models (KPGM) and Chung Lu (CL) models are scalable and capture power-law degree distributions, but they produce graphs that are "too random"—they lack the tight-knit clusters or "triangles" (if A knows B and B knows C, A is likely to know C) that define human society.

On the other end, Exponential Random Graph Models (ERGMs) can model these triangles perfectly but are computationally "heavy," failing once a network exceeds a few thousand nodes.

The "Random Surfer" Insight

The brilliance of TCL lies in its physical intuition. The authors frame the standard Chung Lu model as a "random surfer" process: when an edge is formed, it's like a surfer landing on a random node based solely on that node's popularity (degree).

However, in a real social network, we don't just find friends at random. We find them through existing connections. TCL introduces a transitive closure step:

• With probability $1-\rho$, the model performs a standard random jump (Chung Lu).
• With probability $\rho$, it follows a two-hop path (friend-of-a-friend) to close a triangle.

Correcting the Fast Sampling Bias

Before implementing the transitive logic, the authors identified a critical flaw in the "Fast Chung Lu" (FCL) algorithm: Edge Collision Bias. In FCL, when the same edge is sampled twice, the sample is often rejected. This disproportionately affects high-degree nodes, leading to an underestimation of the "hubs" in a network. TCL introduces a collision queue that "slightly permutes" the nodes, ensuring exactly $M$ edges are placed without distorting the distribution.

The figure above shows how the standard FCL (green) fails to reach the true degree peaks, while the corrected cFCL (blue) matches the ground truth (red) almost perfectly.

Methodology: The Transitive Update

The TCL algorithm (Algorithm 2) doesn't just build a graph from scratch; it uses an iterative update process:

1. Initialize with a corrected Fast Chung Lu graph.
2. For $M$ iterations, select a node $v_j$.
3. With probability $\rho$, perform two uniform steps through the current neighbors to find $v_i$.
4. Add the new edge $e_{ij}$ and remove the oldest edge to maintain constant density.

Learning $\rho$ via EM

How do we know the right $\rho$ for a specific network? The authors use Expectation-Maximization. The "E-step" calculates the responsibility: how likely was an existing edge formed by transitivity versus a random jump? The "M-step" updates $\rho$ based on these expectations. This converges in seconds, even on massive datasets like the Purdue Email logs.

Experiments and Results

The authors tested TCL against real-world data (Facebook, Epinions, Gnutella, Email) and compared it with the state-of-the-art KPGM.

1. Degree Distribution: Both CL and TCL match the ground truth perfectly. KPGM often exhibits "dips" that don't exist in real data.
2. Clustering Coefficients: This is where TCL crushes the competition. Both CL and KPGM show nearly zero clustering, whereas TCL's curve sits right on top of the original data.
3. Efficiency: TCL is $O(M)$, while KPGM is $O(M\log N)$. In practice, this meant generating the Purdue Email graph (millions of edges) was nearly 2.5x faster.

The figure shows local clustering coefficients. TCL (blue/pink) is the only model that tracks the actual data distribution.

Conclusion and Outlook

TCL proves that you don't need complex, non-scalable mathematical frameworks to capture "community" properties like clustering. By simply allowing a random walker to occasionally close a triangle, we get a generator that is both biologically/socially intuitive and computationally lean.

Future Work: While $\rho$ is a powerful heuristic, further research is needed to derive the exact analytical bounds of clustering in such transitive systems. However, for practitioners needing synthetic "social-like" data now, TCL is the new gold standard.