# The impact of degree variability on connectivity properties of large
networks††thanks: A preliminary version of this work was presented at the 12th
Workshop on Algorithms and Models for the Web Graph (WAW ’15), Eindhoven,
Netherlands, December 2015.

Lasse Leskelä  Aalto University School of Science, Department of Mathematics
and Systems Analysis, Otakaari 1 Espoo, Finland.
math.aalto.fi/en/research/stochastics/ Hoa Ngo22footnotemark: 2

###### Abstract

The goal of this work is to study how increased variability in the degree
distribution impacts the global connectivity properties of a large network. We
approach this question by modeling the network as a uniform random graph with
a given degree sequence. We analyze the effect of the degree variability on
the approximate size of the largest connected component using stochastic
ordering techniques. A counterexample shows that a higher degree variability
may lead to a larger connected component, contrary to basic intuition about
branching processes. When certain extremal cases are ruled out, the higher
degree variability is shown to decrease the limiting approximate size of the
largest connected component.

##  1 Introduction

Digital communication networks and online social media have dramatically
increased the spread of information in our society. As a result, the global
connectivity structure of communication between people appears to be better
modeled as a dimension-free unstructured graph instead of a geometrical graph
based on a two-dimensional grid, and the spread of messages over an online
network can be modeled as an epidemic on a large random graph. When the nodes
of the network spread the epidemic independently of each other, the final
outcome of the epidemic, or the ultimate set of nodes that receive a message,
corresponds to the connected component of the initial root node in a randomly
thinned version of the original communication graph called the epidemic
generated graph [BST14]. This is why the sizes of connected components are
important in studying information dynamics in unstructured networks.

A characterizing statistical feature of many communication networks is the
high variability among node degrees, which is manifested by observed
approximate power-law shapes in empirical measurements. The simplest
mathematical model that allows to capture the degree variability is the so-
called configuration model which is defined as follows. Fix a set of nodes
labeled using $[n]=\\{1,2,\dots,n\\}$ and a sequence of nonnegative integers
$d_{n}=\\{d_{n}(1),\dots,d_{n}(n)\\}$ such that
$\ell_{n}=\sum_{i=1}^{n}d_{n}(i)$ is even. Each node $i$ gets assigned
$d_{n}(i)$ half-links, or stubs, and then we select a uniform random matching
among the set of all half-links. A matched pair of half-links will form a
link, and we denote by $X_{i,j}$ the number of links with one half-link
assigned to $i$ and the other half-link assigned to $j$. The resulting random
matrix $(X_{i,j})$ constitutes a random undirected multigraph on the node set
$[n]$. This multigraph is called the _configuration model_ generated by the
degree sequence $d_{n}$. The multigraph is called simple if it contains no
loops ($X_{i,i}=0$ for all $i$) and no parallel links ($X_{i,j}\leq 1$ for all
$i,j$). The distribution of the multigraph conditional on being simple is the
same as the distribution of the uniform random graph in the space of graphs on
$[n]$ with degree sequence $d_{n}$ [vdH14, Prop. 7.13].

A tractable mathematical way to analyze large random graphs is to let the size
of the graph grow to infinity and approximate the empirical degree
distribution of the random graph

$p_{n}(k)=\frac{1}{n}\sum_{i=1}^{n}1(d_{n}(i)=k)$

using a limiting probability distribution $p$ on the infinite set of
nonnegative integers $\mathbb{Z}_{+}$. One of the key results in the theory of
random graphs is the following, first derived by Molloy and Reed [MR95, MR98]
and strengthened by Janson and Łuczak [JL09]. Assume that the collection of
degree sequences $(d_{n})$ is such that the corresponding empirical degree
distributions satisfy

$\displaystyle p_{n}(k)$ $\displaystyle\to p(k)\quad\text{for all $k\geq 0$},$
(1.1) $\displaystyle\sup_{n}m_{2}(p_{n})$ $\displaystyle<\infty,$

and that $p(2)<1$ and $0<m_{1}(p)<\infty$, where $m_{i}(p)=\sum_{k}k^{i}p(k)$
denotes the $i$th moment $p$. Then [JL09, Thm 2.3, Rem 2.7] the size of the
largest connected component $\lvert{\mathcal{C}}_{\rm{max}}\rvert$ in the
configuration model multigraph (and in the associated uniform random graph)
converges according to

$n^{-1}\lvert{\mathcal{C}}_{\rm{max}}\rvert\to\zeta_{\rm CM}(p)\qquad\text{(in
probability)},$ (1.2)

where the constant $\zeta_{\rm CM}(p)\in[0,1]$ is uniquely characterized by
$p$ and satisfies $\zeta_{\rm CM}(p)>0$ if and only if $m_{2}(p)>2m_{1}(p)$.
The above fundamental result is important because it has been extended to
models of wide generality (e.g. [BJR11]).

Most earlier mathematical studies (and extensions) have focused on
establishing the phase transition (showing that there is a critical phenomenon
related to whether or not $\zeta_{\rm CM}(p)>0$), and studying the behavior of
the model near the critical regime. On the other hand, for practical
applications it may crucial to be able to predict the size of $\zeta_{\rm
CM}(p)$ based on estimates of the degree distribution $p$. This paper aims to
obtain qualitative insight into this question by studying properties of the
functional $p\mapsto\zeta_{\rm CM}(p)$ in detail analyzing its sensitivity to
the variability of $p$.

##  2 Branching functional of the configuration model

###  2.1 Size biasing and downshifting

The configuration model, like many real-world networks, exhibits a size-bias
phenomenon in degrees, in that "your friends are likely to have more friends
than you do". The _size biasing_ of a probability distribution $\mu$ on the
nonnegative real line $\mathbb{R}_{+}$ (or a subset thereof) with mean
$m_{1}(\mu)=\int x\mu(dx)\in(0,\infty)$, is the probability distribution
$\mu^{*}$ defined by

$\mu^{*}(B)=\frac{\int_{B}x\mu(dx)}{m_{1}(\mu)},\quad B\subset\mathbb{R}_{+}.$

If $X$ and $X^{*}$ are random numbers with distributions $\mu$ and $\mu^{*}$,
respectively, then

$\mathbb{E}\,\phi(X^{*})=\frac{\mathbb{E}\,\phi(X)X}{\mathbb{E}X}$ (2.1)

for any real function $\phi$ such that the above expectations exist. The size
biasing of a probability distribution $p$ on the nonnegative integers
$\mathbb{Z}_{+}$ is given by

$p^{*}(k)=\frac{kp(k)}{m_{1}(p)},\quad k\in\mathbb{Z}_{+}.$

Furthermore, the _downshifted size biasing_ of $p$ is the probability
distribution $p^{\circ}$ defined by

$p^{\circ}(k)=p^{*}(k+1),\quad k\in\mathbb{Z}_{+}.$ (2.2)

If $X^{*}$ and $X^{\circ}$ are random integers distributed according to
$p^{*}$ and $p^{\circ}$, respectively, then $X^{\circ}$ and $X^{*}-1$ are
equal in distribution. If $G_{p}(s)=\sum_{k\geq 0}s^{k}p(k)$ denotes the
generating function of $p$, then the generating functions of $p^{*}$ and
$p^{\circ}$ can be written as

$G_{p^{*}}(s)=\frac{s}{m_{1}(p)}G_{p}(s)\qquad\text{and}\qquad
G_{p^{\circ}}(s)=\frac{1}{m_{1}(p)}G_{p}(s).$ (2.3)

######  Example 2.1.

The size biasing of the Dirac point mass at $x$ is given by
$\delta_{x}^{*}=\delta_{x}$.

######  Example 2.2.

The downshifted size biasing of binomial distribution
$\operatorname{Bin}(n,p)$ is given by
$\operatorname{Bin}(n,p)^{\circ}=\operatorname{Bin}(n-1,p)$.

######  Example 2.3.

The size biasing of the Pareto distribution $\operatorname{Par}(\alpha,c)$
with shape $\alpha>1$ and scale $c>0$ (with density function $f(t)=\alpha
c^{\alpha}t^{-\alpha-1}1(t>c)$) is given by
$\operatorname{Par}(\alpha,c)^{*}=\operatorname{Par}(\alpha-1,c)$.

######  Example 2.4.

The size biasing of the lognormal distribution
$\operatorname{LNor}(b,\sigma^{2})$ with location $b\in\mathbb{R}$ and scale
$\sigma>0$ (with density
$f(t)=\frac{1}{\sqrt{2\pi\sigma^{2}t}}\exp(-\frac{(\log
t-b)^{2}}{2\sigma^{2}})$ for $t>0$ ) is given by
$\operatorname{LNor}(b,\sigma^{2})^{*}=\operatorname{LNor}(b+\sigma^{2},\sigma^{2})$
[AGK15, Equation (45)].

######  Example 2.5.

Denote by $\operatorname{MPoi}(\mu)$ the $\mu$-mixed Poisson distribution on
$\mathbb{Z}_{+}$ with probability mass function

$p(k)=\int_{\mathbb{R}_{+}}e^{-\lambda
k}\frac{\lambda^{k}}{k!}\,\mu(d\lambda),\quad k\in\mathbb{Z}_{+},$

where $\mu$ is a probability distribution on $\mathbb{R}_{+}$ with a finite
nonzero mean. In this case the downshifted size biasing is given by
$\operatorname{MPoi}(\mu)^{\circ}=\operatorname{MPoi}(\mu^{*})$. Especially,
by Example 2.1,
$\operatorname{Poi}(x)^{\circ}=\operatorname{MPoi}(\delta_{x})^{\circ}=\operatorname{Poi}(x)$
for a standard Poisson distribution with mean $x$, and by Example 2.3,
$\operatorname{MPoi}(\operatorname{Par}(\alpha,c))^{\circ}=\operatorname{MPoi}(\operatorname{Par}(\alpha-1,c))$
for a Pareto-mixed Poisson distribution with shape $\alpha>1$ and scale $c>0$.

###  2.2 Definition of the branching functional

Given a probability distribution $p$ on $\mathbb{Z}_{+}$, we denote by

$\eta(p)=\inf\\{s\geq 0:G_{p}(s)=s\\}$

the smallest fixed point of the generating function $G_{p}(s)=\sum_{k\geq
0}s^{k}p(k)$ in the interval $[0,1]$. Classical branching process theory (e.g.
[GS01, vdH14]) tells that $\eta(p)\in[0,1]$ is well defined and equal to the
extinction probability of a Galton–Watson process with offspring distribution
$p$. We denote the corresponding survival probability by

$\zeta(p)=1-\eta(p).$ (2.4)

As a consequence of [JL09, Thm 2.3], the limiting maximum component size of a
configuration model with limiting degree distribution $p$ corresponds to the
survival probability of a two-stage branching process where the root node has
offspring distribution $p$ and all other nodes have offspring distribution
$p^{\circ}$ defined by (2.2). Therefore, the branching functional
$p\mapsto\zeta_{\rm CM}(p)$ appearing in (1.2) can be written as

$\zeta_{\rm CM}(p)=1-G_{p}(\eta(p^{\circ})).$ (2.5)

The following two elementary examples will serve to illustrate the
nonconvexity for the branching functional (see Remark 2.8).

######  Example 2.6.

For the Dirac measure $\delta_{n}$ at an integer $n\geq 1$ we have

$\zeta_{\rm CM}(\delta_{n})=\begin{cases}0,&\quad n=1,\\\ 1,&\quad n\geq
2.\end{cases}$ (2.6)

To verify this it suffices to note that $\zeta_{\rm
CM}(\delta_{n})=1-G_{\delta_{n}}(\eta(\delta_{n}^{\circ}))=1-\eta(\delta_{n}^{\circ})^{n}$
where $\eta(\delta_{n}^{\circ})=\eta(\delta_{n-1})$ equals one for $n=1$ and
zero for $n\geq 2$.

######  Example 2.7.

For the uniform distribution on $\\{1,n\\}$ we have

$\zeta_{\rm CM}\left(\frac{1}{2}\delta_{1}+\frac{1}{2}\delta_{n}\right)\ =\
\begin{cases}0,&\quad n=1,2,\\\ 1-o(1),&\quad n\gg 2.\end{cases}$ (2.7)

To verify this, an elementary computation shows that the downshifted size
biasing of $p_{n}=\frac{1}{2}\delta_{1}+\frac{1}{2}\delta_{n}$ equals

$p_{n}^{\circ}\ =\
\left(\frac{1}{n+1}\right)\delta_{0}+\left(\frac{n}{n+1}\right)\delta_{n-1}.$

For $n=1,2$ the support of $p_{n}^{\circ}$ is contained in $\\{0,1\\}$ which
implies that $\eta(p_{n}^{\circ})=1$. On the other hand, because
$G_{p_{n}^{\circ}}(s)\to 0$ uniformly on $[0,s_{0}]$ for all $s_{0}<1$, it
follows that $\eta(p_{n}^{\circ})=o(1)$ as $n\to\infty$. Hence the fact that
$G_{p_{n}}(s)\leq s$ implies $G_{p_{n}}(\eta(p_{n}^{\circ}))=o(1)$, and we may
conclude (2.7).

######  Remark 2.8.

The functional $p\mapsto\zeta_{\rm CM}(p)$ is not convex nor concave. To see
why, consider the probability distribution $\alpha p+(1-\alpha)q$ where
$\alpha=1/2$, $p=\delta_{1}$, and $q=\delta_{n}$ for some integer $n\geq 1$.
Then by formula (2.6),

$~\alpha\zeta_{\rm CM}(p)+(1-\alpha)\zeta_{\rm CM}(q)\ =\
\frac{1}{2}\quad\text{for all}\ n\geq 2,$

whereas by formula (2.7),

$\zeta_{\rm CM}(\alpha p+(1-\alpha)q)\ =\ \begin{cases}0,&\quad n=1,2,\\\
1-o(1),&\quad n\gg 2.\end{cases}$

###  2.3 Continuity properties

We will next discuss continuity properties of branching functionals using two
convergence concepts. For probability distributions
$\mu,\mu_{1},\mu_{2},\dots$ on $\mathbb{R}_{+}$, we denote convergence in
distribution by $\mu_{n}\xrightarrow{d}\mu$. For probability distributions on
$\mathbb{R}_{+}$ with finite first moments, we denote
$\mu_{n}\xrightarrow{W}\mu$ if $\mu_{n}$ converges to $\mu$ in distribution
and $(\mu_{n})$ is uniformly integrable. Recall [AGS08, Theorem 7.1.5] that
$\mu_{n}\xrightarrow{W}\mu$ is equivalent to convergence in the Wasserstein
metric defined by

$d_{W}(\mu,\nu)\ =\
\inf\int_{\mathbb{R}_{+}\times\mathbb{R}_{+}}|x-y|\,\gamma(dx,dy),$

where the infimum is computed over the set of all couplings of $\mu$ and
$\nu$. See [LV13] for a probabilistic discussion about the Wasserstein metric.

######  Theorem 2.9.

Let $p,p_{n}$ be probability measures on $\mathbb{Z}_{+}$ each with a finite
nonzero mean. If $p_{n}\xrightarrow{W}p$ and $p(1)>0$, then $\zeta_{\rm
CM}(p_{n})\to\zeta_{\rm CM}(p)$.

The proof of the theorem is based on the following two lemmas. The first
states that convergence in the Wasserstein metric implies convergence in
distribution for associated size biasings.

######  Lemma 2.10.

Let $\mu,\mu_{1},\mu_{2},\dots$ be probability measures on $\mathbb{R}_{+}$
each with a finite nonzero mean. If $\mu_{n}\xrightarrow{W}\mu$, then
$\mu_{n}^{*}\xrightarrow{d}\mu^{*}$ and
$\mu_{n}^{\circ}\xrightarrow{d}\mu^{\circ}$.

###### Proof.

Uniform integrability and $\mu_{n}\xrightarrow{d}\mu$ imply [Kal02, Lemma
4.11] that $m(\mu_{n})\to m(\mu)$. If $\phi:\mathbb{R}_{+}\to\mathbb{R}$ is
continuous and has compact support, then $\psi(x)=x\phi(x)$ is continuous and
bounded, and hence

$\mu_{n}^{*}(\phi)=\frac{\mu_{n}(\psi)}{m(\mu_{n})}\to\frac{\mu(\psi)}{m(\mu)}=\mu^{*}(\phi).$

We conclude that $\mu_{n}^{*}\to\mu^{*}$ vaguely. In addition, the uniform
integrability of $(\mu_{n})$ implies tightness of $(\mu_{n}^{*})$, and we may
conclude [Kal02, Lemma 5.20] that $\mu_{n}^{*}\xrightarrow{d}\mu^{*}$. The
fact that $\mu_{n}^{\circ}\xrightarrow{d}\mu^{\circ}$ follows from the
continuous mapping theorem [Kal02, Theorem 4.27]. ∎

The following result on the continuity of extinction probabilities is probably
well known. Because we did not find it in the literature, the proof is
included in Appendix A for reader’s convenience.

######  Lemma 2.11.

Let $p,p_{n}$ be probability measures on $\mathbb{Z}_{+}$. If
$p_{n}\xrightarrow{d}p$ and $p(0)>0$, then $\eta(p_{n})\to\eta(p)$.

###### Proof of Theorem 2.9.

By Lemma 2.10, $p_{n}^{\circ}\xrightarrow{d}p^{\circ}$. Moreover,
$p^{\circ}(0)=\frac{p(1)}{m_{1}(p)}>0$. Hence
$\eta(p_{n}^{\circ})\to\eta(p^{\circ})$ by Lemma 2.11. The assumption that
$p_{n}\xrightarrow{d}p$ also implies that $G_{p_{n}}\to G_{p}$ uniformly on
$[0,1]$, as explained in the proof of Lemma 2.11. Hence

$\zeta_{\rm CM}(p_{n})\ =\ 1-G_{p_{n}}(\eta(p_{n}^{\circ}))\ \to\
1-G_{p}(\eta(p^{\circ}))\ =\ \zeta_{\rm CM}(p).$

∎

###  2.4 Upper bounds

A simple closed-form expression for $\zeta_{\rm CM}(p)$ is not readily
available due to the implicit definition of $\eta(p^{\circ})$. To get a
qualitative insight into the behavior of $\zeta_{\rm CM}(p)$ as a functional
of $p$, analytical bounds will be valuable. The following result presents a
fundamental upper bound which only depends on the mean degree distribution.
This result is implicitly contained in the proof of [BT12, Theorem 2]. Here we
provide a short and transparent proof.

######  Proposition 2.12.

For any probability distribution $p$ with a finite nonzero mean $\lambda$,

$\displaystyle\zeta_{\rm CM}(p)\ \leq\ \frac{\lambda}{2}.$ (2.8)

###### Proof.

Denote $z=\eta(p^{\circ})$, so that by definition, $G_{p^{\circ}}(z)=z.$
Moreover, the convexity of $G_{p^{\circ}}$ implies that $G_{p^{\circ}}(s)\leq
s$ for all $s\in[z,1]$. Next, by applying (2.3) we can write

$G_{p}(s)=1-\lambda\int_{s}^{1}G_{p^{\circ}}(s)ds.$

Hence,

$\zeta_{\rm CM}(p)\ =\ 1-G_{p}(z)\ =\
\lambda\int_{z}^{1}G_{p^{\circ}}(s)\,ds,$

and we may conclude that

$\zeta_{\rm CM}(p)\ \leq\ \lambda\int_{z}^{1}s\,ds\ \leq\
\lambda\int_{0}^{1}s\,ds\ =\ \frac{\lambda}{2}.$

∎

The upper bound in Proposition 2.12 tells nothing for graphs of mean degree
two or higher. The following result provides a crude upper bound applicable
also for $\lambda\leq 2$. Similar bounds for standard branching processes have
been derived in [SK14, VYZ14].

######  Proposition 2.13.

For any probability distribution $p$ on $\mathbb{Z}_{+}$ with a finite nonzero
mean $\lambda$,

$\zeta_{\rm CM}(p)\ \leq\ 1-p(0)-\frac{p(1)^{2}}{\lambda}.$ (2.9)

###### Proof.

Let $p^{\circ}$ be the downshifted size biasing of $p$ defined by (2.2).
Because a branching process with offspring distribution $p^{\circ}$ goes
extinct at the first step with probability $p^{\circ}(0)$, it follows that

$\eta(p^{\circ})\geq p^{\circ}(0)=\frac{p(1)}{\lambda}.$

Together with $G_{p}(s)\geq p(0)+p(1)s$, this shows that

$G_{p}(\eta(p^{\circ}))\geq p(0)+\frac{p(1)^{2}}{\lambda}.$

The above inequality substituted into (2.5) implies (2.9). ∎

The following result provides a more accurate upper bound of $\zeta_{\rm
CM}(p)$ based on $\lambda,p(0),p(1),p(2)$. Similar techniques may be applied
to derive more accurate upper bounds when a larger collection of low values of
the the probability mass function of $p$ are known.

######  Proposition 2.14.

For any probability distribution $p$ on $\mathbb{Z}_{+}$ with a finite nonzero
mean $\lambda$,

$\zeta_{\rm CM}(p)\ \leq\ 1-p(0)-p(1)a-p(2)a^{2}$ (2.10)

where $a=\frac{p(1)}{\lambda-2p(2)}$.

###### Proof.

Observe that $G_{p^{\circ}}(s)\geq p^{\circ}(0)+p^{\circ}(1)s$ implies

$\eta(p^{\circ})\ =\ G_{p^{\circ}}(\eta(p^{\circ}))\ \geq\
p^{\circ}(0)+p^{\circ}(1)\eta(p^{\circ}),$

so that

$\eta(p^{\circ})\ \geq\ \frac{p^{\circ}(0)}{1-p^{\circ}(1)}\ =\
\frac{\lambda^{-1}p(1)}{1-2\lambda^{-1}p(2)}\ =\ a.$

Then by (2.5) and the monotonicity of $G_{p}$ we find that

$\zeta_{\rm CM}(p)\ =\ 1-G_{p}(\eta(p^{\circ}))\ \leq\ 1-G_{p}(a).$

Hence the claim follows by $G_{p}(a)\geq p(0)+p(1)a+p(2)a^{2}$. ∎

###  2.5 Thinning

The study of percolation and epidemics on random graphs requires the analysis
of thinned degree distributions (see Section 4.3). The _$r$ -thinning_ of a
probability distribution $p$ on $\mathbb{Z}_{+}$ with $r\in[0,1]$ is the
probability distribution $T_{r}p$ on $\mathbb{Z}_{+}$ with probability mass
function

$T_{r}p(k)\ =\ \sum_{\ell\geq k}p(\ell)\binom{\ell}{k}r^{k}(1-r)^{\ell-k}$

and generating function

$G_{T_{r}p}(s)\ =\ G_{p}\circ G_{\operatorname{Ber}(r)}(s)\ =\ G_{p}(1-r+rs).$

The $r$-thinning of $p$ can be recognized as a mixed binomial distribution of
a random integer $X_{r}$ corresponding to a random vector $(X_{r},X)$ where
$X$ is $p$-distributed and the conditional distribution of $X_{r}$ given $X=n$
is $\operatorname{Bin}(n,r)$. Alternatively, if
$X,\theta_{1},\theta_{2},\dots$ are mutually independent and such that $X$ is
$p$-distributed and $\theta_{i}$ is $\operatorname{Ber}(r)$-distributed, then
$X_{r}=\sum_{i=1}^{X}\theta_{i}$ is distributed according to the $r$-thinning
of $p$.

######  Example 2.15.

The $r$-thinnings of Dirac, binomial, and Poisson distributions are given by
$T_{r}(\delta_{n})=\operatorname{Bin}(n,r)$,
$T_{r}(\operatorname{Bin}(n,\alpha))=\operatorname{Bin}(n,\alpha r)$, and
$T_{r}(\operatorname{Poi}(\lambda))=\operatorname{Poi}(\lambda r)$.

######  Lemma 2.16.

The downshifted size biasing and $r$-thinning operations commute according to
$(T_{r}p)^{\circ}=T_{r}(p^{\circ})$.

###### Proof.

Because $G_{\operatorname{Ber}(r)}^{\prime}(s)=\frac{d}{ds}(1-r+rs)=r$, we
find that

$G_{T_{r}p}^{\prime}(s)=G_{p}^{\prime}(G_{\operatorname{Ber}(r)}(s))\,r.$

Using this formula together with (2.3) and $m(T_{r}p)=rm_{1}(p)$, we see that

$G_{(T_{r}p)^{\circ}}(s)=\frac{G_{T_{r}p}^{\prime}(s)}{m(T_{r}p)}=\frac{G_{p}^{\prime}(G_{\operatorname{Ber}(r)}(s))\,r}{rm_{1}(p)}=\frac{G_{p}^{\prime}(G_{\operatorname{Ber}(r)}(s))}{m_{1}(p)},$

and from this we may conclude that

$G_{(T_{r}p)^{\circ}}(s)=G_{p^{\circ}}(G_{\operatorname{Ber}(r)}(s))=G_{T_{r}(p^{\circ})}(s).$

∎

##  3 Stochastic ordering of branching processes

###  3.1 Strong and convex stochastic orders

The upper bound of $\zeta_{\rm CM}(p)$ obtained in Proposition 2.13 is rough
as it disregards information about the tail characteristics of $p$. To obtain
better estimates, we will develop in this section techniques based on the
theory of stochastic orders (see [MS02] or [SS07] for comprehensive surveys).

Integral stochastic orderings between probability distributions on
$\mathbb{R}$ (or a subset thereof) are defined by requiring

$\int\phi(x)\mu(dx)\leq\int\phi(x)\nu(dx)$ (3.1)

to hold for all functions $\phi:\mathbb{R}\to\mathbb{R}$ in a certain class of
functions such that both integrals above exist. The _strong stochastic order_
is defined by denoting $\mu\leq_{\rm{st}}\nu$ if (3.1) holds for all
increasing functions $\phi$. The _convex stochastic order_ (resp. concave,
increasing convex, increasing concave) order is defined by denoting
$\mu\leq_{\rm{cx}}\nu$ (resp. $\mu\leq_{\rm{cv}}\nu$, $\mu\leq_{\rm{icx}}\nu$
$\mu\leq_{\rm{icv}}\nu$) if (3.1) holds for all convex (resp. concave,
increasing convex, increasing concave) functions $\phi$. For random numbers
$X$ and $Y$ distributed according to $\mu$ and $\nu$, we denote
$X\leq_{\rm{st}}Y$ if $\mu\leq_{\rm{st}}\nu$, and similarly for other integral
stochastic orders.

When $X\leq_{\rm{st}}Y$ we say that $X$ is smaller than $Y$ in the strong
order because then $\mathbb{P}(X>t)\leq\mathbb{P}(Y>t)$ for all $t$. When
$X\leq_{\rm{cx}}Y$ we say that $X$ is less variable than $Y$ in the convex
order, because then $\mathbb{E}X=\mathbb{E}Y$ and
$\operatorname{Var}(X)\leq\operatorname{Var}(Y)$ whenever the second moments
exist. Note that $X\leq_{\rm{cv}}Y$ if and only if $X\geq_{\rm{cx}}Y$, that
is, $X$ is less concentrated than $Y$. The order $X\leq_{\rm{icv}}Y$ can be
interpreted by saying that $X$ is smaller and less concentrated than $Y$.

###  3.2 Stochastic ordering and branching processes

To obtain sharp results for branching processes, it is useful to introduce one
more integral stochastic order. For probability distributions $\mu$ and $\nu$
on $\mathbb{R}_{+}$ (or a subset thereof), the _Laplace transform order_ is
defined by denoting $\mu\leq_{\rm{Lt}}\nu$ if (3.1) holds for all functions
$\phi$ of the form $\phi(x)=-e^{-tx}$ with $t\geq 0$. Observe that
$\mu\leq_{\rm{Lt}}\nu$ is equivalent to requiring $L_{\mu}(t)\geq L_{\nu}(t)$
for all $t\geq 0$, where we denote the Laplace transform of $\mu$ by
$L_{\mu}(t)=\int e^{-tx}\mu(dx).$ For probability distributions $p$ and $q$ on
$\mathbb{Z}_{+}$, observe that $p\leq_{\rm{Lt}}q$ if and only if their
generating functions are ordered by $G_{p}(s)\geq G_{q}(s)$ for all
$s\in[0,1]$. Because for any $t\geq 0$, the function $x\mapsto-e^{-tx}$ is
increasing and concave, it follows that

$\mu\leq_{\rm{st}}\nu\implies\mu\leq_{\rm{icv}}\nu\implies\mu\leq_{\rm{Lt}}\nu.$

Due to the above implications we may interpret $X\leq_{\rm{Lt}}Y$ as $X$ being
smaller and less concentrated than $Y$ (in a weaker sense than
$X\leq_{\rm{icv}}Y$).

The following elementary result confirms an intuitive fact that a branching
population with a smaller and more variable offspring distribution is less
likely to survive in the long run. The proof can be obtained as a special case
of a slightly more general result below (Lemma 4.5).

######  Proposition 3.1.

When $p\leq_{\rm{Lt}}q$, the survival probabilities defined by (2.4) are
ordered according to $\zeta(p)\leq\zeta(q)$. Especially,

$p\leq_{\rm{st}}q\ \text{or}\ p\leq_{\rm{cv}}q\ \implies\ p\leq_{\rm{icv}}q\
\implies\ p\leq_{\rm{Lt}}q\ \implies\ \zeta(p)\leq\zeta(q).$

##  4 Stochastic ordering of the configuration model

Basic intuition about standard branching processes, as confirmed by
Proposition 3.1, suggests that a large configuration model with a smaller and
more variable degree distribution should have a smaller giant component. The
next subsection displays a counterexample where this intuitive reasoning
fails.

###  4.1 A counterexample

Consider degree distributions $p$ and $q$ defined by

$\displaystyle p$
$\displaystyle=\frac{1}{8}\delta_{1}+\frac{6}{8}\delta_{2}+\frac{1}{8}\delta_{3},$
$\displaystyle q$
$\displaystyle=\frac{1}{16}\delta_{0}+\frac{1}{8}\delta_{1}+\frac{5}{8}\delta_{2}+\frac{1}{8}\delta_{3}+\frac{1}{16}\delta_{4},$

where $\delta_{k}$ represents the Dirac point mass at point $k$. Their
downshifted size biasings, computed using (2.2), are given by

$\displaystyle p^{\circ}$
$\displaystyle=\frac{1}{16}\delta_{0}+\frac{12}{16}\delta_{1}+\frac{3}{16}\delta_{2},$
$\displaystyle q^{\circ}$
$\displaystyle=\frac{1}{16}\delta_{0}+\frac{10}{16}\delta_{1}+\frac{3}{16}\delta_{2}+\frac{2}{16}\delta_{3}.$

By comparing integrals of cumulative distributions functions [SS07, Thm 3.A.1]
or by constructing a martingale coupling [LV14], it is not hard to verify that
in this case $p\leq_{\rm{cx}}q$. Numerically computed values for the
associated means, variances, and extinction probabilities are listed in Table
1.

| $p$ | $q$ | $p^{\circ}$ | $q^{\circ}$
---|---|---|---|---
mean | 2.000 | 2.000 | 1.125 | 1.375
variance | 0.250 | 0.750 | 0.234 | 0.609
extinction probability $\eta$ | 0.000 | 0.076 | 0.333 | 0.186
Table 1: Statistical indices associated to $p$ and $q$ and their downshifted
size biasings.

By evaluating the associated generating functions at $\eta(p^{\circ})=0.333$
and $\eta(q^{\circ})=0.186$, we find using (2.5) that $\zeta_{\rm
CM}(p)=0.870$ and $\zeta_{\rm CM}(q)=0.892$.

This example shows that a standard branching process with a less variable
offspring distribution ($p\leq_{\rm{cx}}q$) is less likely to go extinct
($\eta(p)<\eta(q)$), but the same is not true for the downshifted size-biased
offspring distributions ($\eta(p^{\circ})>\eta(q^{\circ}))$. As a consequence,
the giant component of a large random graph corresponding to a configuration
model with limiting degree distribution $p$ is with high probability smaller
than the giant component in a similar model with limiting degree distribution
$q$, even though $p$ is less variable than $q$. The reason for this is that,
even though higher variability has an unfavorable effect on standard branching
(the immediate neighborhood of the root note), higher variability also causes
the neighbors of a neighbor to have bigger degrees on average.

###  4.2 A monotonicity result when one extinction probability is small

The following result shows that increasing the variability of a degree
distribution $p$ _does_ decrease the limiting relative size of a giant
component, under the extra conditions that $p(0)=q(0)$ and that the extinction
probability related to $q^{\circ}$ is less than $e^{-2}\approx 0.135$. Note
that in the analysis of configuration models it is often natural to assume
that $p(0)=q(0)$ because nodes without any half-links have no effect on large
components.

######  Theorem 4.1.

Assume that $p\leq_{\rm{icv}}q$, $p(0)=q(0)$, and $\eta(q^{\circ})\leq
e^{-2}$. Then $\zeta_{\rm CM}(p)\leq\zeta_{\rm CM}(q)$.

######  Remark 4.2.

Assume that $q(1)>0$ and that $\zeta_{\rm CM}(q)\geq 1-q(0)-q(1)e^{-2}$. If
this holds, then the inequality $G_{q}(s)\geq q(0)+q(1)s$ applied to
$s=\eta(q^{\circ})$ implies that

$q(0)+q(1)e^{-2}\geq 1-\zeta_{\rm CM}(q)=G_{q}(\eta(q^{\circ}))\geq
q(0)+q(1)\eta(q^{\circ}),$

so that $\eta(q^{\circ})\leq e^{-2}$ as required in Theorem 4.1.

Theorem 4.1 is a direct consequence (choose $\ell=0$ below) of the following
slightly more general result.

######  Theorem 4.3.

Assume that $p\leq_{\rm{icv}}q$, $p(i)=q(i)$ for all
$i\in\\{0,1,2,...,\ell\\}$ and $\eta(q^{\circ})\leq e^{-2/(\ell+1)}$ for some
integer $\ell\geq 0$. Then $\zeta_{\rm CM}(p)\leq\zeta_{\rm CM}(q)$.

The proof of Theorem 4.3 is based on the following two lemmas.

######  Lemma 4.4.

If $p\leq_{\rm{icv}}q$ and $p(i)=q(i)$ for all $i\in\\{0,1,2,...,\ell\\}$,
then the generating functions of the downshifted size biasings of $p$ and $q$
are ordered by

$G_{p^{\circ}}(s)\geq G_{q^{\circ}}(s)\quad\text{for all
$s\in[0,e^{-2/(\ell+1)}]$}.$

###### Proof.

Fix $s\in(0,e^{-2/(\ell+1)}]$. Define a function
$\phi_{s}:\mathbb{R}_{+}\to\mathbb{R}_{+}$ by

$\phi_{s}(x)=xs^{x}.$

Denote $t=-\log s$, so that $t\in[2,\infty)$. Because
$\phi_{s}^{\prime}(x)=(1-tx)e^{-tx}$ and
$\phi_{s}^{\prime\prime}(x)=(tx-2)te^{-tx}$, we find that $\phi_{s}$ is
decreasing on $[\frac{1}{-\log s},\infty)$ and convex on $[\frac{2}{-\log
s},\infty)$. Because $-\log s\geq\frac{2}{\ell+1}$, it follows that $\phi_{s}$
is decreasing and convex on $[\ell+1,\infty).$ Define a decreasing convex
function by

$\displaystyle\psi_{s}(x)=f_{s}(x)1_{[0,x_{0})}+\phi_{s}(x)1_{[x_{0},\infty)}(x)$
(4.1)

where $f_{s}(x)=\phi_{s}(x_{0})+\phi_{s}^{\prime}(x_{0})(x-x_{0})$ and
$x_{0}=\ell+1$ (see Figure 1).

Let $X$ and $Y$ be random integers distributed according to $p$ and $q$. By
assumption $p\leq_{\rm{icv}}q$,

$\mathbb{E}\big{(}\psi_{s}(X)\big{)}\geq\mathbb{E}\big{(}\psi_{s}(Y)\big{)}.$

By the second assumption $p(i)=q(i)$ for all $i\in\\{0,1,2,...,\ell\\}$, the
above inequality can also be written as

$\sum_{i=\ell+1}^{\infty}\psi_{s}(i)p(i)\geq\sum_{i=\ell+1}^{\infty}\psi_{s}(i)q(i),$

and hence by (4.1) we find that

$\sum_{i=\ell+1}^{\infty}\phi_{s}(i)p(i)\geq\sum_{i=\ell+1}^{\infty}\phi_{s}(i)q(i).$

By applying again the second assumption we obtain

$\mathbb{E}\big{(}\phi_{s}(X)\big{)}\geq\mathbb{E}\big{(}\phi_{s}(Y)\big{)},$

which implies $G_{p}^{\prime}(s)\geq G_{q}^{\prime}(s).$ Because
$p\leq_{\rm{icv}}q$ also implies $\mathbb{E}(X)\leq\mathbb{E}(Y)$, we see by
(2.3) that

$\displaystyle
G_{p^{*}}(s)=\frac{G_{p}^{\prime}(s)}{\mathbb{E}(X)}\geq\frac{G_{q}^{\prime}(s)}{\mathbb{E}(Y)}=G_{q^{*}}(s).$
(4.2)

Dividing both sides of (4.2) by $s$, we obtain

$G_{p^{\circ}}(s)=\frac{G_{p^{*}}(s)}{s}\geq\frac{G_{q^{*}}(s)}{s}=G_{q^{\circ}}(s).$

Hence the claim is true for all $s\in(0,e^{-2/(\ell+1)}]$. By the continuity
of $G_{p^{\circ}}$ and $G_{q^{\circ}}$, the claim is also true for $s=0$. ∎

Figure 1:  Function $\phi_{s}$ (blue) and its convex modification $\psi_{s}$
(red) for $t=3$.

######  Lemma 4.5.

If $G_{p}(s)\geq G_{q}(s)$ for all $s\in[0,\eta(q)]$, then
$\eta(p)\geq\eta(q)$.

###### Proof.

The claim is trivial for $\eta(q)=0$, so let us assume that $\eta(q)>0$. Then
$G_{q}(0)>0$, and the continuity of $s\mapsto G_{q}(s)-s$ implies that
$G_{q}(s)>s$ for all $s\in[0,\eta(q))$. Hence also

$G_{p}(s)\geq G_{q}(s)>s$

for all $s\in[0,\eta(q))$. This shows that $G_{p}$ has no fixed points in
$[0,\eta(q))$ and therefore $\eta(p)$, the smallest fixed point of $G_{p}$ in
$[0,1]$, must be greater than or equal to $\eta(q)$. ∎

###### Proof of Theorem 4.3.

By applying Lemma 4.4 we see that

$G_{p^{\circ}}(s)\geq G_{q^{\circ}}(s)$ (4.3)

for all $s\in[0,e^{-2/(\ell+1)}]$. The assumption $\eta(q^{\circ})\leq
e^{-2/(\ell+1)}$ further guarantees that (4.3) is true for all
$s\in[0,\eta(q^{\circ})]$. Lemma 4.5 then shows that
$\eta(p^{\circ})\geq\eta(q^{\circ})$. Finally, $p\leq_{\rm{icv}}q$ implies
$p\leq_{\rm{Lt}}q$, so that $G_{p}(s)\geq G_{q}(s)$ for all $s\in[0,1]$.
Therefore, the monotonicity of $G_{p}$ implies that

$G_{p}(\eta(p^{\circ}))\geq G_{p}(\eta(q^{\circ}))\geq
G_{q}(\eta(q^{\circ})).$

By substituting the above inequality into (2.5), we obtain Theorem 4.3. ∎

###  4.3 Application: Social network modeling

Consider a large online social network of mean degree $\lambda_{0}$ where
users forward copies of messages to their neighbors independently of each
other with probability $r_{0}$. Without any a priori information about the
higher order statistics of the degree distribution, one might choose to model
the network using a configuration model with some degree distribution which is
similar to one observed in some known social network. Because several well-
studied social networks data exhibit a power-law tail in their degree data, a
natural first choice is to model the unknown network using a configuration
model with a Pareto-mixed Poisson limiting degree distribution (see Example
2.5)

$p_{0}=\operatorname{MPoi}(\operatorname{Par}(\alpha,c_{0}))$ (4.4)

with shape $\alpha>1$, scale $c_{0}=\lambda_{0}(1-1/\alpha)$, and mean
$\lambda_{0}$.

Because the above choice of degree distribution was made without regard to
network data, it is important to try to analyze how big impact can a wrong
choice make to key network characteristics. When interested in global effects
on information spreading, it is natural to consider the epidemic generated
graph obtained by deleting stubs of the initial configuration model
independently with probability $1-r_{0}$. The outcome corresponds to another
configuration model where the limiting degree $p=T_{r_{0}}p_{0}$ is the
$r_{0}$-thinning of $p_{0}$ defined in Section 2.5. Using generating functions
one may verify that the $r$-thinning of a $\mu$-mixed Poisson distribution
$\operatorname{MPoi}(\mu)$ equals $\operatorname{MPoi}(r\mu)$, where $r\mu$
denotes the distribution of a $\mu$-distributed random number multiplied by
$r\in[0,1]$. Because
$r\operatorname{Par}(\alpha,c)=\operatorname{Par}(\alpha,rc)$, it follows that
the Pareto-mixed Poisson distribution is scale-free in the sense that

$T_{r}\operatorname{MPoi}(\operatorname{Par}(\alpha,c))=\operatorname{MPoi}(\operatorname{Par}(\alpha,rc)).$

See [ALW14] for an insightful discussion on scale-free properties of discrete
probability distributions. As a consequence, the $r_{0}$-thinning of $p_{0}$
in (4.4) equals

$p=\operatorname{MPoi}(\operatorname{Par}(\alpha,\lambda(1-1/\alpha)))$ (4.5)

with $\lambda=\lambda_{0}r_{0}$.

Now the key quantity describing the information spreading dynamics of the
social network model is given by $\zeta_{\rm CM}(p)$ defined in (2.5). To
study how sensitive this functional is to the variability of $p$, we have
numerically evaluated $\zeta_{\rm CM}(p)$ for different values of $\alpha$ and
$\lambda$, see Fig. 2. An extreme case is obtained by letting
$\alpha\to\infty$ which leads to the standard Poisson distribution with mean
$\lambda$. Again, perhaps a bit surprisingly, we see that for small values of
$\lambda$, a Pareto-mixed Poisson as a limiting degree distribution may
produce an asymptotically larger maximally connected component in a
configuration model than a one with a less variable unmixed Poisson
distribution with the same mean. This phenomenon is most clearly visible when
$\lambda=0.9$, in which case $\zeta_{\rm
CM}(\operatorname{Poi}(\lambda))=\zeta(\operatorname{Poi}(\lambda))=0$ but a
Pareto-mixed Poisson degree distribution with a heavy enough tail yields
nonzero values of $\zeta_{\rm CM}$, as shown by the magenta curve in Fig. 2.
For sufficiently large values of $\lambda$, this phenomenon appears not to
take place.

Figure 2:  Configuration model branching functional $\zeta_{\rm
CM}(p_{\alpha})$ for a collection of Pareto-mixed Poisson degree distributions
with mean $\lambda$, plotted as a function of the shape parameter $\alpha>1$.

Proving the monotonicity of $\zeta_{\rm CM}(p)$ for Pareto-mixed Poisson
distributions of the form (4.5) is not directly possible using Theorem 4.1
because $p(0)$ is not constant with respect to the shape parameter $\alpha$.
However, the following result can be applied here. Let us define a constant

$\lambda_{\rm cr}=\inf\\{\lambda\geq
0:\lambda\zeta(\operatorname{Poi}(\lambda))=2\\}.$

Because $\lambda\mapsto\lambda\zeta(\operatorname{Poi}(\lambda))$ is
increasing (Proposition 3.1) and continuous (Lemma 2.11) and grows from zero
to infinity as $\lambda$ ranges from zero to infinity, it follows that
$\lambda_{\rm cr}\in(2,\infty)$ is well defined. Numerical computations
indicate that $\lambda_{\rm cr}\approx 2.3$. The following result establishes
a monotonicity result for the configuration model with a Pareto-mixed Poisson
limiting distribution $p_{\alpha}=\operatorname{MPoi}(\mu_{\alpha})$ with
$\mu_{\alpha}=\operatorname{Par}(\alpha,c_{\alpha})$, where the scale
$c_{\alpha}=\lambda(1-1/\alpha)$ is chosen so that the mean of $p_{\alpha}$
equals $\lambda$ for all $\alpha>0$ (see Examples 2.3 and 2.5).

######  Theorem 4.6.

For any $\lambda>\lambda_{\rm cr}$ there exists a constant $\alpha_{\rm cr}>1$
such that

$\zeta_{\rm CM}(p_{\alpha})\leq\zeta_{\rm CM}(p_{\beta})\leq\zeta_{\rm
CM}(\operatorname{Poi}(\lambda))$

for all $\alpha_{\rm cr}\leq\alpha\leq\beta$.

######  Remark 4.7.

Note that $\zeta_{\rm
CM}(\operatorname{Poi}(\lambda))=\zeta(\operatorname{Poi}(\lambda))$ due to
the fact that the Poisson distribution is invariant to downshifted size
biasing (cf. Example 2.5).

###### Proof.

Fix $\lambda>\lambda_{\rm cr}$ and denote
$\eta_{\infty}=\eta(\operatorname{Poi}(\lambda))$. Because
$\lambda>\lambda_{\rm cr}$, it follows that $\lambda(1-\eta_{\infty})>2$, and
therefore

$\lambda(1-\eta_{\infty})\geq\frac{2}{1-1/\alpha_{0}}+\lambda\epsilon$ (4.6)

for some large enough $\alpha_{0}>1$ and small enough $\epsilon>0$. Next,
Lemma 4.9 below shows that
$\mu_{\alpha}^{*}=\operatorname{Par}(\alpha-1,c_{\alpha})\to\delta_{\lambda}$
and hence also
$p_{\alpha}^{\circ}=\operatorname{MPoi}(\mu_{\alpha}^{*})\to\operatorname{Poi}(\lambda)$
in distribution as $\alpha\to\infty$. The continuity of the standard branching
functional (Lemma 2.11) implies that
$\eta(p_{\alpha}^{\circ})\to\eta_{\infty}$, and we may choose a constant
$\alpha_{\rm cr}\geq\alpha_{0}$ such that
$\eta(p_{\alpha}^{\circ})\leq\eta_{\infty}+\epsilon$ for all
$\alpha\geq\alpha_{\rm cr}$.

Assume now that $\alpha_{\rm cr}\leq\alpha\leq\beta$. Then by Lemma B.1 we
know that

$\mu_{\alpha}\leq_{\rm{cv}}\mu_{\beta}\leq_{\rm{cv}}\delta_{\lambda}.$ (4.7)

Furthermore, $c_{\alpha_{0}}\leq c_{\alpha}\leq c_{\beta}$ implies that the
supports of $\mu_{\alpha}$, $\mu_{\beta}$, and $\delta_{\lambda}$ are
contained in $[c_{\alpha_{0}},\infty)$. Lemma 4.8 below implies that
$G_{p_{\alpha}^{\circ}}(s)\geq G_{p_{\beta}^{\circ}}(s)\geq
G_{\operatorname{Poi}(\lambda)}$ for all $s\in[0,s_{0}]$ where
$s_{0}=1-2/c_{\alpha_{0}}$. Now (4.6) shows that

$s_{0}=1-\lambda^{-1}\left(\frac{2}{1-1/\alpha_{0}}\right)\geq
1-\lambda^{-1}\left(\lambda(1-\eta_{\infty})-\lambda\epsilon\right)=\eta_{\infty}+\epsilon,$

and hence the interval $[0,s_{0}]$ contains both $[0,\eta_{\infty}]$ and
$[0,\eta(p_{\beta}^{\circ})]$. By applying Lemma 4.5 twice, it follows that
$\eta(p_{\alpha}^{\circ})\geq\eta(p_{\beta}^{\circ})\geq\eta(\operatorname{Poi}(\lambda))=\eta_{\infty}$.

On the other hand, inequality (4.7) together with [SS07, Thm 8.A.14] implies
that
$\operatorname{MPoi}(\mu_{\alpha})\leq_{\rm{icv}}\operatorname{MPoi}(\mu_{\beta})\leq_{\rm{icv}}\operatorname{Poi}(\lambda)$.
Especially,
$p_{\alpha}\leq_{\rm{Lt}}p_{\beta}\leq_{\rm{Lt}}\operatorname{Poi}(\lambda)$,
so that $G_{p_{\alpha}}\geq G_{p_{\beta}}\geq G_{\operatorname{Poi}(\lambda)}$
pointwise on $[0,1]$. This together with the monotonicity of the generating
functions shows that

$G_{p_{\alpha}}(\eta(p_{\alpha}^{\circ}))\geq
G_{p_{\beta}}(\eta(p_{\beta}^{\circ}))\geq
G_{\operatorname{Poi}(\lambda)}(\eta(\operatorname{Poi}(\lambda))),$

and the claim follows by substituting the above inequalities into (2.5). ∎

######  Lemma 4.8.

Let $p=\operatorname{MPoi}(\mu)$ and $q=\operatorname{MPoi}(\nu)$ where
$\mu\leq_{\rm{icv}}\nu$. Assume that the supports of $\mu$ and $\nu$ are
contained in an interval $[c,\infty)$ for some $c\geq 2$. Then
$G_{p^{\circ}}(s)\geq G_{q^{\circ}}(s)$ for all $s\in[0,1-2/c]$.

###### Proof.

Note first that for $G_{\operatorname{MPoi}(\mu)}(s)=L_{\mu}(1-s)$ and recall
from Example 2.5 that
$\operatorname{MPoi}(\mu)^{\circ}=\operatorname{MPoi}(\mu^{*})$. Hence
$G_{p^{\circ}}(s)=L_{\mu^{*}}(1-s)$. Fix $s\in[0,1-2/c]$ and note that
$G_{p^{\circ}}(s)=m_{1}(\mu)^{-1}\int\phi_{s}(x)\,\mu(dx)$, where
$\phi_{s}(x)=xe^{-(1-s)x}$. Because
$\phi_{s}^{\prime}(x)=(1-(1-s)x)e^{-(1-s)x}$ and
$\phi^{\prime\prime}_{s}(x)=(1-s)((1-s)x-2)e^{-(1-s)x}$, it follows that the
function $\phi_{s}$ is decreasing on $[\frac{1}{1-s},\infty)$ and convex on
$[\frac{2}{1-s},\infty)$. Because $s\in[0,1-2/c]$, it follows that $\phi_{s}$
is decreasing and convex on the support of $\mu_{i}$ for both $i=1,2$.
Therefore $\mu\leq_{\rm{icv}}\nu$ implies
$\int\phi_{s}d\mu\geq\int\phi_{s}d\nu$. Because $\mu\leq_{\rm{icv}}\nu$ also
implies that the first moments are ordered according to $m_{1}(\mu)\leq
m_{1}(\nu)$, we conclude that

$G_{p^{\circ}}(s)\ =\ m_{1}(\mu)^{-1}\int\phi_{s}\,d\mu\ \geq\
m_{1}(\nu)^{-1}\int\phi_{s}\,d\nu\ =\ G_{q^{\circ}}(s).$

∎

######  Lemma 4.9.

If $c_{\alpha}\to\lambda\geq 0$ as $\alpha\to\infty$, then
$\operatorname{Par}(\alpha,c_{\alpha})\to\delta_{\lambda}$.

###### Proof.

Let $U$ be a uniformly distributed random number in $(0,1)$. Then
$X_{\alpha}=c_{\alpha}(1-U)^{-1/\alpha}$ has
$\operatorname{Par}(\alpha,c_{\alpha})$ distribution for all $\alpha$. Because
$c_{\alpha}\to\lambda$ and $(1-U)^{-1/\alpha}\to 1$, it follows that
$X_{\alpha}\to\lambda$ almost surely, and hence also in distribution. ∎

###  4.4 Numerical experiments

After a detailed analysis of the configuration model branching functional for
Pareto-mixed Poisson degree distributions, a natural question to ask is
whether or not similar observations remain valid or other types of
distributions as well. We studied this question by performing numerical
experiments on two classes of distributions: lognormally mixed Poisson
distributions and binomial distributions.

In Figure 3 we have plotted numerically evaluated values of $\zeta_{\rm
CM}(p)$ where $p=\operatorname{MPoi}(\operatorname{LNor}(b,\sigma^{2}))$ is a
lognormally mixed Poisson distribution with scale $\sigma^{2}>0$ and location
$b=\log\lambda-\sigma^{2}/2$ chosen so that the mean of $p$ equals $\lambda>0$
(see Example 2.4). The curves are plotted as functions of $1/\sigma^{2}$, so
that variability decreases along the horizontal axis. The behavior of the
branching functional is the qualitatively the same as for the Pareto-mixed
case: for network models with a small mean degree, higher variability may
dramatically increase the size of the largest component.

Figure 3:  Configuration model branching functional $\zeta_{\rm CM}$ for a
collection of lognormally mixed Poisson distributions with mean $\lambda$,
plotted as a function of $1/\sigma^{2}>0$.

In Figure 4 we have plotted numerically evaluated values of $\zeta_{\rm
CM}(p)$ where $p=\operatorname{Bin}(n,\lambda/n)$ is a binomial distribution
with mean $\lambda$, parameterized by $n\geq 3$. The variance of $p$ equals
$\lambda(1-\lambda/n)$ and increases towards $\lambda$ along the horizontal
axis. Also in this case with a light-tailed degree distribution, the overall
qualitative picture is the same as for the Pareto and lognormally mixed
Poisson distributions. The one difference is that all curves in Figure 4
appear to be monotone, either increasing (for small mean degree) or decreasing
(for large mean degree). In addition, in this case the values of $\lambda\leq
1$ always produce $\zeta_{\rm CM}(p)=0$, because the downshifted size biasing
of $\operatorname{Bin}(n,\lambda/n)$ equals
$\operatorname{Bin}(n-1,\lambda/n)$ and has mean $\lambda(1-1/n)\leq 1$
whenever $\lambda\leq 1$.

Figure 4:  Configuration model branching functional $p\mapsto\zeta_{\rm
CM}(p)$ for a collection of binomial degree distributions with mean $\lambda$,
plotted as a function of $n\geq 3$.

##  5 Conclusions

In this paper we studied the effect of degree variability to the global
connectivity properties of large network models. The analysis was restricted
to the configuration model and the associated uniform random graph with a
given limiting degree distribution. Counterexamples were discovered both for a
bounded support and power-law case that described that due to size biasing
effects, increased degree variability may sometimes have a favorable effect on
the size of the giant component, in sharp contrast to standard branching
processes. We also proved using rigorous mathematical arguments that for some
instances of strongly supercritical networks the increased degree variability
has a negative effect on the global connectivity. Numerical experiments
illustrate that these observations can be detected for both light-tailed and
heavy-tailed degree distributions.

### Acknowledgements

This research was financially supported by the Emil Aaltonen Foundation.

##  Appendix A A continuity property of branching processes

###### Proof of Lemma 2.11.

We denote $\eta=\eta(p)$ and $\eta_{n}=\eta(p_{n})$. We also denote
$G(t)=G_{p}(t)$ and $G_{n}(t)=G_{p_{n}}(t)$. Observe first that

$|G_{n}(t)-G(t)|\ \leq\ \sum_{k=0}^{\infty}t^{k}|p_{n}(k)-p(k)|\ \leq\
2d_{\rm{tv}}(p_{n},p).$

for all $t\in[0,1]$, where $d_{\rm{tv}}$ refers to the total variation
distance. Because convergence in total variation and convergence in
distribution are equivalent on countable spaces, it follows that

$||G_{n}-G||=\sup_{t\in[0,1]}|G_{n}(t)-G(t)|\to 0.$ (A.1)

(i) Consider first the case where $\eta(p)\in(0,1)$. Then $p(0)+p(1)<1$. Hence
$p(k)>0$ for some $k\geq 2$, and this shows that

$G^{\prime\prime}(t)=\sum_{k=2}^{\infty}p(k)k(k-1)t^{k-2}>0$

for all $t\in(0,1)$. Note that by the continuity of $G(t)-t$, we see that

$G(t)>t\quad\text{for all $t\in[0,\eta)$}.$ (A.2)

We will next show that

$G(t)<t\quad\text{for all $t\in(\eta,1)$}.$ (A.3)

Assume, on the contrary, that $G(\eta^{\prime})\geq\eta^{\prime}$ for some
$\eta^{\prime}\in(\eta,1)$. Then indeed $G(\eta^{\prime})=\eta^{\prime}$,
because by the convexity of $G$, the point $(\eta^{\prime},G(\eta^{\prime}))$
must lie below the line connecting the points $(\eta,G(\eta))=(\eta,\eta)$ and
$(1,G(1))=(1,1)$. But then the points
$(\eta,G(\eta),(\eta^{\prime},G(\eta^{\prime})),(1,G(1))$ all lie on the
straight line between $(\eta,\eta)$ and $(1,1)$, and the convexity $G$ implies
that $G(t)=t$ on $[\eta,1]$. This contradicts the fact that
$G^{\prime\prime}(t)>0$ on $(\eta,1)$. Hence we conclude that (A.3) is valid.

Next fix any $\epsilon>0$ such that
$(\eta-\epsilon,\eta+\epsilon)\subset(0,1)$. Then (A.2) and the continuity of
$G(t)-t$ imply that $\delta_{1}:=\inf_{t\in[0,\eta-\epsilon]}(G(t)-t)>0$. On
the other hand (A.3) implies that
$\delta_{2}:=(\eta+\epsilon)-G(\eta+\epsilon)>0$. By (A.1) we may fix $n_{0}$
such that $||G_{n}-G||\leq\min(\delta_{1},\delta_{2})/2$ for all $n\geq
n_{0}$. Then for any $n\geq n_{0}$, we find that $G_{n}(t)-t\geq\delta_{1}/2$
on $[0,\eta-\epsilon]$ and $G_{n}(\eta+\epsilon)\leq
G(\eta+\epsilon)+||G_{n}-G||\leq(\eta+\epsilon)-\delta_{2}/2$. Hence
$G_{n}(t)>t$ on $[0,\eta-\epsilon]$ and $G_{n}(t)<t$ for $t=\eta+\epsilon$. By
the continuity of $G_{n}$, we conclude that $G_{n}$ has no fixed points in
$[0,\eta-\epsilon]$ and at least one fixed point in
$(\eta-\epsilon,\eta+\epsilon)$. Therefore the smallest nonzero fixed point of
$G_{n}$ satisfies $\eta_{n}\in(\eta-\epsilon,\eta+\epsilon)$ for all $n\geq
n_{0}$.

(ii) Consider next the case with $\eta=1$. Then $G(0)>0$ and the continuity of
$G$ imply that $G(t)>t$ on the interval $(0,1)$. Especially,
$\delta=\inf_{t\in[0,1-\epsilon]}G(t)>0$ for any $\epsilon>0$. For any large
enough $n$ such that $||G_{n}-G||\leq\delta/2$, it follows that $G_{n}(t)\geq
G(t)-||G_{n}-G||\geq t+\delta/2$ for all $t\in[0,1-\epsilon]$. This shows that
$G_{n}$ has no fixed points in $[0,1-\epsilon]$, and hence
$\eta_{n}>1-\epsilon$ for all big enough $n$. ∎

##  Appendix B Stochastic ordering of Pareto distributions

The following result characterizes stochastic ordering properties of Pareto
distributions. For $i=1,2$, let $\mu_{i}=\operatorname{Par}(\alpha_{i},c_{i})$
be the Pareto distribution with shape $\alpha_{i}>1$, scale $c_{i}>0$, and
mean $\lambda_{i}=c_{i}(1-1/\alpha_{i})^{-1}$.

######  Theorem B.1.

For any Pareto distributions $\mu_{i}=\operatorname{Par}(\alpha_{i},c_{i})$
with shape $\alpha_{i}>1$, scale $c_{i}>0$, and mean
$\lambda_{i}=c_{i}(1-1/\alpha_{i})^{-1}$:

  1. (i)

$\mu_{1}\leq_{\rm{icx}}\mu_{2}$ if and only if $\lambda_{1}\leq\lambda_{2}$
and $\alpha_{1}\geq\alpha_{2}$.

  2. (ii)

$\mu_{1}\leq_{\rm{cx}}\mu_{2}$ if and only if $\lambda_{1}=\lambda_{2}$ and
$\alpha_{1}\geq\alpha_{2}$.

  3. (iii)

$\mu_{1}\leq_{\rm{icv}}\mu_{2}$ if and only if $\lambda_{1}\leq\lambda_{2}$
and $c_{1}\leq c_{2}$.

Result (i) above quantifies the intuitively natural property that a larger
mean and a heavier tail makes a Pareto distribution bigger and more variable
in the increasing convex order. Interestingly, result (iii) may be valid for
both $\alpha_{1}<\alpha_{2}$ and $\alpha_{1}>\alpha_{2}$, depending on the
value of the scale parameter.

###### Proof.

(i) Let $F_{i}^{-1}(s)=c_{i}(1-s)^{-1/\alpha_{i}}$ be the quantile function of
$\mu_{i}$, and denote the upper and lower integrated quantile functions of
$\mu_{i}$ by

$\displaystyle\bar{H}_{i}(t)$
$\displaystyle=\int_{t}^{1}F_{i}^{-1}(s)\,ds=\lambda_{i}(1-t)^{1-1/\alpha_{i}},$
$\displaystyle H_{i}(t)$
$\displaystyle=\int_{0}^{t}F_{i}^{-1}(s)\,ds=\lambda_{i}(1-(1-t)^{1-1/\alpha_{i}}).$

Now by [SS07, Thm 3.A.5, Thm 4.A.3] $\mu_{1}\leq_{\rm{icx}}\mu_{2}$ if and
only if $\bar{H}_{1}(t)\leq\bar{H}_{2}(t)$ for all $t\in(0,1)$, that is,

$\lambda_{1}(1-t)^{1-1/\alpha_{1}}\leq\lambda_{2}(1-t)^{1-1/\alpha_{2}}$ (B.1)

for all $t\in(0,1)$. If $\lambda_{1}\leq\lambda_{2}$ and
$\alpha_{1}\geq\alpha_{2}$, the the above inequality holds for all
$t~\in(0,1)$, and hence $\mu_{1}\leq_{\rm{icx}}\mu_{2}$.

Assume next that $\mu_{1}\leq_{\rm{icx}}\mu_{2}$. Then (B.1) is valid for all
$t\in(0,1)$. By letting $t\to 0$, it follows that
$\lambda_{1}\leq\lambda_{2}$. Inequality (B.1) also implies that the fraction

$\frac{(1-t)^{1-1/\alpha_{1}}}{(1-t)^{1-1/\alpha_{2}}}=(1-t)^{1/\alpha_{2}-1/\alpha_{1}}$

is bounded over $t\in(0,1)$. This is possible only if
$1/\alpha_{2}-1/\alpha_{1}\geq 0$, so we obtain $\alpha_{1}\geq\alpha_{2}$.

(ii) It is sufficient to note that $\mu_{1}\leq_{\rm{cx}}\mu_{2}$ if and only
if $\mu_{1}\leq_{\rm{icx}}\mu_{2}$ and $m(\mu_{1})=m(\mu_{2})$. The claim
hence follows from (i).

(iii) Recall [FS04, Thm 2.58] that $\mu_{1}\leq_{\rm{icv}}\mu_{2}$ if and only
if $H_{1}(t)\leq H_{2}(t)$ for all $t\in[0,1]$.

Assume now that $\mu_{1}\leq_{\rm{icv}}\mu_{2}$. Then $H_{1}(1)\leq H_{2}(1)$
implies $\lambda_{1}\leq\lambda_{2}$. Moreover, $H_{1}(0)=H_{2}(0)=0$ implies
that $t^{-1}(H_{1}(t)-H_{1}(0))\leq t^{-1}(H_{2}(t)-H_{2}(0))$ for all
$t\in(0,1)$, and by letting $t\to 0$, we get $c_{1}=H_{1}^{\prime}(0)\leq
H_{2}^{\prime}(0)=c_{2}$, so that $c_{1}\leq c_{2}$. (Note that this reasoning
indeed showed that $\mu_{1}\leq_{\rm{st}}\mu_{2}$ which automatically implies
$\mu_{1}\leq_{\rm{icv}}\mu_{2}$.)

To prove the other direction of the claim, let us next assume that
$\lambda_{1}\leq\lambda_{2}$ and $c_{1}\leq c_{2}$. Let us analyze separately
the cases $\alpha_{1}\geq\alpha_{2}$ and $\alpha_{1}\leq\alpha_{2}$.

  1. (a)

If $\alpha_{1}\geq\alpha_{2}$, then

$F_{1}^{-1}(s)=c_{1}(1-s)^{-1/\alpha_{1}}\leq
c_{2}(1-s)^{-1/\alpha_{2}}=F_{2}^{-1}(s)$

for all $s\in(0,1)$.

  2. (b)

If $\alpha_{1}\leq\alpha_{2}$, then $\lambda_{1}\leq\lambda_{2}$ shows that

$\frac{H_{2}(t)}{H_{1}(t)}=\left(\frac{\lambda_{2}}{\lambda_{1}}\right)\frac{1-(1-t)^{a_{2}}}{1-(1-t)^{a_{1}}}\geq\frac{1-(1-t)^{a_{2}}}{1-(1-t)^{a_{1}}},$

where $a_{i}=1-1/\alpha_{i}$. Now $\alpha_{1}\leq\alpha_{2}$ implies
$a_{1}\leq a_{2}$, Hence also $(1-t)^{a_{1}}~\geq(1-t)^{a_{2}}$, which shows
that $H_{2}(t)\geq H_{1}(t)$ for all $t\in(0,1)$.

∎

## References

  * [AGK15] Richard Arratia, Larry Goldstein, and Fred Kochman.  Size bias for one and all.  arXiv:1308.2729, June 2015.
  * [AGS08] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré.  Gradient flows in metric spaces and in the space of probability measures.  Lectures in Mathematics ETH Zürich. Birkhäuser, Basel, second edition, 2008.
  * [ALW14] Richard Arratia, Thomas M. Liggett, and Malcolm J. Williamson.  Scale-free and power law distributions via fixed points and convergence of (thinning and conditioning) transformations.  Electron. Commun. Probab., 19(39):1–10, 2014.
  * [BJR11] Béla Bollobás, Svante Janson, and Oliver Riordan.  Sparse random graphs with clustering.  Random Structures Algorithms, 38(3):269–323, 2011.
  * [BST14] Frank G. Ball, David J. Sirl, and Pieter Trapman.  Epidemics on random intersection graphs.  Ann. Appl. Probab., 24(3):1081–1128, 2014.
  * [BT12] Tom Britton and Pieter Trapman.  Maximizing the size of the giant.  J. Appl. Probab., 49(4):1156–1165, 2012.
  * [FS04] Hans Föllmer and Alexander Schied.  Stochastic Finance.  Walter de Gruyter & Co., 2nd edition, 2004.
  * [GS01] Geoffrey R. Grimmett and David R. Stirzaker.  Probability and Random Processes.  Oxford University Press, 3rd edition, 2001.
  * [JL09] Svante Janson and Malwina J. Luczak.  A new approach to the giant component problem.  Random Struct. Algor., 34(2):197–216, 2009.
  * [Kal02] Olav Kallenberg.  Foundations of Modern Probability.  Springer, second edition, 2002.
  * [LV13] Lasse Leskelä and Matti Vihola.  Stochastic order characterization of uniform integrability and tightness.  Statist. Probab. Lett., 83(1):382–389, 2013.
  * [LV14] Lasse Leskelä and Matti Vihola.  Conditional convex orders and measurable martingale couplings.  arXiv:1404.0999, April 2014.
  * [MR95] Michael Molloy and Bruce Reed.  A critical point for random graphs with a given degree sequence.  Random Struct. Algor., 6(2-3):161–180, 1995.
  * [MR98] Michael Molloy and Bruce Reed.  The size of the giant component of a random graph with a given degree sequence.  Comb. Probab. Comput., 7(3):295–305, 1998.
  * [MS02] Alfred Müller and Dietrich Stoyan.  Comparison Methods for Stochastic Models and Risks.  Wiley, 2002.
  * [SK14] Sterling Sawaya and Steffen Klaere.  Extinction in a branching process: Why some of the fittest strategies cannot guarantee survival.  Journal of Statistical Distributions and Applications, 1(10), 2014\.
  * [SS07] Moshe Shaked and J. George Shanthikumar.  Stochastic Orders.  Springer, 2007.
  * [vdH14] Remco van der Hofstad.  Random graphs and complex networks - Vol. I.  Lecture notes. http://www.win.tue.nl/~rhofstad/NotesRGCN.html, 2014\.
  * [VYZ14] José E. Valdés, Yoel G. Yera, and Leonel Zuaznabar.  Bounds for the expected time to extinction and the probability of extinction in the Galton-Watson process.  Communications in Statistics - Theory and Methods, 43(8):1698–1707, 2014.