Efficient control of epidemics over random networks

ABSTRACT

Motivated by the modeling of the spread of viruses or epidemics with coordination among agents, we introduce a new model generalizing both the basic contact model and the bootstrap percolation. We analyze this percolated threshold model when the underlying network is a random graph with fixed degree distribution. Our main results unify many results in the random graphs literature. In particular, we provide a necessary and sufficient condition under which a single node can trigger a large cascade. Then we quantify the possible impact of an attacker against a degree based vaccination and an acquaintance vaccination. We define a security metric allowing to compare the different vaccinations. The acquaintance vaccination requires no knowledge of the node degrees or any other global information and is shown to be much more efficient than the uniform vaccination in all cases.

REFERENCES

• 1: J. Balogh and B.G. Pittel. Bootstrap percolation on the random regular graph. Random Structures Algorithms, 30(1-2):257--286, 2007.
• 2: Noam Berger , Christian Borgs , Jennifer T. Chayes , Amin Saberi, On the spread of viruses on the internet, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 3: B. Bollobás. Random graphs. Cambridge University Press, Cambridge, second edition, 2001.
• 4: C. Borgs, J. Chayes, A. Ganesh, and A. Saberi. How to distribute antidote to control epidemics.
• 5: T. Britton, S. Janson, and A. Martin-Löf. Graphs with specified degree distributions, simple epidemics, and local vaccination strategies. Adv. in Appl. Probab., 39(4):922--948, 2007.
• 6: R. Cohen, K. Erez, D. ben Avraham, and S. Havlin. Resilience of the internet to random breakdowns. Phys. Rev. Lett., 85(21):4626--4628, Nov 2000.
• 7: R. Cohen, S. Havlin, and D. ben Avraham. Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett., 91(24), 2003.
• 8: M. Draief, A. Ganesh, and L. Massoulié. Thresholds for virus spread on networks. Ann. Appl. Probab., 18(2):359--378, 2008.
• 9: Rick Durrett, Random Graph Dynamics (Cambridge Series in Statistical and Probabilistic Mathematics), Cambridge University Press, New York, NY, 2006
• 10: N. Fountoulakis. Percolation on sparse random graphs with given degree sequence, 2007.
• 11: A.J. Ganesh, L. Massoulié, and D.F. Towsley. The effect of network topology on the spread of epidemics. In INFOCOM, pages 1455--1466, 2005.
• 12: M.O. Jackson and L. Yariv. Diffusion of behavior and equilibrium properties in network games. The American Economic Review, 97(2), 2007.
• 13: Svante Janson, The probability that a random multigraph is simple, Combinatorics, Probability and Computing, v.18 n.1-2, p.205-225, March 2009 [doi>10.1017/S0963548308009644]
• 14: S. Janson. On percolation in random graphs with given vertex degrees. Electronic Journal of Probability, 14:86--118, 2009.
• 15: Svante Janson , Malwina J. Luczak, A simple solution to the k-core problem, Random Structures & Algorithms, v.30 n.1-2, p.50-62, January 2007 [doi>10.1002/rsa.v30:1/2]
• 16: J. Kleinberg. Cascading behavior in networks: algorithmic and economic issues. In Algorithmic game theory, pages 613--632. Cambridge Univ. Press, Cambridge, 2007.
• 17: M. Lelarge. Diffusion and cascading behavior in random networks, http://www.di.ens.fr/ lelarge/.
• 18: Marc Lelarge, Diffusion of Innovations on Random Networks: Understanding the Chasm, Proceedings of the 4th International Workshop on Internet and Network Economics, December 17-20, 2008, Shanghai, China [doi>10.1007/978-3-540-92185-1_25]
• 19: M. Lelarge. Economics of Malware: Epidemic Risks Model, Network Externalities and Incentives. In Fifth bi-annual Conference on The Economics of the Software and Internet Industries, 2009.
• 20: Marc Lelarge , Jean Bolot, A local mean field analysis of security investments in networks, Proceedings of the 3rd international workshop on Economics of networked systems, August 22-22, 2008, Seattle, WA, USA [doi>10.1145/1403027.1403034]
• 21: Marc Lelarge , Jean Bolot, Network externalities and the deployment of security features and protocols in the internet, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 22: Petros Maniatis , Mema Roussopoulos , T. J. Giuli , David S. H. Rosenthal , Mary Baker, The LOCKSS peer-to-peer digital preservation system, ACM Transactions on Computer Systems (TOCS), v.23 n.1, p.2-50, February 2005 [doi>10.1145/1047915.1047917]
• 23: Michael Molloy , Bruce Reed, A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, v.6 n.2/3, p.161-179, March-May 1995
• 24: S. Morris. Contagion. Rev. Econom. Stud., 67(1):57--78, 2000.
• 25: M.E.J. Newman. The structure and function of complex networks. SIAM Rev., 45(2):167--256 (electronic), 2003.
• 26: R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Physical review letters, 86(14):3200--3203, 2001.
• 27: David Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theoretical Computer Science, v.282 n.2, p.231-257, 10 June 2002 [doi>10.1016/S0304-3975(01)00055-X]
• 28: Oliver Riordan, The k-core and branching processes, Combinatorics, Probability and Computing, v.17 n.1, p.111-136, January 2008 [doi>10.1017/S0963548307008589]
• 29: F. Vega-Redondo. Complex social networks, volume 44 of Econometric Society Monographs. Cambridge University Press, Cambridge, 2007.
• 30: D.J. Watts. A simple model of global cascades on random networks. Proc. Natl. Acad. Sci. USA, 99(9):5766--5771 (electronic), 2002.
• 31: Nicholas Weaver , Vern Paxson , Stuart Staniford , Robert Cunningham, A taxonomy of computer worms, Proceedings of the 2003 ACM workshop on Rapid malcode, October 27-27, 2003, Washington, DC, USA [doi>10.1145/948187.948190]
• 32: Cliff Changchun Zou , Lixin Gao , Weibo Gong , Don Towsley, Monitoring and early warning for internet worms, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948136]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Design, Performance, Theory

Keywords:
epidemics, random graphs, vaccination