Strategic Stability in Growing Networks: Information Diffusion on the ILT Model

TL;DR

In the rapidly evolving landscape of Online Social Networks (OSNs), does a winning strategy today remain a winning strategy as the network grows? This paper explores this via the Iterated Local Transitivity (ILT) model. The core finding: for two competing agents, if they start at an independent Nash Equilibrium, that equilibrium is "frozen" in time—it remains valid no matter how large the network grows through the ILT process.

Introduction: The Geometry of Influence

Information diffusion is often modeled as a game where agents (marketers, politicians, or influencers) pick "seed nodes" to maximize their reach. However, social networks are not static. They grow through transitivity (the "friend of a friend" effect). The ILT model captures this by iteratively cloning nodes and edges, creating complex, community-rich structures.

The central question: Can we find a Nash Equilibrium (N.E.)—a state where no agent can improve their reach by shifting their seed node—on a small graph and trust that it holds as the graph scales?

Methodology: The ILT Growth Engine

The ILT process is a deterministic way to simulate OSN growth. Starting with a graph $G_0$, every iteration $G_{t+1}$ creates a clone $v^{\prime }$ for every existing node $v$.

• Each clone $v^{\prime }$ is connected to its original $v$.
• $v^{\prime }$ is connected to all the original neighbours of $v$.

This creates a "local transitivity" that mirrors real-world social cliques. The diffusion process (Process D) follows a simple rule: nodes adopt the "color" of their neighbors. If multiple colors reach a node simultaneously, it becomes "grey" (neutral/inactive).

Core Insight: The Stability of Independent N.E.

The authors prove a powerful induction:

1. Utility Scaling: If agents choose seed nodes that are not adjacent (an independent set), their utility in the grown graph $\hat{G}$ is exactly double their utility in the original graph $G$.
2. 2-Agent Robustness: For two agents, the researchers show that moving from a node $v$ to its clone $v^{\prime }$ never improves utility. Thus, if a strategy was optimal in $G_0$, it remains optimal in $G_t$.

Why Does it Fail for 3+ Agents?

The paper provides a sharp counter-example. In a 3-agent game, the "grey node" rule introduces non-linearities. As the network grows, the relative "blocking" power of agents changes. A strategy that was a N.E. in a small group may be disrupted because a third party can now "claim" clones of nodes that were previously contested or neutral.

In the figure above (Fig 2), the authors demonstrate a case where an non-independent N.E. exists in the base graph, but completely disappears in the iterated version.

Experimental Analysis: SOTA Comparison

Unlike Voronoi Games on graphs—which are notoriously difficult to solve and often lack pure-strategy N.E.—the ILT-based competitive diffusion model allows for tractable analysis.

• Voronoi Games: Require exhaustive enumeration; N.E. existence is rare and restricted to highly transitive graphs.
• ILT Diffusion: Allows establishing N.E. on complex, large-scale graphs by simply verifying the seed graph $G_0$.

Critical Insight & Future Outlook

Takeaway: This work bridges the gap between static game theory and dynamic network growth. It proves that the "local" nature of social network evolution preserves the "global" strategic landscape, at least in duopolistic competitions.

Limitations: The model is deterministic. Real-world OSNs have stochastic growth and "long-range" edges (shortcuts) that the ILT model doesn't fully capture. Future research should look into stochastic ILT models and Kronecker graphs to see if this strategic "freezing" still holds.

Conclusion: If you are competing with one other entity for influence in a community that grows by word-of-mouth (transitivity), your best initial move is likely to remain your best move forever.