Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-27T14:38:07.787Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximizing the Size of the Giant

Part of: Equilibrium statistical mechanics Markov processes Graph theory

Published online by Cambridge University Press:  30 January 2018

Tom Britton  and
Pieter Trapman
Tom Britton*
Affiliation:
Stockholm University
Pieter Trapman*
Affiliation:
Stockholm University
*
∗ Postal address: Department of Mathematics, Stockholm University, 106 91 Stockholm, Sweden.
∗ Postal address: Department of Mathematics, Stockholm University, 106 91 Stockholm, Sweden.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Consider a random graph where the mean degree is given and fixed. In this paper we derive the maximal size of the largest connected component in the graph. We also study the related question of the largest possible outbreak size of an epidemic occurring ‘on’ the random graph (the graph describing the social structure in the community). More precisely, we look at two different classes of random graphs. First, the Poissonian random graph in which each node i is given an independent and identically distributed (i.i.d.) random weight Xi with E(Xi)=µ, and where there is an edge between i and j with probability 1-e-XiXj/(µ n), independently of other edges. The second model is the thinned configuration model in which the n vertices of the ground graph have i.i.d. ground degrees, distributed as D, with E(D) = µ. The graph of interest is obtained by deleting edges independently with probability 1-p. In both models the fraction of vertices in the largest connected component converges in probability to a constant 1-q, where q depends on X or D and p. We investigate for which distributions X and D with given µ and p, 1-q is maximized. We show that in the class of Poissonian random graphs, X should have all its mass at 0 and one other real, which can be explicitly determined. For the thinned configuration model, D should have all its mass at 0 and two subsequent positive integers.

Keywords

Random graphbranching processepidemiology

MSC classification

Primary: 05C80: Random graphs 60J80: Branching processes (Galton-Watson, birth-and-death, etc.) 92D30: Epidemiology
Secondary: 82B43: Percolation
Type
Research Article
Information
Journal of Applied Probability , Volume 49 , Issue 4 , December 2012 , pp. 1156 - 1165
Copyright
© Applied Probability Trust 

References

Andersson, H. (1999). Epidemic models and social networks. Math. Sci. 24, 128–147.Google Scholar
Ball, F. G., Sirl, D. and Trapman, P. (2009). Threshold behaviour and final outcome of an epidemic on a random network with household structure. Adv. Appl. Prob. 41, 765–796.Google Scholar
Bollobás, B. (2001). Random Graphs, 2nd edn. Cambridge University Press.CrossRefGoogle Scholar
Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31, 3–122.Google Scholar
Britton, T., Deijfen, M., Lagerås, A. N. and Lindholm, M. (2008). Epidemics on random graphs with tunable clustering. J. Appl. Prob. 45, 743–756.Google Scholar
Durrett, R. (2006). Random Graph Dynamics. Cambridge University Press.CrossRefGoogle Scholar
Jagers, P. (1975). Branching Processes with Biological Applications. John Wiley, London.Google Scholar
Molloy, M. and Reed, B. (1998). The size of the giant component of a random graph with a given degree sequence. Combinatorics Prob. Comput. 7, 295–305.Google Scholar
Newman, M. E. J. (2002). Spread of epidemic disease on networks. Phys. Rev. E 66, 016128, 11 pp.Google Scholar
Norros, I. and Reittu, H. (2006). On a conditionally Poissonian graph process. Adv. Appl. Prob. 38, 59–75.CrossRefGoogle Scholar