Maximizing the size of the giant

DOI10.1239/JAP/1354716664zbMATH Open1257.05158arXiv1010.0524OpenAlexW2963685758MaRDI QIDQ4903049FDOQ4903049

Authors: T. Britton, Pieter Trapman 

Publication date: 19 January 2013

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

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.

Full work available at URL: https://arxiv.org/abs/1010.0524

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

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)

Cites Work

• The phase transition in inhomogeneous random graphs
• Random graphs.
• Random graph dynamics
• Threshold behaviour and final outcome of an epidemic on a random network with household structure
• Title not available (Why is that?)
• On a conditionally Poissonian graph process
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Epidemics on Random Graphs with Tunable Clustering
• Title not available (Why is that?)

Cited In (6)

• SIRS epidemics with individual heterogeneity of immunity waning
• Epidemics on networks with preventive rewiring
• 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)