Maximizing the size of the giant

Details Maximizing the size of the giant Maximizing the size of the giant

2010-10-04

arxiv.org/abs/1010.0524v1

Mathematics

Probability

Scientific paper

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 $\mathbb{E}(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/(\mu n)}$. $(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 $\mathbb{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.

Affiliated with

Also associated with

No associations

Rating

Maximizing the size of the giant does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximizing the size of the giant, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximizing the size of the giant will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-274227