Network Formation under Random Attack and Probabilistic Spread

Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern

Abstract

We study a network formation game where agents balance the benefits of connectivity against the risks of a probabilistic contagion. In this model, an attack starts at a random vertex and spreads via the independent cascade model. We demonstrate that equilibrium networks are naturally sparse, containing $O(n \log n)$ edges, yet they maintain high social welfare ($\Theta(n^2)$), comparable to networks without attack risks.

The Challenge of Probabilistic Contagion

In traditional network formation games, agents pay to build links to maximize their reachability. However, real-world networks—such as the Internet or social groups—are vulnerable to cascading failures or viral spreads. While previous models often assumed deterministic infection (where an infected neighbor always infects you), this research addresses the more complex Independent Cascade Model. Here, if a node is infected, the contagion spreads to each neighbor independently with a fixed probability $p$.

Calculating expected utility in this probabilistic setting is #P-complete, making direct optimization computationally intractable for agents. This paper investigates whether stable (Nash equilibrium) networks still emerge and what structural properties they possess under such strategic risks.

Methodology

The authors employ a game-theoretic approach to analyze pure strategy Nash equilibria. To overcome the computational hardness of calculating exact utilities, they focus on proving structural properties of the graphs:

  • Graph Decomposition: Utilizing decomposition trees to identify subgraphs with high minimum cuts that are prone to "almost certain infection."
  • Probabilistic Analysis: Applying random graph theory and branching processes to model infection propagation in the "small $p$" regime.
  • Equilibrium Constraints: Proving that if a network is too dense, the risk of infection outweighs the benefits of connectivity, prompting rational agents to drop edges to reduce their risk.

Key Insights: The Tension Between Connectivity and Safety

The research identifies a fundamental trade-off: while more edges increase reachability, they also create more pathways for infection.

  1. The Sparsity Constraint: The risk of infection eventually dominates as density increases. This forces equilibrium networks to remain sparse ($O(n \log n)$ edges).
  2. Fragility of Dense Subgraphs: If a subgraph is too well-connected, a single hit anywhere within it likely destroys the entire component. Agents strategically avoid such "fragile" states by limiting their connections.
  3. Welfare Resilience: Despite the threat of attack, a "giant component" of healthy nodes typically survives in equilibrium, ensuring that total system utility remains high.

Key Results

The study provides several formal bounds on the nature of equilibrium networks and their efficiency:

  • Edge Density: Any equilibrium network on $n$ vertices has at most $O(n \log n / p)$ edges. For constant $p$, this is nearly tight.
  • Component Size: Every non-trivial equilibrium network is guaranteed to have a giant component containing at least $n/3$ of the agents.
  • Social Welfare: In the sparse regime ($O(n)$ edges), social welfare is $\Theta(n^2)$, asymptotically matching the welfare of networks where no attacks occur.
Examples of network topologies analyzed for equilibrium properties, including star and cycle configurations.

Limitations and Future Directions

While the paper establishes strong upper bounds, a small gap remains between the $O(n \log n)$ upper bound and the $\Omega(n)$ lower bound for edge density. Future work may explore whether $O(n)$ is the true limit. Additionally, the current model does not account for agent "immunization" or bilateral link formation (where both parties must agree to a link), both of which would significantly alter the strategic landscape. Finally, understanding the convergence of best-response dynamics—how agents might reach these equilibria through trial and error—remains an open question.

Summary updated

Abstract

We study a network formation game where agents receive benefits by forming connections to other agents but also incur both direct and indirect costs from the formed connections. Specifically, once the agents have purchased their connections, an attack starts at a randomly chosen vertex in the network and spreads according to the independent cascade model with a fixed probability, destroying any infected agents. The utility or welfare of an agent in our game is defined to be the expected size of the agent's connected component post-attack minus her expenditure in forming connections. Our goal is to understand the properties of the equilibrium networks formed in this game. Our first result concerns the edge density of equilibrium networks. A network connection increases both the likelihood of remaining connected to other agents after an attack as well the likelihood of getting infected by a cascading spread of infection. We show that the latter concern primarily prevails and any equilibrium network in our game contains only $O(n\log n)$ edges where $n$ denotes the number of agents. On the other hand, there are equilibrium networks that contain $\Omega(n)$ edges showing that our edge density bound is tight up to a logarithmic factor. Our second result shows that the presence of attack and its spread through a cascade does not significantly lower social welfare as long as the network is not too dense. We show that any non-trivial equilibrium network with $O(n)$ edges has $\Theta(n^2)$ social welfare, asymptotically similar to the social welfare guarantee in the game without any attacks.
BibTeX
@inproceedings{chen2019network,
  author = {Yu Chen and Shahin Jabbari and Michael J. Kearns and Sanjeev Khanna and Jamie Morgenstern},
  title = {{Network Formation under Random Attack and Probabilistic Spread}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=gp7Ftqb3fsJ},
}

Loading related content...

Figure