ILDT: Decoding the Structural Evolution of Directed Social Networks

TL;DR

The Iterated Local Directed Transitivity (ILDT) model is a deterministic growth framework designed to simulate directed social networks. By mimicking the "cloning" behavior of new users who inherit the social status and connections of their predecessors, ILDT successfully replicates real-world phenomena: network densification and the dominance of transitive triads over directed cycles.

Background & Motivation: Moving Beyond Undirected Graphs

Traditional social network models often treat relationships as symmetric. However, platforms like Twitter or Epinions operate on Status Theory, where a directed arc indicates that the sender views the recipient as having higher status.

The authors identify a gap: while the original ILT model handled undirected graphs well, it couldn't explain the specific triadic signatures of directed social media. In these networks, "friend of a friend" transitivity ($xoy,yoz⟹xoz$) is far more common than circular 3-cycles. The ILDT model was born to bridge this gap through a deterministic, step-by-step evolution.

Methodology: The Logic of Cloning

At its core, ILDT is defined by a simple yet powerful recursive rule. For every time step $t$:

1. Node Doubling: Every node $x\in G_t$ creates a clone $x^{\prime }$.
2. Reciprocity: A bidirectional arc is formed between $x$ and $x^{\prime }$.
3. Transitive Inheritance: If there was an arc $(x,z)$, we add $(x^{\prime },z)$. If there was $(y,x)$, we add $(y,x^{\prime })$.

This process preserves the "memory" of the initial graph $G_0$ while creating a complex, layered hierarchy.

Figure 1: The logic of adding arcs between parents and clones.

Key Findings: Why It Works

1. The Densification Power Law

Unlike random graphs where the average degree remains constant, social networks get "thicker" over time. The ILDT model proves this mathematically. The number of arcs $e_t$ grows at a rate of $3^t$, while nodes $n_t$ grow at $2^t$.

• Result: $e_t/n_t\sim (1.5{)}^t$. This exponential densification matches empirical observations of maturing online communities.

2. Triad Abundance: Transitive vs. Cyclic

One of the most striking findings in studies of Wikipedia and Epinions is that transitive 3-cycles (A follows B, B follows C, A follows C) are much more frequent than directed 3-cycles (A follows B, B follows C, C follows A). The ILDT model proves that the number of directed 3-cycles $D_t$ only increases by a constant factor ($4imes{D}_{t-1}$), whereas transitive cycles $T_t$ receive a massive boost from the existing arcs in the network.

3. Spectral Fingerprints

The eigenvalues of the adjacency matrix in ILDT graphs display a "fractal-like" distribution in the complex plane. By normalizing these eigenvalues, the authors suggest the existence of a limiting curve as $to\infty$.

Figure 2: Normalized eigenvalues showing the structural progression of the digraph.

Hamiltonian Cycles: Theoretical Interest

An interesting graph-theoretical property discovered is that despite being a social network model, ILDT eventually generates Hamiltonian directed cycles (cycles visiting every node once) for many initial configurations. This suggests that the "cloning" mechanism provides a high degree of connectivity that eventually overcomes the initial sparsity.

Critical Analysis & Conclusion

Takeaway

The ILDT model is a major step in formalizing Status Theory. It provides a rigorous proof that simple local rules (copying neighbors) can lead to complex global signatures (Hamiltonicity, Densification).

Limitations

• Determinism: In the real world, "cloning" isn't perfect. Real users don't follow every person their parent follows.
• Independent Set of Clones: In the current model, clones form an independent set (no arcs between clones). Adding relationships between "peers" (children born at the same time) would increase the model's realism.

Future Outlook

The next frontier for ILDT lies in Spectral Expansion Analysis and Clustering Coefficients. Understanding how quickly info-diffusion happens in these structures could have massive implications for viral marketing and rumor control modeling.