Table of Contents
Thesis Summary i
Samenvatting iii
1 Introduction 1
1.1 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Part I: N-intertwined model . . . . . . . . . . . . . . . . . . 4
1.2.2 Part II: Optimization of protection and game theory . . . . 4
1.2.3 Part III: Influence of quarantine on epidemic spread . . . . 5
2 Epidemic modeling 7
2.1 Epidemic modeling in biology . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 Kermack-McKendrick threshold theorem . . . . . . . . . . . 9
2.1.2 Whittle’s threshold theorem . . . . . . . . . . . . . . . . . . 11
2.2 Epidemic Modeling and the Internet . . . . . . . . . . . . . . . . . 12
2.2.1 Kephart and White model (KW) . . . . . . . . . . . . . . . 13
2.2.2 Pastor-Satorras and Vespignani model . . . . . . . . . . . . 14
2.2.3 Modeling scanning worms . . . . . . . . . . . . . . . . . . . 15
2.2.4 Topological aspects of epidemics . . . . . . . . . . . . . . . 16
2.2.5 Sufficient conditions for fast recovery and lasting infection . 17
2.2.6 The Model of Wang et al. . . . . . . . . . . . . . . . . . . . 17
2.2.7 Interactive Markov Chains . . . . . . . . . . . . . . . . . . . 18
2.2.8 Pair-approximation models . . . . . . . . . . . . . . . . . . 19
2.2.9 Percolation on a graph . . . . . . . . . . . . . . . . . . . . . 19
I N-intertwined model 21
3 The exact 2
N state Markov chain 23
3.1 Spectrum of Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.1 The complete graph KN . . . . . . . . . . . . . . . . . . . . 29
vii
viii CONTENTS
3.1.2 The line graph . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.3 The row sum of Q for the line topology . . . . . . . . . . . 31
4 N-intertwined model 33
4.1 The steady-state . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Model approximations . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3 The time evolution of epidemics . . . . . . . . . . . . . . . . . . . . 44
4.4 The role of the spectrum of A . . . . . . . . . . . . . . . . . . . . . 45
4.5 The N-intertwined model and other models . . . . . . . . . . . . . 46
4.5.1 Evaluation of the Kephart and White model . . . . . . . . 47
4.5.2 Average cluster model and isoperimetric constant . . . . . . 47
4.5.3 The model of Wang et al. . . . . . . . . . . . . . . . . . . . 52
4.5.4 The exact 2N Markov chain . . . . . . . . . . . . . . . . . . 52
4.6 Special case – complete bi-partite graph . . . . . . . . . . . . . . . 53
4.6.1 The impact of infection delay . . . . . . . . . . . . . . . . . 55
4.6.2 Simulation analysis . . . . . . . . . . . . . . . . . . . . . . . 57
4.6.3 Extinction probability . . . . . . . . . . . . . . . . . . . . . 59
5 Heterogenous N-intertwined model 65
5.1 General heterogeneous steady-state . . . . . . . . . . . . . . . . . . 66
5.1.1 The generalized Laplacian Q (qi) . . . . . . . . . . . . . . . 67
5.1.2 The critical threshold . . . . . . . . . . . . . . . . . . . . . 70
5.1.3 Bounding λmax (R) . . . . . . . . . . . . . . . . . . . . . . . 72
5.1.4 Additional properties . . . . . . . . . . . . . . . . . . . . . 73
5.2 Special case – the regular graph . . . . . . . . . . . . . . . . . . . . 75
5.2.1 Virus spread on regular graphs with two curing rates . . . . 76
5.3 Special case – the complete bi-partite graph . . . . . . . . . . . . . 77
II Optimization of protection and Game theory 81
6 Optimization of protection 83
6.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Inverse Optimization Problem . . . . . . . . . . . . . . . . . . . . . 84
6.3 Optimization at the Threshold, α = 0 . . . . . . . . . . . . . . . . 84
6.4 Sum of Ratios Fractional Programming, α ∈ (0, 1) . . . . . . . . . 85
6.4.1 Protection Proportional to the Node Degree for α ∈ (0, 1) . 86
6.5 Special case – complete bi-partite graph . . . . . . . . . . . . . . . 90
7 Epidemic, a game theoretic perspective 93
7.1 The virus protection game . . . . . . . . . . . . . . . . . . . . . . . 94
7.1.1 Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . 95
7.1.2 Characterization of equilibrium . . . . . . . . . . . . . . . . 97
7.1.3 Unconstrained case with 2 nodes . . . . . . . . . . . . . . . 100
CONTENTS ix
7.2 Price of anarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.2.1 Social optimum . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.2.2 The worst NEP at the threshold . . . . . . . . . . . . . . . 103
7.2.3 The worst NEP above the threshold . . . . . . . . . . . . . 104
7.3 constrain on the infection probabilities . . . . . . . . . . . . . . . . 105
III Influence of quarantine on epidemic spread 107
8 Virus spread in social networks 109
8.1 Quarantine model and networks . . . . . . . . . . . . . . . . . . . . 110
8.2 Early clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.3 Delayed clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.3.1 Random removal of nodes . . . . . . . . . . . . . . . . . . . 117
8.4 Discussion of results . . . . . . . . . . . . . . . . . . . . . . . . . . 118
9 Conclusions 125
9.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
List of Abbreviations 139
Acknowledgments 141
Curriculum Vitae 143
Publications by the Author 145
NGInfra PhD Thesis Series 147
Abstract
Epidemic theory has wide range of applications in computer networks, from spreading of malware to the information dissemination algorithms. Our society depends more strongly than ever on such computer networks. Many of these networks rely to a large extent on decentralization and self-organization. While decentralization removes obvious vulnerabilities related to single points of failure, it leads to a higher complexity of the system. A more complex type of vulnerability appears in such systems. For instance, computer viruses are imminent threats to all computer networks. We intend to study the interaction between malware spreading and strategies that are designed to cope with them. The main goals of this thesis are: 1. to analyze influence of network topology on infection spread 2. to determine how topology can be used for network protection 3. to formulate and study optimization of malware protection problem with respect to topology 4. to investigate non-cooperative game of security We used analytical tools from various fields to answer these questions. First of all, we have developed homogeneous and heterogeneous N-intertwined, susceptible – infected – susceptible (SIS) model for virus spread. This model is used to determine the influence of topology on the spreading process. For the N-intertwined model, we show that the largest eigenvalue of the adjacency matrix of the graph rigorously defines the epidemic threshold. The results of the model also predict the upper and lower bounds on epidemics as a function of nodal degree. The epidemic threshold is found to be a consequence of the mean field approximation. However, slow convergence to the steady-state justifies the application of the threshold concept. We used the exact 2N-state Markov chain model to explore the phase transition phenomenon for two contrasting cases, namely the line graph and the complete graph. The N-intertwined model assumes that the infection spreading over a link is a Poisson process. By introducing infection delay, we studied the influence of deviation from Poisson process assumption on epidemic threshold for the special case of a complete bi-partite graph. Due to the special structure of bi-partite graphs we were also able to derive approximate formula for the extinction probability in the first phase of the infection. In the case of SIS epidemic models, the effects of infection depend on the protection of individual nodes. We studied optimization of protection scheme for different networks. We use the results from heterogeneous N-intertwined model to determine the global optimum at the threshold. Above the threshold, the problem is a sum of ratios fractional programming problem, which is NP-complete. Therefore, we only determine the upper bound on the optimum. Contrary to the common sense, reducing the probability of infection for higher degree nodes pushes the network out of the global optimum. For the case of complete bi-partite graphs, we derive optimal threshold if only 2 fixed protection rates are available. Computer networks are generally distributed systems and protection cannot be globally optimized. The Internet is an extreme example: there is no global control center, and obtaining complete information on its global state is an illusion. To approach the issue of security over decentralized network, we derived a novel framework for network security under the presence of autonomous decision makers. The problem under the consideration is the N players non-cooperative game. We have established the existence of a Nash equilibrium point (NEP). The willingness of nodes to invest in protection depends on the price of protection. We showed that, when the price of protection is relatively high for all the nodes, the only equilibrium point is that of a completely unprotected network; while if this price is sufficiently low for a single node, it will always invest in protecting itself. We determine bounds on the Price of Anarchy (PoA), that describes how far the NEP is from the global optimum. We have also proposed two methods for steering the network equilibrium, namely by influencing the relative prices and by imposing an upper bound on infection probabilities. A quarantine is another possible measure against the epidemic. A quarantine on a set of network nodes separates them from the rest of the network by removing links. The concept of threshold and the N-intertwined model provides a tool to analyze how quarantine improves the network protection. We studied several different networks from artificially generated to real-world examples using the modularity algorithm. The real-world networks tend to show a better epidemic threshold after clustering than artificially generated graphs. The real-world networks have typically two or three big clusters and several smaller ones, while Barabasi-Albert (BA) and Erdos-Renyi (ER) graphs have several smaller clusters comparable in size. However, the number of removed links in a graph using modularity algorithm is unjustifiably high, suggesting that complete quarantine is not a viable solution for real-world networks.
