Optimal Resource Allocation for Competitive Spreading Processes on Bilayer Networks

Nicholas J. Watkins, Cameron Nowzari, Victor M. Preciado, George J. PappasIEEE Trans. Control. Netw. Syst 2018 · OpenReview

TL;DR

This paper tackles the challenge of controlling competing "contagions" (like ideas, behaviors, or even diseases) on complex, interconnected networks. They introduce a novel framework for optimally allocating resources to eliminate one contagion while allowing another to persist, using a generalized epidemic model and advanced optimization techniques. This work is crucial for designing effective interventions in diverse scenarios, from marketing campaigns to public health strategies.

What Problem Does This Paper Address?

In today's interconnected world, phenomena like the spread of information, opinions, or even diseases often involve multiple competing "contagions" simultaneously influencing a population. Traditional models often simplify this by focusing on single-layer networks or homogeneous spreaders. However, real-world networks are complex, with different types of connections and individuals who react differently. This paper addresses the critical need to understand and control these competitive spreading processes on such realistic, multi-layered (bilayer) networks. Specifically, the authors aim to find the most cost-effective way to eliminate one competing contagion (e.g., negative word-of-mouth) while ensuring another (e.g., positive brand perception) can survive, or even thrive. This is a significant challenge because the interactions between competing contagions can lead to complex, emergent behaviors that are difficult to predict and control.

Methods

The core of this paper lies in its innovative approach to modeling and controlling competitive spreading processes.

  • Generalized SI₁SI₂S Model: They extend the existing SI₁SI₂S model (Susceptible-Infected₁-Infected₂-Susceptible) to a more general, heterogeneous setting. This means they allow for:
  • Edge-dependent infection rates: The likelihood of spreading depends on the specific connection between two nodes.
  • Node-dependent recovery rates: Individuals recover at different rates.
  • Arbitrary graph topologies: The networks can be directed and complex, not just simple, undirected structures.
  • Mean-Field Approximation: To manage the complexity of exact state-space enumeration (which grows exponentially with the number of nodes), they employ a mean-field approximation. This simplifies the system by focusing on the average behavior of nodes, reducing the state space significantly.
  • Exponential Stability Conditions: They derive necessary and sufficient conditions for the desired equilibrium (one contagion extinct, the other endemic) to be exponentially stable. This means the system will reliably return to this desired state.
  • Optimal Resource Allocation: Building on the stability conditions, they formulate two optimization problems:
  • Minimum Cost Extinction: Find the cheapest way to adjust network parameters (spreading and recovery rates) to achieve the desired extinction. This involves minimizing cost functions associated with these parameters.
  • Fixed Budget Mitigation: Given a fixed budget, find the best allocation of resources to either achieve extinction or, if that's not possible, to minimize the spread of the unwanted contagion as much as possible.
  • Geometric Programming: To solve these optimization problems, they leverage geometric programming, a powerful class of convex optimization problems that can be efficiently solved. They transform the original non-convex problems into solvable geometric programs.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and simulation using synthetic network structures.

Key Insights and Ideas

  • Heterogeneity is Key: The paper strongly emphasizes that real-world networks and spreading processes are rarely homogeneous. Allowing for edge-dependent infection and node-dependent recovery is crucial for accurately modeling and controlling these systems.
  • Competition as a Control Lever: The presence of competing contagions isn't just a nuisance; it can be strategically leveraged. The authors show how to use the dynamics of one contagion to suppress another, turning competition into a tool for control.
  • Mean-Field as a Practical Tool: While acknowledging its limitations, the paper demonstrates the practical utility of the mean-field approximation for designing control strategies. It provides a good approximation for the system's behavior, especially in the steady state, and enables computationally tractable optimization.
  • Geometric Programming for Network Control: The successful application of geometric programming to network control problems is a significant methodological contribution, offering a robust way to find optimal resource allocations.
  • Extinction vs. Mitigation: The distinction between achieving guaranteed extinction (requiring sufficient resources) and mitigating spread (when resources are limited) is a practical and important one, addressed by their two distinct optimization frameworks.

Key Results

  • Necessary and Sufficient Conditions for Exponential Stability: The paper provides clear mathematical criteria for when a chosen contagion can be made to disappear exponentially quickly, while the other persists.
  • Optimal Resource Allocation Frameworks: They successfully formulate and solve two key optimization problems:
  • Minimum Cost Extinction: They show how to find the cheapest way to design network parameters to achieve the desired extinction.
  • Fixed Budget Mitigation: They provide a method to maximize the effectiveness of a limited budget in controlling a contagion.
  • Simulation Validation: Extensive simulations on synthetic networks demonstrate that their optimization methods work well in practice, achieving the desired outcomes in the mean-field regime. They also show that the mean-field approximation is reasonably accurate for the steady-state behavior of the controlled systems.

Limitations and Future Work

  • Mean-Field Accuracy: The authors acknowledge that the mean-field approximation is not always perfectly accurate, especially for the transient dynamics or when stochastic effects are significant. They highlight the need for further research into better approximation schemes and understanding the precise relationship between the approximated and exact stochastic processes.
  • Cost Function Assumptions: The optimization frameworks rely on specific types of cost functions (monotonically decreasing for spreading rates, and posynomials for recovery rates). While they argue these are natural assumptions, exploring a wider range of cost functions could be beneficial.
  • Generalization to k-Layer Networks: The current work focuses on bilayer networks. A natural extension is to generalize the framework to networks with more than two layers and more than two competing processes.
  • More Sophisticated Control Objectives: Future work could explore more complex control objectives, such as simultaneously controlling multiple parameters or achieving specific steady-state behaviors beyond simple extinction/endemic states.
  • Real-World Data Integration: While the framework is applicable to real-world problems, integrating it with actual network data and cost structures would be a valuable next step.

Summary updated

Abstract

We consider a competitive epidemic process in a bilayer network, and develop a framework to find an optimal allocation of control resources to eliminate one of the epidemics. We consider the SI <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> SI <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> S model, a recent generalization of the popular SIS model to the case of two competitive epidemics. We start our analysis by extending the standard SI <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> SI <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> S formulation with homogeneous parameters to a heterogeneous setting with edge-dependent infection rates, and node-dependent recovery rates. We then find necessary and sufficient conditions under which the mean-field approximation of a chosen epidemic process stabilizes to extinction exponentially quickly. Leveraging this result, we develop a framework for the solution of two optimization problems. In the first, we find an optimal allocation of control resources in order to eradicate the chosen epidemic at a minimum cost. In the second, we are given a fixed budget and propose a method which provably attains the extinction condition when sufficient capital is available, and otherwise mitigates the spread of the unwanted epidemic as much as possible. We explore the efficacy of our methods through extensive simulation.
BibTeX
@article{watkins2018optimal,
  author = {Nicholas J. Watkins and Cameron Nowzari and Victor M. Preciado and George J. Pappas},
  title = {{Optimal Resource Allocation for Competitive Spreading Processes on Bilayer Networks}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2018},
  url = {https://openreview.net/forum?id=gLwQDdLWgoD},
}
Figure