Maximizing the size of the giant. (English) Zbl 1257.05158

Britton, Tom; Trapman, Pieter

J. Appl. Probab. 49, No. 4, 1156-1165 (2012).

Summary: 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 \(X_{i}\) with \(E(X_{i})=\mu \), and where there is an edge between \(i\) and \(j\) with probability \(1-e^{-X_{i}X_{j}/(\mu 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) = \mu \). 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 \(\mu \) 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.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C90	Applications of graph theory
60J80	Branching processes (Galton-Watson, birth-and-death, etc.)
92D30	Epidemiology
82B43	Percolation

Keywords:

random graph; branching process; epidemiology

References:

[1]	Andersson, H. (1999). Epidemic models and social networks. Math. Sci. 24 , 128-147. · Zbl 0951.92022
[2]	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. · Zbl 1176.92042
[3]	Bollobás, B. (2001). Random Graphs , 2nd edn. Cambridge University Press. · Zbl 0979.05003
[4]	Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 , 3-122. · Zbl 1123.05083
[5]	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. · Zbl 1147.92034
[6]	Durrett, R. (2006). Random Graph Dynamics . Cambridge University Press. · Zbl 1116.05001
[7]	Jagers, P. (1975). Branching Processes with Biological Applications . John Wiley, London. · Zbl 0356.60039
[8]	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. · Zbl 0916.05064
[9]	Newman, M. E. J. (2002). Spread of epidemic disease on networks. Phys. Rev. E 66 , 016128, 11pp.
[10]	Norros, I. and Reittu, H. (2006). On a conditionally Poissonian graph process. Adv. Appl. Prob. 38 , 59-75. · Zbl 1096.05047