Paper Info
Title
Controlling infection by blocking nodes and links simultaneously
Abstract
In this paper we study the problem of controlling the spread of undesirable things (viruses, epidemics, rumors, etc.) in a network. We present a model called the mixed generalized network security model, denoted by MGNS(d), which unifies and generalizes several well-studied infection control model in the literature. Intuitively speaking, our goal under this model is to secure a subset of nodes and links in a network so as to minimize the expected total loss caused by a possible infection (with a spreading limit of d-hops) plus the cost spent on the preventive actions. Our model has wide applications since it incorporates both node-deletion and edge-removal operations. Our main results are as follows: 1 For all 1≤dd+1)-approximation algorithm for computing the optimal solution of MGNS(d). This improves the approximation factor of 2d obtained in [19] for a special case of our model. We derive an O(logn)-approximation for the case d=∞. Moreover, we give a polynomial time $\frac{3}{2}$-approximation for MGNS(1) on bipartite graphs. We prove that for all d∈ℕ∪{∞}, it is $\mathcal{APX}$-hard to compute the optimum cost of MGNS(d) even on 3-regular graphs. We also show that, assuming the Unique Games Conjecture 13, we cannot obtain a $(\frac{3}{2}-\epsilon)$-approximation for MGNS(d) in polynomial time. Our hardness results hold for the special case GNS(d) in [19] as well. We show that an optimal solution of MGNS(d) can be found in polynomial time for every fixed d∈ℕ∪{∞} if the underlying graph is a tree, and the infection cost and attack probability are both uniform. Our algorithm also works for the case where there are budget constraints on the number of secured nodes and edges in a solution. This in particular settles an open question from [21] that asks whether there exists an efficient algorithm for the minimum average contamination problem on trees.
Year
DOI
Venue
2011
10.1007/978-3-642-25510-6_18
WINE
Keywords
Field
DocType
controlling infection,special case,optimal solution,approximation factor,optimum cost,infection cost,polynomial time,approximation algorithm,well-studied infection control model,efficient algorithm,mixed generalized network security
Unique games conjecture,Time complexity,Special case,Approximation algorithm,Discrete mathematics,Mathematical economics,Combinatorics,Mathematical optimization,Existential quantification,Bipartite graph,Network security,Vertex cover,Mathematics
Conference
Citations 
PageRank 
References 
10
0.61
22
Authors
3
Name
Order
Citations
PageRank
Jing He1222.67
Hongyu Liang28416.39
Hao Yuan3121.31