More Like this

1. Blocking the Propagation of Two Simultaneous Contagions over Networks

   Carscadden, H ; Kuhlman, C ; Marathe, M ; Ravi, SS ; Rosenkrantz, D ( December 2020 , International conference on complex networks and their applications)

   null (Ed.)

   We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of infected nodes subject to a budget constraint on the total number of nodes that can be vaccinated. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. Since the optimization problem is NP-hard, we develop a heuristic based on a generalization of the set cover problem. Using experiments on three real-world networks, we compare the performance of the heuristic with some baseline methods. 

   more » « less
2. Techniques for blocking the propagation of two simultaneous contagions over networks using a graph dynamical systems framework

   https://doi.org/10.1017/nws.2022.18  

   Carscadden, Henry L. ; Kuhlman, Chris J. ; Marathe, Madhav V. ; Ravi, S. S. ; Rosenkrantz, Daniel J. ( September 2022 , Network Science)

   Abstract We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NP-hard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many real-world networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILP-based approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm. 

   more » « less
3. Techniques for Blocking the Propagation of Two Simultaneous Contagions over Networks Using a Graph Dynamical Systems Framework

   Carscadden, Henry L. ; Kuhlman, Chris J. ; Marathe, Madhav V. ; Ravi, S. S. ; Rosenkrantz, Daniel J. ( August 2022 , Network science)

   We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NP-hard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many real-world networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILP-based approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm. 

   more » « less
4. Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems: Complexity, Special Case Algorithms and Heuristics

   https://doi.org/10.1609/aaai.v36i9.21174  

   Qiu, Zirou ; Chen, Chen ; Marathe, Madhav ; Ravi, S.S. ; Rosenkrantz, Daniel J. ; Stearns, Richard ; Vullikanti, Anil ( June 2022 , Proceedings of the AAAI Conference on Artificial Intelligence)

   Networked discrete dynamical systems are often used to model the spread of contagions and decision-making by agents in coordination games. Fixed points of such dynamical systems represent configurations to which the system converges. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of affected nodes is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a nontrivial fixed point of the system with the minimum number of affected nodes. We establish that, unless P = NP, there is no polynomial-time algorithm for approximating a solution to this problem to within the factor n^(1 - epsilon) for any constant epsilon > 0. To cope with this computational intractability, we identify several special cases for which the problem can be solved efficiently. Further, we introduce an integer linear program to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with greedy selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the proposed heuristics. A full version of the manuscript, source code and data areavailable at: https://github.com/bridgelessqiu/NMIN-FPE 

   more » « less
5. Using Dominating Sets to Block Contagions in Social Networks

   Bao, R. ; Hancock, M. ; Kuhlman, C. ; Ravi, S.S. ( November 2022 , IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining)

   Abstract—There are myriad real-life examples of contagion processes on human social networks, e.g., spread of viruses, information, and social unrest. Also, there are many methods to control or block contagion spread. In this work, we introduce a novel method of blocking contagions that uses nodes from dominating sets (DSs). To our knowledge, this is the first use of DS nodes to block contagions. Finding minimum dominating sets of graphs is an NP-Complete problem, so we generalize a well-known heuristic, enabling us to customize its execution. Our method produces a prioritized list of dominating nodes, which is, in turn, a prioritized list of blocking nodes. Thus, for a given network, we compute this list of blocking nodes and we use it to block contagions for all blocking node budgets, contagion seed sets, and parameter values of the contagion model. We report on computational experiments of the blocking efficacy of our approach using two mined networks. We also demonstrate the effectiveness of our approach by comparing blocking results with those from the high degree heuristic, which is a common standard in blocking studies. Index Terms—contagion blocking, dominating sets, threshold models, social networks, simulation, high degree heuristic 

   more » « less