How Clustering Affects Epidemics in Random Networks

Emilie Coupechoux, Marc LelargearXiv 2012 · OpenReview

TL;DR

This paper introduces a new model for random networks that allows for tunable clustering coefficients alongside a given degree distribution. They analyze how this clustering impacts the spread of "epidemics" (like information or diseases) through two models: diffusion and a symmetric threshold model, finding that clustering generally inhibits diffusion but has a more complex, connectivity-dependent effect on contagion.

What Problem Does This Paper Address?

Understanding how information, diseases, or innovations spread through networks is crucial in many fields, from epidemiology to social science. While much research has focused on random networks with specific degree distributions (how many connections nodes have), real-world networks often exhibit significant "clustering" – meaning friends of friends are also likely to be friends. This clustering can profoundly affect how things spread. Previous models often lacked the ability to independently control both the degree distribution and the clustering coefficient, making it difficult to isolate the specific impact of clustering. This paper aims to fill that gap by providing a tractable model that allows for this control and analyzing its consequences for epidemic spread.

Methods

The authors introduce a novel random graph model that builds upon the standard configuration model. Their approach involves probabilistically replacing nodes in a base random graph with cliques (fully connected subgraphs). This "clique replacement" mechanism allows them to tune the clustering coefficient of the network while keeping the underlying degree distribution fixed. They then analyze two epidemic models on these clustered networks:

  1. Diffusion Model: Inspired by epidemic models, where nodes transmit an "infection" to their neighbors with a certain probability, independently.
  2. Symmetric Threshold Model: Where a node becomes active only if a certain threshold of its neighbors are already active. This model encompasses phenomena like coordination games and contagion processes.

They derive analytical results for the conditions under which global cascades (widespread adoption/infection) occur and compute their size, using techniques like branching process approximations.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Clustering is a double-edged sword: While clustering generally hinders simple diffusion processes, its effect on contagion (where adoption depends on neighbors' behavior) is more nuanced.
  • Connectivity matters for contagion: In low-connectivity networks, clustering inhibits contagion. However, in high-connectivity networks, clustering can actually favor the emergence of large-scale cascades, though it might reduce their ultimate size.
  • A new tunable model: The proposed graph model provides a powerful tool for studying the isolated effects of clustering on network dynamics, which was previously challenging.
  • Beyond simple diffusion: The symmetric threshold model captures more complex social dynamics where individual decisions are correlated, offering a richer framework for understanding real-world spread phenomena.

Key Results

  • Diffusion Inhibition: For both diffusion and contagion models, clustering generally inhibits the spread of epidemics.
  • Contagion Complexity: For the contagion model, the impact of clustering depends on the network's connectivity. In low-connectivity regimes, clustering inhibits contagion. In high-connectivity regimes, clustering can favor the possibility of global cascades but reduce their size.
  • Analytical Framework: The paper provides explicit formulas for the conditions leading to global cascades and their sizes for both diffusion and symmetric threshold models, as a function of degree distribution and clustering.
  • Regular and Power-Law Graphs: These analytical results are applied to specific graph types (regular and power-law with exponential cutoff), providing concrete insights into how clustering affects epidemic spread in these common network structures.

Limitations and Future Work

  • Model Simplifications: The model, while powerful, still relies on approximations and specific mechanisms for introducing clustering. Real-world networks might have more complex interdependencies.
  • Focus on Final State: The analysis primarily focuses on the final state of the epidemic (whether a cascade occurs and its size), rather than the detailed temporal dynamics of the spread.
  • Future Directions: The authors suggest that their framework can be extended to study other network phenomena and control strategies for epidemics. Further exploration of the interplay between clustering, degree distribution, and different epidemic models is also a natural next step.

Summary updated

Abstract

Motivated by the analysis of social networks, we study a model of random networks that has both a given degree distribution and a tunable clustering coefficient. We consider two types of growth processes on these graphs: diffusion and symmetric threshold model. The diffusion process is inspired from epidemic models. It is characterized by an infection probability, each neighbor transmitting the epidemic independently. In the symmetric threshold process, the interactions are still local but the propagation rule is governed by a threshold (that might vary among the different nodes). An interesting example of symmetric threshold process is the contagion process, which is inspired by a simple coordination game played on the network. Both types of processes have been used to model spread of new ideas, technologies, viruses or worms and results have been obtained for random graphs with no clustering. In this paper, we are able to analyze the impact of clustering on the growth processes. While clustering inhibits the diffusion process, its impact for the contagion process is more subtle and depends on the connectivity of the graph: in a low connectivity regime, clustering also inhibits the contagion, while in a high connectivity regime, clustering favors the appearance of global cascades but reduces their size. For both diffusion and symmetric threshold models, we characterize conditions under which global cascades are possible and compute their size explicitly, as a function of the degree distribution and the clustering coefficient. Our results are applied to regular or power-law graphs with exponential cutoff and shed new light on the impact of clustering.
BibTeX
@misc{coupechoux2012how,
  author = {Emilie Coupechoux and Marc Lelarge},
  title = {{How Clustering Affects Epidemics in Random Networks}},
  year = {2012},
  eprint = {1202.4974},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1202.4974},
}
Figure