Maximizing the size of the giant - Mathematics > ProbabilityReportar como inadecuado

Maximizing the size of the giant - Mathematics > Probability - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We consider two classes of random graphs: $a$ Poissonian random graphs inwhich the $n$ vertices in the graph have i.i.d.\ weights distributed as $X$,where $\mathbb{E}X = \mu$. Edges are added according to a product measure andthe probability that a vertex of weight $x$ shares and edge with a vertex ofweight $y$ is given by $1-e^{-xy-\mu n}$. $b$ A thinned configuration modelin which we create a ground-graph in which the $n$ vertices have i.i.d.\ground-degrees, distributed as $D$, with $\mathbb{E}D = \mu$. The graph ofinterest is obtained by deleting edges independently with probability $1-p$.In both models the fraction of vertices in the largest connected componentconverges 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 explicitlydetermined. For the thinned configuration model $D$ should have all its mass at0 and two subsequent positive integers.

Autor: Tom Britton, Pieter Trapman


Documentos relacionados