 NSFPAR ID:
 10376924
 Date Published:
 Journal Name:
 Network Science
 Volume:
 10
 Issue:
 3
 ISSN:
 20501242
 Page Range / eLocation ID:
 234 to 260
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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 NPhard. 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 realworld 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 ILPbased approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm.more » « less

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 NPhard, we develop a heuristic based on a generalization of the set cover problem. Using experiments on three realworld networks, we compare the performance of the heuristic with some baseline methods.more » « less

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 NPhard, we develop a heuristic based on a generalization of the set cover problem. Using experiments on three realworld networks, we compare the performance of the heuristic with some baseline methods.more » « less

The high reliability required by many futuregeneration network services can be enforced by proper resource assignments by means of logical partitions, i.e., network slices, applied in optical metroaggregation networks. Different strategies can be applied to deploy the virtual network functions (VNFs) composing the slices over physical nodes, while providing different levels of resource isolation (among slices) and protection against failures, based on several available techniques. Considering that, in optical metroaggregation networks, protection can be ensured at different layers, and the slice protection with traffic grooming calls for evolved multilayer protection approaches. In this paper, we investigate the problem of reliable slicing with protection at the lightpath layer for different levels of slice isolation and different VNF deployment strategies. We model the problem through an integer linear program (ILP), and we devise a heuristic for joint optimization of VNF placement and ligthpath selection. The heuristic maps nodes and links over the physical network in a coordinated manner and provides an effective placement of radio access network functions and the routing and wavelength assignment for the optical layer. The effectiveness of the proposed heuristic is validated by comparison with the optimal solution provided by the ILP. Our illustrative numerical results compare the impact of different levels of isolation, showing that higher levels of network and VNF isolation are characterized by higher costs in terms of optical and computation resources.

Networked discrete dynamical systems are often used to model the spread of contagions and decisionmaking 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 polynomialtime 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 realworld networks demonstrate the effectiveness of the proposed heuristics. A full version of the manuscript, source code and data areavailable at: https://github.com/bridgelessqiu/NMINFPEmore » « less