Sensitivity of Diffusion Dynamics to Network Uncertainty

Abhijin Adiga, Chris J. Kuhlman, Henning S. Mortveit, Anil VullikantiJAIR 2014 · DOI

TL;DR

This paper investigates how robust common network diffusion models (Independent Cascade and Linear Threshold) are to uncertainty in network structure. They find that the Independent Cascade model can be surprisingly sensitive near a critical point, while the Linear Threshold model is generally more stable. This work is crucial for understanding the reliability of predictions made from real-world, often incomplete, network data.

What Problem Does This Paper Address?

Many real-world phenomena, like the spread of diseases, information, or trends, are modeled using diffusion processes on networks. However, the networks we use to model these processes are rarely perfect. They are often inferred from incomplete or noisy data (e.g., social media APIs, experimental measurements). This raises a fundamental question: how much can we trust our diffusion model predictions if the underlying network structure is uncertain? Specifically, how do perturbations in the network affect the dynamics of diffusion and the conclusions we draw from them? Existing research has shown that even small network changes can significantly alter dynamics, but a rigorous understanding of this sensitivity, especially for popular diffusion models, has been lacking.

Methods

The authors tackle this problem by introducing and analyzing two simple models of network perturbation:

  • Uniform Perturbation: Edges are added or deleted between any pair of vertices with a certain probability ($\epsilon$). This is a common model for representing random noise or sampling errors.
  • Degree-Assortative Perturbation: The probability of adding or deleting an edge is proportional to the product of the degrees of the connected vertices. This aims to capture perturbations that might preserve some network properties like degree distribution.

They then rigorously analyze the Independent Cascade (IC) and Linear Threshold (LT) diffusion models under these perturbations. For the IC model, they characterize the sensitivity in terms of the critical transmission probability ($p_c$) and show that sensitivity is maximized near this critical point. For the LT model, they use a random graph correspondence to derive bounds on the expected number of infected nodes. Extensive simulations on real-world networks are used to validate their theoretical findings.

Datasets

The paper uses twenty diverse real-world networks for their experimental analysis. These networks span various domains, including:

  • Autonomous Systems
  • Co-authorship networks (e.g., AstroPh, CondMat)
  • Citation networks (e.g., HepPh, HepTh)
  • Communication networks (e.g., Email-Enron)
  • Social networks (e.g., Epinion, Twitter)
  • Internet peer-to-peer networks (e.g., Gnutella)

A synthetic "Random-Regular-20" graph is also used. The paper provides a table (Table 1) listing key properties of these networks, such as the number of nodes, average degree, and maximum degree.

Key Insights and Ideas

  • IC Model Sensitivity is Localized: The most striking insight is that the Independent Cascade model's diffusion dynamics are not uniformly sensitive to network perturbations. Instead, the sensitivity is highly concentrated around the "critical transmission probability" ($p_c$), where a phase transition from small to large outbreaks occurs. Outside this critical region, the model is surprisingly robust.
  • LT Model is Generally Robust: In contrast to the IC model, the Linear Threshold model with uniform edge weights appears to be quite stable to network perturbations. The expected number of infections changes only gradually with the perturbation parameter $\epsilon$.
  • Transient Behavior is More Sensitive: While the final size of an outbreak might be stable in some cases, the transient behavior (how the number of infections evolves over time) is found to be more sensitive to network uncertainty in both models.
  • Degree-Assortative Perturbations are More Network-Specific: Perturbations that consider node degrees (degree-assortative) seem to have more varied effects across different network structures compared to uniform perturbations, suggesting they might better capture certain real-world noise patterns.

Key Results

  • IC Model Theorem: For the IC model, they formally show that if the transmission probability $p$ is far from the critical probability $p_c$, the number of infections is stable under uniform edge addition. However, if $p$ is close to $p_c$, a small perturbation factor $\epsilon$ can lead to a phase transition, drastically increasing the number of infections.
  • LT Model Theorem: For the LT model, they derive bounds showing that the expected number of infections grows at most linearly with the perturbation parameter $\epsilon$, indicating general robustness.
  • Experimental Validation: Extensive simulations on 20 real-world networks confirm the theoretical predictions for both models, showing good agreement between theoretical insights and empirical observations.
  • Temporal Dynamics: Experiments reveal that temporal characteristics (like the time to peak infections or the peak number of new infections) are generally more sensitive to perturbations than the final infection size.

Limitations and Future Work

  • Specific Perturbation Models: The theoretical results are based on specific, simplified models of network uncertainty (uniform and degree-assortative edge addition). Real-world network uncertainty is likely more complex and may involve dependencies not captured by these models.
  • Focus on Expected Values: While temporal dynamics are analyzed, the primary theoretical focus is on the expected number of infections.
  • Future Work Suggestions: The authors suggest extending their work to:
  • Other diffusion models, especially those with heterogeneous probabilities or weights.
  • More complex noise models that account for dependencies.
  • Investigating the sensitivity to the number of initial sources.
  • Obtaining better theoretical bounds for the LT model, particularly for higher degrees.

Summary updated

BibTeX
@article{adiga2014sensitivity,
  author = {Abhijin Adiga and Chris J. Kuhlman and Henning S. Mortveit and Anil Vullikanti},
  title = {{Sensitivity of Diffusion Dynamics to Network Uncertainty}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  doi = {10.1613/jair.4330},
}

Loading related content...

Figure