Maximizing the size of the giant

DOI10.1239/JAP/1354716664MaRDI QIDQ4903049zbMATH OpenOpenAlexFDO

Authors T. Britton, Pieter Trapman

Publication date 19 January 2013

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.0524, https://projecteuclid.org/euclid.jap/1354716664

zbMATH Keywords

random graphepidemiologybranching process

Mathematics Subject Classification ID

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

Abstract: We consider two classes of random graphs: $(a)$ Poissonian random graphs in which the $n$ vertices in the graph have i.i.d. weights distributed as $X$, where $mathbbE(X)=mu$. Edges are added according to a product measure and the probability that a vertex of weight $x$ shares and edge with a vertex of weight $y$ is given by $1-e^{-xy/(mun)}$. $(b)$ A thinned configuration model in which we create a ground-graph in which the $n$ vertices have i.i.d. ground-degrees, distributed as $D$, with $mathbbE(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.

Recommendations

• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• An old approach to the giant component problem
• Connected components in random graphs with given expected degree sequences
• A new approach to the giant component problem
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees

Cites work

• scientific article; zbMATH DE number 3555176 (Why is no real title available?)
• scientific article; zbMATH DE number 1471878 (Why is no real title available?)
• Epidemics on Random Graphs with Tunable Clustering
• On a conditionally Poissonian graph process
• Random graph dynamics
• Random graphs.
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The phase transition in inhomogeneous random graphs
• Threshold behaviour and final outcome of an epidemic on a random network with household structure

Cited in

(6)

• Epidemics on networks with preventive rewiring
• SIRS epidemics with individual heterogeneity of immunity waning
• The tail does not determine the size of the giant
• Dismantling Sparse Random Graphs
• The Logic of Large Enough
• What to maximize if you must

This page was built for publication: Maximizing the size of the giant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4903049)