# Connectivity of random graphs after
centrality-based vertex removal

###### Abstract

Centrality measures aim to indicate who is important in a network. Various
notions of ‘being important’ give rise to different centrality measures. In
this paper, we study how important the central vertices are for the
_connectivity structure_ of the network, by investigating how the removal of
the most central vertices affects the number of connected components and the
size of the giant component. We use _local convergence techniques_ to identify
the limiting number of connected components for locally converging graphs and
centrality measures that depend on the vertex’s neighborhood. For the size of
the giant, we prove a general upper bound. For the matching lower bound, we
specialize to the case of _degree centrality_ on one of the most popular
models in network science, the _configuration model_ , for which we show that
removal of the highest-degree vertices destroys the giant most.

###### keywords:

Strictly local centrality measures; centrality-based vertex removal; number of
connected components; size of giant; configuration model

Remco van der Hofstad, Manish Pandey

[Eindhoven University of Technology]Remco van der Hofstad [Eindhoven
University of Technology]Manish Pandey Department of Mathematics and Computer
Science, Eindhoven University of Technology, 5600 MB Eindhoven, The
Netherlands<EMAIL_ADDRESS><EMAIL_ADDRESS>
60G9905C80; 60E15

##  1 Introduction and Main Results

###  1.1 Introduction

Complex networks are everywhere. Prominent examples include social networks,
Internet, the World-Wide-Web, transportation networks, etc. In any network, it
is of great interest to be able to quantify who is ‘important’ and who is less
so. This is what _centrality measures_ aim to do.

There are several well-known centrality measures in networks [38, Chapter 7],
such as degree centrality, PageRank centrality and betweeness centrality.
PageRank, first proposed in [39], can be visualised as the stationary
distribution of a random walk with uniform restarts. Betweeness centrality was
first defined by Anthonisse [2]. For a survey on centrality measures, see
Boldi and Vigna [9] and Borgatti [12].

There are many ways in which we can compare the effectiveness of centrality
measures. Here, one can think of importance for spreading diseases or
information [42], for being an information bridge between different
communities, or for being an important source of information in a network of
scientific papers [41].

In this paper, we compare centrality measures by investigating the rate of
_disintegration_ of the network by the removal of central vertices. This
approach quantifies the notion that a centrality measure is more effective
when the network disintegrates more upon the removal of the most central
vertices. This work is motivated by the analysis and simulations performed in
[35], where the number of connected components and the size of the giant were
compared after the removal of the most central vertices based on several
centrality measures from a simulation perspective.

Central questions. Our key questions are as follows:

  * $\rhd$

How will the number of connected components grow with the removal of the
most/least central vertices?

  * $\rhd$

Does vertex removal with respect to centrality measures preserve the existence
of local limits?

  * $\rhd$

What are the sub-critical and super-critical regimes of the giant component
for vertex removals with respect to centrality measure?

  * $\rhd$

What is the proportion of vertices in the giant component?

Main innovation of this paper. To answer the above questions, we rely on the
theory of _local convergence_ [1, 6], see also [23, Chapter 2] for an
extensive overview. We show that when considering _strictly local_ centrality
measures, i.e., measures that depend on a fixed-radius neighborhood of a
vertex, the number of connected components after the vertex removal procedure
converges, and the local limit of the removed graph can be determined in terms
of the original local limit. Thus, this answers the first two questions rather
generally, assuming local convergence.

It is well-known that the _giant_ in a random graph is not determined by the
local limit (even though it frequently ‘almost’ is, see [22]). While the upper
bound on the giant is always equal to the survival probability of the local
limit, the matching _lower bound_ can be different. To give an example where
we can prove that the giant of the vertex-removed graph equals the survival
probability of its local limit, we restrict our attention to the configuration
model with a given degree distribution, and degree centrality. There, we
identify the giant of the vertex-removed graph, and also show that the giant
is smaller when removing more degree-central vertices.

###  1.2 Preliminaries

In this section, we define centrality measures and then give an informal
introduction to local convergence, as these play a central role in this paper.
We will assume that $|V(G)|=n$, and for convenience assume that
$V(G)=\\{1,\ldots,n\\}\equiv[n]$.

####  1.2.1 Centrality Measures

In this section, we define _centrality measures:_

######  Definition 1 (Centrality measures)

For a _finite_ (undirected) graph $G=(V(G),E(G))$, a _centrality measure_ is a
function $R\colon V(G)\to\mathbb{R}_{\geq 0}$, where we consider $v$ to be
central if $R(v)$ is large. $\blacktriangleleft$

Centrality measures can be extended to directed graphs, but in this paper we
restrict to undirected graph as in [35]. Commonly used examples of centrality
measures are the following:

Degree Centrality. In degree centrality, we rank the vertices according to
their degrees and then divide the rank by the total number of vertices. We
_randomly_ assign ranks to vertices with the same degree, to remove ties.

PageRank Centrality. PageRank is a popularly known algorithm for measuring
centrality in the World-Wide Web [13]:

######  Definition 2 (PageRank centrality)

Consider a finite (undirected) graph $G$. Let $e_{j,i}$ be the number of edges
between $j$ and $i$. Denote the degree of vertex $i\in[n]$ by $d_{i}$. Fix a
damping factor or teleportation parameter $c\in(0,1)$. Then, PageRank is the
unique probability vector $\boldsymbol{\pi}_{n}=(\pi_{n}(i))_{i\in[n]}$ that
satisfies that, for every $i\in[n]$,

$\pi_{n}(i)=c\sum_{j\in[n]}\frac{e_{j,i}}{d_{j}}\pi_{n}(j)+\frac{1-c}{n},\qquad
i\in[n].$ (1.1)

Suppose $\boldsymbol{1}=(1,1,\ldots,1)$ is the all-one vector. Then, with
$P=(p_{i,j})_{i,j\in V(G)}$ and $p_{i,j}=e_{i,j}/d_{i}$ the transition matrix
for the random walk on $G$,

$\boldsymbol{\pi}_{n}=\left(\frac{1-c}{n}\right)\boldsymbol{1}(I-cP)^{-1}.$
(1.2)

$\blacktriangleleft$

In order to use local convergence techniques [19], it is useful to work with
the graph-normalised PageRank, given by

$\boldsymbol{R}_{n}=n\boldsymbol{\pi}_{n},\qquad\text{for
which}\qquad\frac{1}{n}\sum_{j\in[n]}R_{n}(j)=1.$ (1.3)

Since $c\in(0,1)$, (1.2) implies

$\boldsymbol{\pi}_{n}=\left(\frac{1-c}{n}\right)\boldsymbol{1}\sum_{k=0}^{\infty}c^{k}P^{k}.$
(1.4)

Equation (1.4) is sometimes called _power-iteration_ for PageRank [3, 7, 8].
It will also be useful to consider the _finite-radius_ PageRank,
$\boldsymbol{R}_{n}^{\scriptscriptstyle(N)}$, for $N\in\mathbb{N}$, defined by

$\boldsymbol{R}_{n}^{\scriptscriptstyle(N)}:=\left(\frac{1-c}{n}\right)\boldsymbol{1}\sum_{k=0}^{N}c^{k}P^{k},$
(1.5)

which approximates PageRank by a finite number of powers in (1.4). PageRank
has been intensely studied on various random graph models [5, 15, 16, 19, 31,
32, 34], with the main focus being to prove or disprove that PageRank has the
same power-law exponent as the in-degree distribution.

Other popular centrality measures. _Closeness centrality_ measures the average
distance of a vertex from a randomly chosen vertex. The higher the average,
the lower is the centrality index, and vice-versa. Interestingly, [18]
predicts that closeness centrality is closely related to degree centrality, at
least for locally tree-like graphs. _Betweeness centrality_ measures the
extent to which vertices are important to _interconnect_ different vertices.

In this paper, we mainly work with _strictly-local_ centrality measures:

######  Definition 3 (Strictly local centrality measures)

For a _finite_ (undirected) graph $G=(V(G),E(G))$, a _strictly local
centrality measure_ is a centrality measure $R\colon V(G)\to\mathbb{R}_{\geq
0}$, such that there exists an $r\in\mathbb{N}$ and for each vertex $v\in
V(G)$, $R(v)$ depends only on the graph through the neighborhood

$B_{r}^{\scriptscriptstyle(G)}(v):=\\{u\in V(G)\colon{\rm
dist}_{\scriptscriptstyle G}(u,v)\leq r\\},$ (1.6)

where ${\rm dist}_{\scriptscriptstyle G}(u,v)$ denotes the graph distance
between $u$ and $v$ in $G$. $\blacktriangleleft$

PageRank is very well approximated by its strictly local version as in (1.5)
[4, 9, 19].

####  1.2.2 Local convergence of undirected random graphs

In this section, we informally introduce local convergence of random graphs,
which describes what a graph locally looks like from the perspective of a
uniformly chosen vertex, as the number of vertices in a graph goes to
infinity. For example, the sparse Erdős-Rényi random graph, which is formed by
bond-percolation on the complete graph, locally looks like a Poisson branching
process, as $n$ tends to infinity [23, Chapter 2]. Before moving further, we
discuss the following notations:

######  Notation 1.1 (Probability convergence)

Suppose $(X_{n})_{n\geq 1}$, $(Y_{n})_{n\geq 1}$ are two sequences of random
variables and $X$ is a random variable.

  1. 1.

We write $X_{n}\overset{\scriptscriptstyle{\prob}/d}{\to}X$ when $X_{n}$
converges in probability/distribution to $X$.

  2. 2.

For two sequences $(f(n))_{n\geq 1}$ and $(g(n))_{n\geq 1}$, we write
$f(n)=o(g(n))$ when $\lim_{n\to\infty}f(n)/g(n)=0.$

  3. 3.

We write $X_{n}=o_{\scriptscriptstyle\mathbb{P}}(Y_{n})$ when
$X_{n}/Y_{n}\overset{\scriptscriptstyle\prob}{\to}0$.

Now let us give the informal definition of local convergence. We will rely on
two types of local convergence, namely, local weak convergence and local
convergence in probability. Let $o_{n}$ denote a uniformly chosen vertex from
$V(G_{n})$. Local weak convergence means that

(1.7)

for all rooted graphs $(H,o^{\prime})$, where a rooted graph is a graph with a
distinguished vertex in the vertex set $V(H)$ of $H$. In (1.7),
$(\bar{G},o)\sim\bar{\mu}$ is a random rooted graph, which is called the local
weak limit. For local convergence in probability, instead, we require that

$\frac{1}{|V(G_{n})|}\sum_{v\in
V(G_{n})}\mathbbm{1}_{\left\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\cong(H,o^{\prime})\right\\}}\overset{\scriptscriptstyle\prob}{\to}\mu(B_{r}^{\scriptscriptstyle(G)}(o)\cong(H,o^{\prime})),$
(1.8)

holds for all rooted graphs $(H,o^{\prime})$. In (1.8), $(G,o)\sim\mu$ is a
random rooted graph which is called the local limit in probability (and bear
in mind that $\mu$ can possibly be a random measure on rooted graphs). Both
(1.7) and (1.8) describe the convergence of the proportions of vertices around
which the graph locally looks like a certain specific graph. We discuss this
definition more formally in Section 2.1. We now turn to our main results.

###  1.3 Main results

In this section, we state our main results. In Section 1.3.1, we discuss our
results that hold for general strictly local centrality measures on locally
converging random graph sequences. In Section 1.3.2, we investigate the size
of the giant after vertex removal. Due to the non-local nature of the giant,
there we restrict to _degree centrality_ on the _configuration model_.

####  1.3.1 Strictly local centrality measures

We first define our vertex removal procedure based on centrality:

######  Definition 8 (Vertex removal based on centrality threshold)

Let $G$ be an arbitrary graph. Define $G(R,r)$ to be the graph obtained after
removing all the vertices $v$ for which $R(v)>r$. We call this the
$\boldsymbol{r}$-killed graph of $G$. $\blacktriangleleft$

######  Theorem 9 (Continuity of vertex removal)

Let $R$ be a strictly local centrality measure and ${(G_{n})}_{n\geq 1}$ a
sequence of random graphs that converges locally weakly/ locally in
probability to $(G,o)\sim\mu$. Then, $(G_{n}(R,r))_{n\geq 1}$ converges
locally weakly/ locally in probability to $(G(R,r),o)$, respectively.

Theorem 9 means that vertex removal with respect to a strictly local
centrality threshold is _continuous_ with respect to the local convergence.

Let $C_{r}(o)$ denote the connected component containing the root in the
$r$-killed graph, $(G(R,r),o)\sim\mu$. As a corollary to Theorem 9, we bound
the limiting value of the proportion of vertices in the giant component in
$G_{n}(R,r)$ in probability by the survival probability of
$(G(R,r),o)\sim\mu$, which is $\mu(|C_{r}(o)|=\infty)$.

######  Corollary 10 (Upper bound on giant)

Denote $v(C_{1}(G_{n}(R,r))$ to the number of vertices in the giant component
of $G_{n}(R,r)$. Under the conditions of Theorem 9

$\lim_{n\to\infty}\mathbb{P}(v(C_{1}(G_{n}(R,r)))\leq
n(\zeta+\varepsilon))=1,$

for all $\varepsilon>0$, where $\zeta=\mu(|C_{r}(o)|=\infty).$

Let $K_{n}^{r}(R)$ denote the number of connected component in the killed
graph $G_{n}(R,r)$. As another corollary to Theorem 9, we give the convergence
properties for $K_{n}^{r}(R)$:

######  Corollary 11 (Number of connected components)

Under the conditions of Theorem 9

  1. (a)

If $G_{n}$ converges locally in probability to $(G,o)\sim\mu$, then

$\frac{K_{n}^{r}(R)}{n}\overset{\scriptscriptstyle\prob}{\to}\mathbb{E}_{\mu}\left[\frac{1}{|C_{r}(o)|}\right].$
(1.9)

  2. (b)

If ${(G_{n})}_{n\geq 1}$ converges locally weakly to
$(\bar{G},\bar{o})\sim\bar{\mu}$, then

$\frac{\mathbb{E}[K_{n}^{r}(R)]}{n}\to\mathbb{E}_{\bar{\mu}}\left[\frac{1}{|C_{r}(o)|}\right].$
(1.10)

####  1.3.2 Degree centrality and configuration model

In this section, we restrict to degree centrality in the configuration model.
Before starting with our main results, we introduce the configuration model:

Configuration Model. The configuration model was introduced by Bollobás [10],
see also [21, Chapter 7] and the references therein for an extensive
introduction. It is one of the simplest possible models for generating a
random graph with a given degree distribution. Written as ${\rm
CM}_{n}(\boldsymbol{d})$, it is a random graph on $n$ vertices having a given
degree sequence $\boldsymbol{d}$, where
$\boldsymbol{d}=(d_{1},d_{2},\ldots,d_{n})\in\mathbb{N}^{n}.$ The giant in the
configuration model has attracted considerable attention in e.g., [11, 30, 36,
37, 22]. It is also known how the tail of the limiting degree distribution
influences the size of giant [17]. Further, the diameter and distances in the
supercritical regime have been studied in [24, 25, 26], while criteria for the
graph to be simple appear in [14, 28, 29]. In this paper we assume that the
degrees satisfy the following usual conditions: [Degree conditions] Let
$\boldsymbol{d}=(d_{1},d_{2},\ldots,d_{n})$ denote a degree sequence. Let
$n_{j}=\\{v\colon d_{v}=j\\}$ denote the number of vertices with degree $j$.
We assume that there exists a probability distribution $(p_{j})_{j\geq 1}$
such that the following hold:

  * (a)

$\lim_{n\rightarrow\infty}n_{j}/n=p_{j}$;

  * (b)

$\lim_{n\rightarrow\infty}\sum_{j\geq 1}jn_{j}/n=\sum_{j\geq 1}jp_{j}<\infty$.

Let $D$ be a non-negative integer random variable with probability mass
function $(p_{j})_{j\geq 1}$. These regularity conditions ensures that the
sequence of graphs converges locally in probability to a unimodular branching
process, with degree distribution $D$. See [23, Chapter 4] for more details.

Generalized vertex removal based on degrees. We wish to study the effect of
the removal of the $\alpha$ proportion of vertices with the highest or lowest
degrees on the giant of the configuration model. For this, we define
$\alpha$-sequences with respect to a probability mass function as follows:

######  Definition 13 ($\alpha$-sequence)

Fix $\alpha\in(0,1)$. Let $\boldsymbol{r}:=(r_{i})_{i\geq 1}$ is a sequence of
elements of $[0,1]$ satisfying

$\displaystyle\mathbb{E}[r_{D}$ $\displaystyle]=\sum_{i\geq
1}p_{i}r_{i}=\alpha.$ (1.11)

Then, $\boldsymbol{r}$ is called an $\alpha$-sequence with respect to
$\boldsymbol{p}=(p_{j})_{j\geq 1}$.

Suppose $(G_{n})_{n\geq 1}$ is a sequence of random graph converging locally
in probability to $(G,o)\sim\mu$ and the limiting degree distribution be $D$,
with probability mass function as $\boldsymbol{p}=(p_{j})_{j\geq 1}$. Suppose
$\boldsymbol{r}=(r_{j})_{j\geq 1}$ is an $\alpha$-sequence with respect to
$\boldsymbol{p}$, then we define vertex removal based on $\alpha$-sequences as
follows:

######  Definition 14 (Vertex removal based on $\alpha$-sequences)

Remove $\lfloor nr_{i}p_{i}\rfloor$ vertices of degree $i$ from $G_{n}$
uniformly at random, for each $n\geq 1$. This gives us the vertex removed
graph according to the $\alpha$-sequence $\boldsymbol{r}=(r_{j})_{j\geq 1}$,
denoted by $(G_{n,\boldsymbol{r}})_{n\geq 1}$. $\blacktriangleleft$

###### Remark 15

In $G_{n,\boldsymbol{r}}$, we asymptotically remove an $\alpha$ proportion of
vertices because, due to Condition 1.3.2 and the dominated convergence
theorem,

$\lim_{n\to\infty}\sum_{j\geq 1}r_{j}\frac{n_{j}}{n}=\ \sum_{j\geq
1}r_{j}p_{j}=\alpha.$ (1.12)

Results for the Configuration Model. Let $(G_{n})_{n\geq 1}$ be a sequence of
random graphs satisfying $G_{n}\sim{\rm CM}_{n}(\boldsymbol{d})$. Throughout
the paper, we shall assume that

$\nu:=\frac{\mathbb{E}[D(D-1)]}{\mathbb{E}[D]}>1.$

Indeed for $\nu<1$, we already know that there is no giant to start with, and
it cannot appear by removing vertices.

######  Definition 16 ($\boldsymbol{r}$-set)

Suppose $\boldsymbol{r}=(r_{j})_{j\geq 1}$ is an $\alpha$-sequence with
respect to $\boldsymbol{p}=(p_{j})_{j\geq 1}$. Let $X=[0,1]^{\mathbb{N}}$ be
the set of all sequences in $[0,1]$. Define the set
$S(\boldsymbol{r})=\\{(\boldsymbol{r^{\scriptscriptstyle(n)}})_{n\geq 1}\in
X^{\mathbb{N}},\text{ s.t.
}\lim_{n\to\infty}r_{i}^{\scriptscriptstyle(n)}=r_{i}\quad\forall i\geq 1\\}.$
$\blacktriangleleft$

An $\boldsymbol{r}-$set $S(\boldsymbol{r})$ can be thought of as the set of
those sequences in $[0,1]^{\mathbb{N}}$ which converge to $\boldsymbol{r}$
component wise. Let $v(C_{1}({\boldsymbol{r}}))$ and
$e(C_{1}({\boldsymbol{r}}))$ denote the number of vertices and edges in the
giant component of $G_{n,{\boldsymbol{r}}}$. The following theorem describes
the giant in $G_{n,{\boldsymbol{r^{\scriptscriptstyle(n)}}}}$:

######  Theorem 17 (Existence of giant after vertex removal)

Let $(\boldsymbol{r}^{\scriptscriptstyle(n)})_{n\geq 1}$ be a sequence from
the $\boldsymbol{r}$-set $S(\boldsymbol{r})$. Then the graph
$G_{n,\boldsymbol{r}^{\scriptscriptstyle(n)}}$ has a giant component if and
only if $\nu_{\boldsymbol{r}}>1$, where

$\nu_{\boldsymbol{r}}:=\frac{\mathbb{E}[D(D-1)(1-r_{D})]}{\mathbb{E}[D]}.$
(1.13)

For $\nu_{\boldsymbol{r}}>1$,

$\frac{v(C_{1}(\boldsymbol{r}^{\scriptscriptstyle(n)}))}{n}\overset{\scriptscriptstyle\prob}{\to}\rho(\boldsymbol{r}):=1-\alpha-2\mathbb{E}[Dr_{D}]\eta_{\boldsymbol{r}}-\sum_{i\geq
1}(1-r_{i})p_{i}{\eta^{i}_{\boldsymbol{r}}}.$ (1.14)
$\frac{e(C_{1}(\boldsymbol{r}^{\scriptscriptstyle(n)}))}{n}\overset{\scriptscriptstyle\prob}{\to}e(\boldsymbol{r}):=\frac{\mathbb{E}[D]}{2}(1-{\eta^{2}}_{\boldsymbol{r}})-\mathbb{E}[Dr_{D}](1-{\eta_{\boldsymbol{r}}}).$
(1.15)

In the above equations, ${\eta_{\boldsymbol{r}}}\in(0,1]$ is the smallest
solution of

$g_{\boldsymbol{r}}^{\prime}({\eta_{\boldsymbol{r}}})=\frac{\mathbb{E}[D]}{\beta_{\boldsymbol{r}}}{\eta_{\boldsymbol{r}}},$
(1.16)

where $\beta_{\boldsymbol{r}}=\mathbb{E}[Dr_{D}]+1-\alpha$ and
$g_{\boldsymbol{r}}(\cdot)$ is the generating function for a random variable
dependent on $\boldsymbol{r}$ given by

$g_{\boldsymbol{r}}(s)=\frac{\sum_{i=1}^{\infty}(1-r_{i})p_{i}s^{i}+\mathbb{E}[Dr_{D}]s}{\beta_{\boldsymbol{r}}}.$
(1.17)

######  Remark 20 (Class of sequences with the same limiting proportion)

For the class of sequences which converge to a given $\alpha$-sequence
component wise, we always have the same limiting proportion of vertices/edges
in the giant component. Thus, choosing our sequence
$(\boldsymbol{r}^{\scriptscriptstyle(n)})_{n\geq 1}$ appropriately, it is
always possible to remove an exact $\alpha$ proportion of the vertices from
each $G_{n}$ having the same limiting graph. $\blacktriangleleft$

We next investigate the effect of removing the $\alpha$ proportion of vertices
with the highest/lowest degrees. For that we first define quantiles:

######  Definition 21 (Degree centrality quantiles)

For each $\alpha\in(0,1)$, let $k_{\alpha}$, the top $\alpha$-quantile,
satisfy

$\mathbb{P}(D>k_{\alpha})<\alpha\quad\text{and}\quad\mathbb{P}(D\geq
k_{\alpha})\geq\alpha.$ (1.18)

Similarly for each $\alpha\in(0,1)$, let $l_{\alpha}$, the bottom
$\alpha$-quantile, satisfy

$\mathbb{P}(D<l_{\alpha})<\alpha\quad\text{and}\quad\mathbb{P}(D\leq
l_{\alpha})\geq\alpha.$ (1.19)

$\blacktriangleleft$

######  Definition 22 ($\alpha$-sequences corresponding to top and bottom
removal)

Let $k$ be the top $\alpha$-quantile for the degree distribution $D$. Define
$\bar{\boldsymbol{r}}(\alpha)$ to have coordinates equal to zero until the
$k$th coordinate, which is $(\alpha-\mathbb{P}(D>k))/p_{k}$, and ones
thereafter. Then $\bar{\boldsymbol{r}}(\alpha)$ is the $\alpha$-sequence
corresponding to the top $\alpha$-removal.

Similarly, let $l$ be the lower $\alpha$-quantile for the degree distribution
$D$. Define $\underline{\boldsymbol{r}}(\alpha)$ to have coordinates equal to
one until the $l$th coordinate, which is $(\alpha-\mathbb{P}(D<l))/p_{l}$, and
zeroes thereafter. Then $\underline{\boldsymbol{r}}(\alpha)$ is the
$\alpha$-sequence corresponding to the bottom $\alpha$-removal.
$\blacktriangleleft$

######  Corollary 23 (Highest/lowest $\alpha$-proportion removal)

Let $\bar{\alpha}_{c}$ and $\underline{\alpha}_{c}$ be defined as

$\displaystyle\bar{\alpha}_{c}=\inf\\{\alpha>0:\mathbb{E}[D(D-1)\mathbbm{1}\\{D\leq
k_{\alpha}\\}]>\mathbb{E}[D]+k_{\alpha}(k_{\alpha}-1)\left(\alpha-\mathbb{P}(D>k_{\alpha})\right)\\},$
$\displaystyle\underline{\alpha}_{c}=\inf\\{\alpha>0:\mathbb{E}[D(D-1)\mathbbm{1}\\{D\
\geq
l_{\alpha}\\}]>\mathbb{E}[D]+l_{\alpha}(l_{\alpha}-1)\left(\alpha-\mathbb{P}(D<l_{\alpha})\right)\\}.$

  1. (1)

Let $v(\bar{C}_{1}^{\alpha})$ and $e(\bar{C}_{1}^{\alpha})$ be the number of
vertices and edges in the largest connected component of the top
$\alpha$-proportion degree vertex removed graph, respectively. If
$\alpha\geq\bar{\alpha}_{c}$, then there is no giant component, i.e.,
$v(\bar{C}_{1}^{\alpha})/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}0$.
If $\alpha<\bar{\alpha}_{c}$, then the giant exists and

$\displaystyle\frac{v(\bar{C}_{1}^{\alpha})}{n}\overset{\scriptscriptstyle\prob}{\to}\rho(\bar{\boldsymbol{r}}(\alpha))>0\qquad\text{
and
}\qquad\frac{e(\bar{C}_{1}^{\alpha})}{n}\overset{\scriptscriptstyle\prob}{\to}e(\bar{\boldsymbol{r}}(\alpha))>0.$
(1.20)

  2. (2)

Let $v(\underline{C}_{1}^{\alpha})$ and $e(\underline{C}_{1}^{\alpha})$ be the
number of vertices and edges in the largest connected component of the lowest
$\alpha$ proportion degree vertex removed graph, respectively. If
$\alpha\geq\underline{\alpha}_{c}$, then there is no giant, i.e.,
$v(\underline{C}_{1}^{\alpha})/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}0$.
If $\alpha<\underline{\alpha}_{c}$, then the giant exists and

$\displaystyle\frac{v(\underline{C}_{1}^{\alpha})}{n}\overset{\scriptscriptstyle\prob}{\to}\rho(\underline{\boldsymbol{r}}(\alpha))>0\qquad\text{
and
}\qquad\frac{e(\underline{C}_{1}^{\alpha})}{n}\overset{\scriptscriptstyle\prob}{\to}e(\underline{\boldsymbol{r}}(\alpha))>0.$
(1.21)

We next give bounds on the size of the giant in the vertex removed graph:

######  Theorem 28 (Bounds for proportion of giant)

Let ${\boldsymbol{r}}$ be an $\alpha$-sequence. Then

$\mathbb{E}[D({\eta_{\boldsymbol{r}}}-r_{D})](1-{\eta_{\boldsymbol{r}}})\leq\rho({\boldsymbol{r}})\leq\mathbb{E}[D(1-r_{D})](1-{\eta_{\boldsymbol{r}}}).$
(1.22)

In the above equation, $\eta_{\boldsymbol{r}}\in(0,1]$ satisfies (1.16).
Furthermore,

$\displaystyle\rho({\boldsymbol{r}})\leq\frac{\mathbb{E}[D(1-r_{D})]^{2}}{\mathbb{E}[D]}\qquad\text{
and }\qquad
e({\boldsymbol{r}})\leq\frac{\mathbb{E}[D(1-r_{D})]^{2}}{2\mathbb{E}[D]},$
(1.23)

and

$\displaystyle\rho({\boldsymbol{r}})\leq
1-\alpha-\frac{2\mathbb{E}[Dr_{D}]^{2}}{\mathbb{E}[D]}<1-\alpha-\frac{2\alpha^{2}}{\mathbb{E}[D]}.$
(1.24)

Additionally, for $\alpha$-sequences which are positively correlated with
degree, we have

$\rho({\boldsymbol{r}})\leq 1-\alpha-2\alpha^{2}\mathbb{E}[D].$ (1.25)

###### Remark 29

$\bar{\boldsymbol{r}}(\alpha)$ is positively correlated with degree. Thus, for
top $\alpha$-proportion removal (1.25) holds

$\rho({\bar{\boldsymbol{r}}}(\alpha))\leq 1-\alpha-2\alpha^{2}\mathbb{E}[D].$
(1.26)

The next logical question is which $\alpha$-sequence destroys the graph the
most. Intuitively, the size of the giant should be the smallest if we remove
the top $\alpha$-proportion degree vertices and the largest when we remove the
bottom $\alpha$ proportion degree vertices, i.e.,
$\rho(\bar{\boldsymbol{r}}(\alpha))\leq\rho(\boldsymbol{r})\leq\rho(\underline{\boldsymbol{r}}(\alpha))$
and $e(\bar{\boldsymbol{r}}(\alpha))\leq e(\boldsymbol{r})\leq
e(\underline{\boldsymbol{r}}(\alpha))$. To prove this, we first define a
partial order over the set of all $\alpha$-sequences that is able to capture
which vertex-removal is more effective for the destruction of the giant in the
configuration model. For this, we recall that, for two non-negative measures
$\mu_{1}$ and $\mu_{2}$ on the real line, we say that $\mu_{1}$ is
stochastically dominated by $\mu_{2}$, and write
$\mu_{1}\preccurlyeq_{\rm{st}}\mu_{2}$, if
$\mu_{1}\left([K,\infty)\right)\leq\mu_{2}\left([K,\infty)\right)$ for all
$K\in\mathbb{R}$. We next extend this to a partial order over the set of all
$\alpha$-sequences:

######  Definition 30 (Stochastically dominant sequences)

Let ${\boldsymbol{r}}=(r_{j})_{j\geq 1}$ and
${\boldsymbol{r^{\prime}}}=(r^{\prime}_{j})_{j\geq 1}$ be $\alpha_{1}$\- and
$\alpha_{2}$-sequences, respectively. Then the sequences
${\boldsymbol{q}}=(p_{j}r_{j})_{j\geq 1}$ and
${\boldsymbol{q^{\prime}}}=(p_{j}r^{\prime}_{j})_{j\geq 1}$ form finite non-
negative measures. We say that $\boldsymbol{r^{\prime}}$ stochastically
dominates $\boldsymbol{r}$, or
$\boldsymbol{r}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r^{\prime}}$, if
$\boldsymbol{q}\preccurlyeq_{\rm{st}}\boldsymbol{q^{\prime}}$.
$\blacktriangleleft$

The following theorem answers which is the best and the worst way to remove an
$\alpha$-proportion vertices from a configuration model and compares other
$\alpha$-sequences:

######  Theorem 31 (Comparison between $\alpha$-sequences)

Let ${\boldsymbol{r}}=(r_{j})_{j\geq 1}$ and
${\boldsymbol{r}}^{\prime}=(r^{\prime}_{j})_{j\geq 1}$ be two
$\alpha$-sequences such that
${\boldsymbol{r}}^{\prime}\preccurlyeq_{\boldsymbol{p}}{\boldsymbol{r}}$.
Then,

$\displaystyle\rho(\bar{\boldsymbol{r}}(\alpha))\leq\rho(\boldsymbol{r})\leq\rho(\boldsymbol{r}^{\prime})\leq\rho(\underline{\boldsymbol{r}}(\alpha))\quad\text{and}\quad
e(\bar{\boldsymbol{r}}(\alpha))\leq e(\boldsymbol{r})\leq
e(\boldsymbol{r}^{\prime})\leq e(\underline{\boldsymbol{r}}(\alpha)).$

As a result, the critical $\alpha$’s for the bottom and top vertex removal
satisfy $\underline{\alpha}_{c}>\bar{\alpha}_{c}.$

The following corollary is stronger than the theorem (as the corollary
immediately implies the theorem), but it follows from the proof of Theorem 31:

######  Corollary 32 (General comparison)

Suppose $\boldsymbol{r},\boldsymbol{r}^{\prime}\in[0,1]^{\mathbb{N}}$ satisfy
$\boldsymbol{r}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}^{\prime}$. Then
$\rho(\boldsymbol{r}^{\prime})\leq\rho(\boldsymbol{r})$ and
$e(\boldsymbol{r}^{\prime})\leq e(\boldsymbol{r})$.

###  1.4 Overview of the proof

In this section, we give an overview to the proofs. The theorems in this paper
are of two types: The first concern arbitrary strictly local centrality
measures on a sequence of locally converging random graphs, whereas the second
concerns degree centrality on the configuration model. We discuss these
separately in the next two sections.

####  1.4.1 Strictly local centrality measures

In this section, we discuss the proof structure for Theorem 9, which involves
the following steps:

  1. 1.

Proof that the vertex removal function with respect to a strictly local
centrality measure is _continuous_ with respect to the rooted graph topology.
As a result, if a function on the set of rooted graphs is continuous, then
this function composed with the function of vertex removal with respect to the
strictly local centrality $R$ is also continuous.

  2. 2.

Next we use the above observations and the local convergence of the sequence
$(G_{n})_{n\geq 1}$ to complete the proof of Theorem 9, and Corollaries 10 and
11 are immediate consequences.

####  1.4.2 Configuration model and degree centrality

In this section, we discuss a construction, motivated by [27], and how it
helps in the study of vertex removal procedure on the configuration model.

Let $G=(V,E)$ be a graph. Suppose $V^{\prime}\subset V$ is the set of vertices
that we wish to remove. We will start by constructing an intermediate graph.
which we call the vertex-exploded graph, and denote it by
$\tilde{G}(V^{\prime})$. To obtain $\tilde{G}(V^{\prime})$ from $G$, we follow
the following steps:

  1. 1.

Index the vertices of the set $V^{\prime}=\\{v_{1},v_{2},\ldots,v_{m}\\}$,
where $m=|V^{\prime}|$.

  2. 2.

_Explode_ the first vertex from the set $V^{\prime}$ into $d_{v_{1}}$ vertices
of degree one.

  3. 3.

Label these new degree-one vertices red.

  4. 4.

Do this for each vertex of $V^{\prime}$.

We denote the number of vertices and degree sequence of
$\tilde{G}(V^{\prime})$ by $\tilde{n}$ and its degree sequence by
$\tilde{\boldsymbol{d}}$. The removal of red vertices, together with the
(single) edge adjacent to them, from $\tilde{G}(V^{\prime})$ gives the
$V^{\prime}$ removed graph. Next, we show that the vertex-exploded graph
remains a configuration model, if vertices are removed with respect to their
degree sequence. This means that we only look at the degree sequence to decide
which vertices to remove, independently of the graph. It is this property that
makes the configuration model amenable for vertex removal based on degree
centrality:

######  Lemma 33 (Exploded configuration model is still a configuration model)

Let $G_{n}={\rm CM}_{n}(\boldsymbol{d})$ be a configuration model with degree
sequence $\boldsymbol{d}=(d_{i})_{i\in[n]}$. Let $\tilde{G}_{n}$ be the
vertex-exploded graph formed from $G_{n}$, where vertices are exploded with
respect to the degree sequence. Then, $\tilde{G}_{n}$ has the same
distribution as ${\rm CM}_{\tilde{n}}(\tilde{\boldsymbol{d}}).$

###### Proof 1.1

A degree sequence in a configuration model can be viewed as half-edges
incident to vertices. These half-edges are matched via a uniform perfect
matching. Suppose one explodes a vertex of degree $i$ in ${\rm
CM}_{n}(\boldsymbol{d})$, then we get a new degree distribution. When one
explodes a vertex of degree $i$, we still have these $i$ half-edges, but these
half-edges will now be incident to a unique newly formed (red) vertex. Since
we are just changing the vertex to which these half-edges are incident, the
half-edges in the vertex-exploded graph are still matched via a uniform
perfect matching, so that the newly formed graph is also a configuration
model, but now with $\tilde{n}$ vertices and degree sequence
$\tilde{\boldsymbol{d}}$.

This lemma is useful because of the following result by Janson and Luczak [30]
to study the giant component in a configuration model:

######  Theorem 34 (Janson and Luczak [30])

Consider ${\rm CM}_{n}(\boldsymbol{d})$ satisfying regularity Conditions 1.3.2
with limiting degree distribution $D$. Let $g_{D}(x):=\sum_{j}p_{j}x^{j}$ be
the probability generating function of $D$. Assume $p_{1}>0$.

  1. (i)

If $\mathbb{E}[D(D-2)]>0$, then there exists unique $\eta\in(0,1)$ such that
$g_{D}^{{}^{\prime}}(\eta)=\mathbb{E}[D]\eta$ and

    1. (1)

$\frac{v(C_{1})}{n}\overset{\scriptscriptstyle\prob}{\to}1-g_{D}(\eta)$;

    2. (2)

$\frac{v_{j}(C_{1})}{n}\overset{\scriptscriptstyle\prob}{\to}p_{j}(1-\eta^{j})$
for all $j\geq 0$;

    3. (3)

$\frac{e(C_{1})}{n}\overset{\scriptscriptstyle\prob}{\to}\frac{\mathbb{E}[D]}{2}(1-\eta^{2})$.

  2. (ii)

If $\mathbb{E}[D(D-2)]\leq 0$, then
$\frac{v(C_{1})}{n}\overset{\scriptscriptstyle\prob}{\to}0$ and
$\frac{e(C_{1})}{n}\overset{\scriptscriptstyle\prob}{\to}0$,

where $C_{1}$ denotes the largest component of ${\rm CM}_{n}(\boldsymbol{d})$.

Using this theorem on the vertex-exploded graph, we obtain the size of giant
(vertices and edges). Removal of the red vertices in the vertex-exploded graph
gives the required vertex removed graph. This fact is used to complete the
proof of Theorem 17. The remaining results are proved by carefully
investigating the limiting proportion of vertices and edges in the giant, and
how they relate to the precise $\alpha$-sequence.

###  1.5 Discussion and open problems

In this section, we discuss the motivation of the problem and some open
problems. The problem of vertex removal with respect to the centrality
measures was motivated by [35], which showed by simulation the size of the
giant and the number of connected components behave for vertex removal based
on different centrality measures. These plots were used to compare the
effectiveness of these centrality measures.

A related problem is whether we can compare the size of giants in
configuration models if their limiting degree distributions have some
stochastic ordering. This question can be answered using the notion of
$\varepsilon$-transformation as discussed in Definition 54 below. Let
$\rho_{\scriptscriptstyle\rm{CM}}(\boldsymbol{p})$ denote the size of giant
for the configuration model case when the limiting degree distribution is
$\boldsymbol{p}$:

######  Theorem 40 (Stochastic ordering and giant in configuration model)

If $\boldsymbol{p}\preccurlyeq_{\rm{st}}\boldsymbol{q},$ then
$\rho_{\scriptscriptstyle\rm{CM}}(\boldsymbol{p})\leq\rho_{\scriptscriptstyle\rm{CM}}(\boldsymbol{q})$.

A similar result is proved in [33] for increasing concave ordering (a
stochastic order different from the one used in this paper), but it requires a
strong additional assumption that we can remove.

Open problems. We close this section with some related open problems:

  1. 1.

What is the size of the configuration model giant for the vertex removed graph
in case of strictly local centrality measures? Which strictly local centrality
measure performs the best? Can we extend this to non-local centrality
measures?

  2. 2.

Strictly local approximations to non-local centrality measures: PageRank can
be very well approximated by the strictly local approximation in (1.5). Can
betweeness, closeness, and other important centrality measures also be well
approximated by strictly local centrality measures? What graph properties are
needed for such an approximation to be valid? Is it true on configuration
models, as predicted for closeness centrality in [18] and suggested for both
closeness and betweeness in [20]? If so, then one can use these strictly local
centrality measures for vertex removal procedures.

  3. 3.

Stochastic monotonicity for the number of connected components: If one starts
removing vertices from a graph, the number of connected components first
increases and then decreases. Where does it start decreasing?

  4. 4.

Extension of results to directed graphs: can we extend the results of this
paper to directed graphs? For the directed graphs, there are several
connectivity notions, while vertices have two degrees, making degree
centrality less obvious.

##  2 Proofs: strictly local centrality measures

In this section, we define _local convergence_ of random graphs and then prove
the results stated in Section 1.3.1.

###  2.1 Local convergence of undirected random graphs

To define local convergence, we introduce isomorphisms of rooted graphs, a
metric space on them, and finally convergence in it. For more details, refer
to [23, Chapter 2]

######  Definition 41 (Rooted (multi)graph, rooted isomorphism, and
neighborhood)

  1. 1.

We call a pair $(G,o)$ a rooted (multi)graph if $G$ is a locally finite,
connected (multi)graph and $o$ is a distinguished vertex of $G$.

  2. 2.

We say that two multigraphs $G_{1}$ and $G_{2}$ are isomorphic, written as
$G_{1}\cong G_{2}$, if there exists a bijection $\phi\colon V(G_{1})\to
V(G_{2})$ such that for any $v,w\in V(G_{1})$, the number of edges between
$v,w$ in $G_{1}$ equals the number of edges between $\phi(v),\phi(w)$ in
$G_{2}$.

  3. 3.

We say that the rooted (multi)graphs $(G_{1},o_{1})$ and $(G_{2},o_{2})$ are
rooted isomorphic if there exists a graph-isomorphism between $G_{1}$ and
$G_{2}$ that maps $o_{1}$ to $o_{2}$.

  4. 4.

For $r\in\mathbb{N}$, we define $B_{r}^{\scriptscriptstyle(G)}(o)$, the
(closed) $r$-ball around $o$ in $G$ or $r$-neighborhood of $o$ in $G$, as the
subgraph of $G$ spanned by all vertices of graph distance at most $r$ from
$o$. We think of $B_{r}^{\scriptscriptstyle(G)}(o)$ as a rooted (multi)graph
with root $o$.

We next define a metric space over the set of rooted (multi)graphs:

######  Definition 42 (Metric space on rooted (multi)graphs)

Let $\mathscr{G}_{\star}$ be the space of all rooted (multi)graphs. Let
$(G_{1},o_{1})$ and $(G_{2},o_{2})$ be two rooted (multi)graphs. Let
$R^{\star}=\sup\left\\{r\geq 0|B_{r}^{\scriptscriptstyle(G_{1})}(o_{1})\cong
B_{r}^{\scriptscriptstyle(G_{2})}(o_{2})\right\\}.$ The metric
$d_{\scriptscriptstyle\mathscr{G}_{\star}}\colon\mathscr{G}_{\star}\times\mathscr{G}_{\star}\to\mathbb{R}_{\geq
0}$ is defined by

$d_{\scriptscriptstyle\mathscr{G}_{\star}}\left((G_{1},o_{1}),(G_{2},o_{2})\right):=\frac{1}{R^{\star}+1}.$
(2.1)

We next define local weak convergence and local convergence in probability for
any sequence from the space of rooted random graphs:

######  Definition 43 (Local weak convergence of rooted (multi)graphs)

The sequence of random (multi)graphs $(G_{n})_{n\geq 1}$ is said to converge
locally weakly to the random rooted graph $(G,o)$, a random variable taking
values in $\mathscr{G}_{\star}$, having law $\mu$, if for every bounded
continuous function $f\colon\mathscr{G}_{\star}\to\mathbb{R}$, as
$n\to\infty$,

$\lim_{n\to\infty}\mathbb{E}[f(G_{n},o_{n})]=\mathbb{E}_{\mu}[f(G,o)],$ (2.2)

where $o_{n}$ is a uniformly chosen vertex from the vertex set of $G_{n}$.
$\blacktriangleleft$

######  Definition 44 (Local convergence in probability)

The sequence of random (multi)graphs $(G_{n})_{n\geq 1}$ is said to converge
locally in probability to the random rooted graph $(G,o)$, a random variable
taking values in $\mathscr{G}_{\star}$, having law $\mu$, when, for every
$r>0$, and for every $(H,o^{\prime})\in\mathscr{G}_{\star}$, as $n\to\infty$,

$\frac{1}{|V(G_{n})|}\sum_{v\in
V(G_{n})}\mathbbm{1}_{\left\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\cong(H,o^{\prime})\right\\}}\overset{\scriptscriptstyle\prob}{\to}\mu(B_{r}^{\scriptscriptstyle(G)}(o)\cong(H,o^{\prime})).$
(2.3)

$\blacktriangleleft$

###  2.2 Local convergence proofs

In this section, we prove the results stated in Section 1.3.1. Let us take a
strictly local centrality measure $R$. This means that it only depends on a
finite fixed neighborhood, say $N\in\mathbb{N}$. The following lemma shows
that the map $(G,o)\to(G(R,r),o)$ is continuous:

######  Lemma 46 (Continuity of centrality-based vertex removal)

Let $R$ be a strictly local centrality measure and
$h\colon\mathscr{G}_{\star}\to\mathbb{R}$ be a continuous bounded map, where
$\mathscr{G}_{\star}$ is the space of rooted graphs, with the standard metric,
$d$, as in Definition 42. Suppose $f:\mathscr{G}_{\star}\to\mathbb{R}$
satisfies

$f(G,o)=h(G(R,r),o).$ (2.4)

Then $f(\cdot)$ is a bounded continuous function.

###### Proof 2.1

$f(\cdot)$ is bounded because $h(\cdot)$ is bounded. Thus, we only need to
show that $f(\cdot)$ is continuous, i.e., for all $\varepsilon>0$, there
exists $\delta>0$ such that

$d_{\scriptscriptstyle\mathscr{G}_{\star}}\left((G_{1},o_{1}),(G_{2},o_{2})\right)<\delta\implies|h(G_{1}(R,r),o_{1})-h(G_{2}(R,r),o_{2})|<\varepsilon.$

Recall that $d_{\scriptscriptstyle\mathscr{G}_{\star}}$ denotes the metric on
$\mathscr{G}_{\star}$. By continuity of $h(\cdot)$, for all $\varepsilon>0$,
there exists $\delta^{\prime}>0$ such that

$d_{\scriptscriptstyle\mathscr{G}_{\star}}((G_{1},o_{1}),(G_{2},o_{2}))<\delta^{\prime}\implies|h(G_{1},o_{1})-h(G_{2},o_{2})|<\varepsilon.$

Thus, it is enough to show that, for all $\delta^{\prime}>0$, there exists
$\delta>0$, such that

$\displaystyle
d_{\scriptscriptstyle\mathscr{G}_{\star}}((G_{1},o_{1}),(G_{2},o_{2}))<\delta\implies
d_{\scriptscriptstyle\mathscr{G}_{\star}}((G_{1}(R,r),o_{1}),(G_{2}(R,r),o_{2}))<\delta^{\prime}.$
(2.5)

Let

$\delta=\left(\frac{\delta^{\prime}}{1+(2N-1)\delta^{\prime}}\right)^{\frac{1}{2N+3}},$
(2.6)

then we claim that (2.5) holds. In this we have used the definition of metric
space over rooted graphs along with the fact that

$B_{2N+l}^{\scriptscriptstyle(G_{1})}(o_{1})\overset{\sim}{=}B_{2N+l}^{\scriptscriptstyle(G_{2})}(o_{2})\implies
B_{l}^{\scriptscriptstyle(G_{1}(R,r))}(o_{1})\overset{\sim}{=}B_{l}^{\scriptscriptstyle(G_{2}(R,r))}(o_{2}).$
(2.7)

This is because the centrality measure $R(v)$ only depends on
$B_{N}^{\scriptscriptstyle(G)}(v)$. This proves the lemma.

######  Proof 2.2 (Proof of Theorem 9)

Suppose that $(G_{n},o_{n})$ converges locally weakly to $(G,o)\sim\mu$, which
means that for all continuous and bounded functions
$f:\mathscr{G}_{\star}\to\mathbb{R}$,

$\lim_{n\to\infty}\mathbb{E}[f(G_{n},o_{n})]=\mathbb{E}[f(G,o)].$ (2.8)

Using $f(\cdot)$ from Lemma 46 in (2.8) we get

$\lim_{n\to\infty}\mathbb{E}[h(G_{n}(R,r),o_{n})]=\lim_{n\to\infty}\mathbb{E}[f(G_{n},o_{n})]=\mathbb{E}[f(G,o)]=\mathbb{E}[h(G(R,r),o)].$
(2.9)

Thus, $(G_{n}(R,r),o_{n})$ converges locally weakly to $(G(R,r),o)$.
Similarly, suppose that $(G_{n},o_{n})$ converges locally in probability to
$(G,o)\sim\mu$, which means for all continuous and bounded function
$f\colon\mathscr{G}_{\star}\to\mathbb{R}$,

$\mathbb{E}[f(G_{n},o_{n})|G_{n}]\overset{\scriptscriptstyle\prob}{\to}\mathbb{E}[f(G,o)].$
(2.10)

Using $f(\cdot)$ from Lemma 46 in (2.10) we get

$\mathbb{E}[h(G_{n}(R,r),o_{n})|G_{n}]=\mathbb{E}[f(G_{n},o_{n})|G_{n}]\overset{\scriptscriptstyle\prob}{\to}\mathbb{E}[f(G,o)]=\mathbb{E}[h(G(R,r),o)].$
(2.11)

Thus, $(G_{n}(R,r),o_{n})$ converges locally in probability to $(G(R,r),o)$.

######  Proof 2.3 (Proof of Corollaries 10 and 11)

These proofs follow immediately from the upper bound on the giant given in
[23, Corollary 2.28], and the convergence of the number of connected
components in [23, Corollary 2.22].

##  3 Proofs: Degree centrality and configuration model

In this section, we restrict ourselves to the configuration model and
investigate all possible $\alpha$-proportion vertex removals, which can be
performed with respect to degree centrality, and then compare them on the
basis of the size of giant.

###  3.1 Giant in vertex removed configuration model: Proof of Theorem 17

For the proof we use the vertex explosion construction as in Section 1.4.2. We
apply the following steps on $G_{n}$:

  1. 1.

Choose $\lfloor n_{k}r_{k}^{\scriptscriptstyle(n)}\rfloor$ vertices uniformly
from the set of vertices of degree $k$ and explode them into $k$ vertices of
degree $1$.

  2. 2.

Label these newly formed degree-$1$ vertices red.

  3. 3.

Repeat this for each $k\in\mathbb{N}$.

This newly constructed graph is $\tilde{G}(V^{\prime})$ from Section 1.4.2 for
an appropriately chosen $V^{\prime}$. We shall denote it by $\tilde{G}_{n}$.
Let $\tilde{n}_{k}$, $\tilde{n}$ and $n_{+}$ denote the number of degree-$k$
vertices, total number of vertices, and number of vertices with red label in
the vertex-exploded graph $\tilde{G}_{n}$, respectively. Then,

$\tilde{n}_{i}=\left.\begin{cases}n_{+}+n_{1}-\lfloor
n_{1}r^{\scriptscriptstyle(n)}_{1}\rfloor&\text{for }i=1,\\\ n_{i}-\lfloor
n_{i}r^{\scriptscriptstyle(n)}_{i}\rfloor&\text{for }i\neq
1.\end{cases}\right.$ (3.1)

$n_{+}=\sum_{i=1}^{\infty}i\lfloor
n_{i}r^{\scriptscriptstyle(n)}_{i}\rfloor=n\sum_{i=1}^{\infty}i\frac{\lfloor
n_{i}r^{\scriptscriptstyle(n)}_{i}\rfloor}{n}.$ (3.2)

$\tilde{n}=\sum_{i=1}^{\infty}\tilde{n}_{k}=n+\sum_{i=1}^{\infty}(i-1)\lfloor
n_{i}r^{\scriptscriptstyle(n)}_{i}\rfloor=n(1+\sum_{i=1}^{\infty}(i-1)\frac{\lfloor
n_{i}r^{\scriptscriptstyle(n)}_{i}\rfloor}{n}).$ (3.3)

Then, by applying the dominated convergence theorem on (3.2) and (3.3),

$n_{+}=\mathbb{E}[Dr_{D}]n+o(n),\qquad\tilde{n}=\beta_{\boldsymbol{r}}n+o(n).$
(3.4)

Recall that $\beta_{\boldsymbol{r}}=\mathbb{E}[Dr_{D}]+1-\alpha$. Due to (3.1)
and (3.4),

$\frac{\tilde{n}_{i}}{n}=\left.\begin{cases}\mathbb{E}[Dr_{D}]+p_{1}(1-r_{1})+o(1)&\text{for
}i=1,\\\ p_{i}(1-r_{i})+o(1)&\text{for }i\neq 1.\end{cases}\right.$ (3.5)

We define

$\tilde{p}_{i}:=\left.\begin{cases}\beta_{\boldsymbol{r}}^{-1}(\mathbb{E}[Dr_{D}]+p_{1}(1-r_{1}))&\text{for
}i=1,\\\ \beta_{\boldsymbol{r}}^{-1}p_{i}(1-r_{i})&\text{for }i\neq
1.\end{cases}\right.$ (3.6)

Then, by (3.5), for every $i\geq 1$,

$\frac{\tilde{n}_{i}}{\tilde{n}}\to\tilde{p}_{i}.$ (3.7)

Let $\tilde{D}$ be a random variable with probability mass function
$(\tilde{p}_{j})_{j\geq 1}$.

By Lemma 33, $\tilde{G}_{n}$ is also a configuration model. Equation (3.7)
shows that the regularity Condition 1.3.2(a) holds for
$\boldsymbol{\tilde{d}}$. Similarly, Condition 1.3.2(b) also holds. Using
Theorem 34, the giant in $\tilde{G}_{n}$ exists if and only if
$\mathbb{E}[\tilde{D}(\tilde{D}-2)]>0$. We compute

$\begin{split}\mathbb{E}[\tilde{D}(\tilde{D}-2)]&=\frac{1}{\beta_{\boldsymbol{r}}}\sum_{j\geq
1}j(j-2)p_{j}(1-r_{j})-\frac{1}{\beta_{\boldsymbol{r}}}\mathbb{E}[Dr_{D}]\\\
&=\frac{1}{\beta_{\boldsymbol{r}}}\mathbb{E}[D(D-2)(1-r_{D})]-\frac{1}{\beta_{\boldsymbol{r}}}\mathbb{E}[Dr_{D}]\\\
&=\frac{1}{\beta_{\boldsymbol{r}}}\mathbb{E}[D(D-1)(1-r_{D})]-\frac{1}{\beta_{\boldsymbol{r}}}\mathbb{E}[D].\end{split}$
(3.8)

Recall $\nu_{\boldsymbol{r}}$ from (1.13). By (3.8),

$\mathbb{E}[\tilde{D}(\tilde{D}-2)]>0\iff\nu_{\boldsymbol{r}}>1.$ (3.9)

Thus, $\tilde{G}_{n}$ has a giant if and only if $\nu_{\boldsymbol{r}}>1$.
Recall that the removal of red vertices (having degree 1) from $\tilde{G}_{n}$
gives $G_{n,\boldsymbol{r}^{\scriptscriptstyle(n)}}$. Since we remove a
fraction $n_{+}/\tilde{n_{1}}$ of all degree-1 vertices, due to the law of
large numbers for a hypergeometric distribution, we asymptotically remove the
same fraction of degree-1 vertices in the giant component. Thus, as
$n\to\infty$,

$v(C_{1}(\boldsymbol{r}^{\scriptscriptstyle(n)}))=v(\tilde{C_{1}})-v_{1}(\tilde{C_{1}})\times\frac{n_{+}}{\tilde{n_{1}}}(1+o_{\scriptscriptstyle\mathbb{P}}(n)).$
(3.10)

See Janson [27, (3.5)]. Also, by Theorem 34,

$\displaystyle\frac{v(\tilde{C_{1}})}{\tilde{n}}\overset{\scriptscriptstyle\prob}{\to}1-g_{\tilde{D}}(\eta_{\boldsymbol{r}})\qquad\text{
and
}\qquad\frac{v_{1}(\tilde{C_{1}})}{\tilde{n}}\overset{\scriptscriptstyle\prob}{\to}\tilde{p}_{1}(1-\eta_{\boldsymbol{r}}),$
(3.11)

where $\eta_{\boldsymbol{r}}\in(0,1]$ satisfies
$\beta_{\boldsymbol{r}}g_{\tilde{D}}^{\prime}(\eta_{\boldsymbol{r}})=\mathbb{E}[D]\eta_{\boldsymbol{r}}$.
Here, we recall that $v(C_{1}(\boldsymbol{r}))$ is the number of vertices in
the largest component of $G_{n,\boldsymbol{r}}$. We define $v(\tilde{C}_{1})$
to be the number of vertices in the largest component of $\tilde{G}_{n}$ and
$v_{1}(\tilde{C}_{1})$ to be the number of degree-1 vertices in the largest
component of $\tilde{G}_{n}$.

Due to (3.10), we conclude that there is a giant in
$G_{n,\boldsymbol{r}^{\scriptscriptstyle(n)}}$ if and only if there is a giant
in $\tilde{G}_{n}$. Thus, the giant exists if $\nu_{\boldsymbol{r}}>1$ and
does not exist if $\nu_{\boldsymbol{r}}\leq 1$. By (3.4),
$\tilde{n}/n\to\beta_{\boldsymbol{r}}$. This means that (3.11) and (3.10) give
us

$\frac{v(C_{1}(\boldsymbol{r}^{\scriptscriptstyle(n)}))}{n}\overset{\scriptscriptstyle\prob}{\to}\beta_{\boldsymbol{r}}(1-g_{\tilde{D}}(\eta_{\boldsymbol{r}}))-(1-\eta_{\boldsymbol{r}})\mathbb{E}[Dr_{D}].$
(3.12)

Let

$\rho(\boldsymbol{r}):=\beta_{\boldsymbol{r}}(1-g_{\tilde{D}}(\eta_{\boldsymbol{r}}))-(1-\eta_{\boldsymbol{r}})\mathbb{E}[Dr_{D}]=1-\alpha-\mathbb{E}[Dr_{D}]\eta_{\boldsymbol{r}}-\beta_{\boldsymbol{r}}g_{\tilde{D}}(\eta_{\boldsymbol{r}}).$

By definition of generating function,

$\beta_{\boldsymbol{r}}g_{\tilde{D}}(\eta_{\boldsymbol{r}})=\sum_{j\geq
1}\tilde{p}_{j}\eta_{\boldsymbol{r}}^{j}=\sum_{j\geq
1}p_{i}(1-r_{i})\eta_{\boldsymbol{r}}^{i}+\mathbb{E}[Dr_{D}]\eta_{\boldsymbol{r}}.$

Thus,

$\rho(\boldsymbol{r})=1-\alpha-2\mathbb{E}[Dr_{D}]\eta_{\boldsymbol{r}}-\sum_{i\geq
1}p_{i}(1-r_{i})\eta_{\boldsymbol{r}}^{i}.$

Removing a red vertex removes exactly one edge. Hence the number of edges in
the giant component of the vertex-removed graph is the number of edges in the
vertex-exploded graph minus the number of red vertices in the giant component
of the vertex-exploded graph. Now using law of large numbers, as in (3.10), we
get

$e(C_{1}(\boldsymbol{r}^{\scriptscriptstyle(n)}))=e(\tilde{C}_{1})-v_{1}(\tilde{C_{1}})\times\frac{n_{+}}{\tilde{n_{1}}}(1+o_{\scriptscriptstyle\mathbb{P}}(n)).$
(3.13)

Dividing by $n$ and taking limits in probability on both sides of (3.13)
completes the proof of Theorem 17. ∎

######  Proof 3.1 (Proof of Corollary 23)

Let $k^{\scriptscriptstyle(n)}$ be the top $\alpha$-quantile for the degree
distribution $D_{n}$, which has probability mass function $(n_{j}/n)_{j\geq
1}$. Define $\bar{{\boldsymbol{r}}}^{\scriptscriptstyle(n)}(\alpha)$ to be

$\bar{{\boldsymbol{r}}}^{\scriptscriptstyle(n)}(\alpha)=\left(0,0,0,\ldots
0,\frac{n(\alpha-\mathbb{P}(D_{n}>k^{\scriptscriptstyle(n)}))}{n_{k^{\scriptscriptstyle(n)}}},1,1,\ldots\right).$

Due to Theorem 17, it is enough to show that
$(\bar{\boldsymbol{r}}^{\scriptscriptstyle(n)}(\alpha))_{n\geq 1}\in
S(\bar{\boldsymbol{r}}(\alpha))$. This follows by Conditions 1.3.2. The proof
for the bottom $\alpha$-quantile is identical. This completes the proof.

###  3.2 Preliminary bounds

In this section, we prove bounds on the size of the giant in Theorem 28. We
also discuss a bound on $\eta_{\boldsymbol{r}}$, interpreted as the half-edge
extinction probability. Recall from (1.16), $\eta_{\boldsymbol{r}}$ is the
smallest solution in $(0,1]$ of (1.16).

######  Lemma 52 (Lower bound for $\eta_{\boldsymbol{r}}$)

For every $\alpha$-sequence $\boldsymbol{r}$,

$\eta_{\boldsymbol{r}}\geq\frac{\mathbb{E}[Dr_{D}]}{\mathbb{E}[D]}.$ (3.14)

###### Proof 3.2

By (1.16) and (1.17),

$\sum_{j\geq
1}jp_{j}(1-r_{j})\eta_{\boldsymbol{r}}^{j-1}+\mathbb{E}[Dr_{D}]=\eta_{\boldsymbol{r}}\mathbb{E}[D],$

which implies that

$\mathbb{E}[D(1-r_{D})\eta_{\boldsymbol{r}}^{D-1}]=\mathbb{E}[(\eta_{\boldsymbol{r}}-r_{D})D].$

In the above equality, obviously LHS $\geq 0$. Thus, RHS $\geq 0$ as required.

######  Remark 53 (Lower bound for $\eta$ dependent only on $\alpha$)

The lower bound given above is non-trivial, since using $D\geq 1$ a.s. gives

$\eta_{\boldsymbol{r}}\geq\frac{\mathbb{E}[Dr_{D}]}{\mathbb{E}[D]}\geq\frac{\alpha}{\mathbb{E}[D]}>0.$
(3.15)

This lower bound is independent of the $\alpha$-sequence used.
$\blacktriangleleft$

######  Proof 3.3 (Proof of Theorem 28)

By (1.14), Lemma 52 and Remark 53,

$\displaystyle\rho({\boldsymbol{r}})$
$\displaystyle=1-\alpha-2\mathbb{E}[Dr_{D}]\eta_{\boldsymbol{r}}-\sum_{j\geq
1}p_{i}(1-r_{i})\eta_{\boldsymbol{r}}^{i}$ (3.16) $\displaystyle\leq
1-\alpha-2\mathbb{E}[Dr_{D}]\eta_{\boldsymbol{r}}\leq
1-\alpha-\frac{2(\mathbb{E}[Dr_{D}])^{2}}{\mathbb{E}[D]}.$ (3.17)

Since $D\geq 1$ almost surely, we have
$\mathbb{E}[Dr_{D}]\geq\mathbb{E}[r_{D}]=\alpha$. Using this fact in (3.17)
proves (1.24). If the $\alpha$-sequence, $\boldsymbol{r}$, is positively
correlated with the degree sequence, we have
$\mathbb{E}[Dr_{D}]\geq\alpha\mathbb{E}[D]$. Using this fact in (3.17) proves
(1.25). The mean-value theorem implies that there exists
$\zeta\in(\eta_{\boldsymbol{r}},1)$ such that
$1-g_{\boldsymbol{r}}(\eta_{\boldsymbol{r}})=g_{\boldsymbol{r}}^{\prime}(\zeta)(1-\eta_{\boldsymbol{r}})$.
Thus, also using (3.12), we obtain

$\rho({\boldsymbol{r}})=\beta_{\boldsymbol{r}}(1-g_{\boldsymbol{r}}(\eta_{\boldsymbol{r}}))-\mathbb{E}[Dr_{D}](1-\eta_{\boldsymbol{r}})=(\beta_{\boldsymbol{r}}g_{\boldsymbol{r}}^{\prime}(\zeta)-\mathbb{E}[Dr_{D}])(1-\eta_{\boldsymbol{r}}).$
(3.18)

Since $g_{\boldsymbol{r}}(\cdot)$ is a generating function of a non-negative
random variable, $g_{\boldsymbol{r}}^{\prime}(\cdot)$ is an increasing
function, so that

$\frac{\mathbb{E}[D]}{\beta_{\boldsymbol{r}}}\eta_{\boldsymbol{r}}=g_{\boldsymbol{r}}^{\prime}(\eta_{\boldsymbol{r}})\leq
g_{\boldsymbol{r}}^{\prime}(\zeta)\leq
g_{\boldsymbol{r}}^{\prime}(1)=\frac{\mathbb{E}[D]}{\beta_{\boldsymbol{r}}}.$

Substituting this inequality in (3.18), we get

$\mathbb{E}[D(\eta_{\boldsymbol{r}}-r_{D})](1-\eta_{\boldsymbol{r}})\leq\rho({\boldsymbol{r}})\leq\mathbb{E}[D(1-r_{D})](1-\eta_{\boldsymbol{r}}).$
(3.19)

Using the lower bound on $\eta_{\boldsymbol{r}}$ (Lemma 52) in (3.19), we
obtain bound for $\rho(\boldsymbol{r})$, in (1.23). Next, we obtain bound for
$e(\boldsymbol{r})$. By Theorem 17,

$e({\boldsymbol{r}})=\left(\frac{\mathbb{E}[D]}{2}(1+\eta_{\boldsymbol{r}})-\mathbb{E}[Dr_{D}]\right)(1-\eta_{\boldsymbol{r}})=-\frac{\mathbb{E}[D]}{2}\eta_{\boldsymbol{r}}^{2}+\mathbb{E}[Dr_{D}]\eta_{\boldsymbol{r}}+\frac{\mathbb{E}[D]}{2}-\mathbb{E}[Dr_{D}].$

Define the polynomial $P(\cdot)$ by

$P(x):=-\frac{\mathbb{E}[D]}{2}x^{2}+\mathbb{E}[Dr_{D}]x+\frac{\mathbb{E}[D]}{2}-\mathbb{E}[Dr_{D}].$

Note that $P(\cdot)$ is a quadratic polynomial with a negative leading
coefficient. Thus, it is maximal at
$x^{\star}=\mathbb{E}[Dr_{D}]/\mathbb{E}[D]\in(0,1)$. By Lemma 52,

$\eta_{\boldsymbol{r}}\in\left[\frac{\mathbb{E}[Dr_{D}]}{\mathbb{E}[D]},1\right].$

Thus,

$0=P(1)<e({\boldsymbol{r}})=P(\eta_{\boldsymbol{r}})\leq P(x^{\star}).$

This gives (1.23), which completes the proof.

###  3.3 $\varepsilon$-transformations and half-edge extinction probability

In this section, we study the effect of a small perturbation in the
$\alpha$-sequence on the size of the giant after vertex removal. For this we
define the notion of an ‘$\varepsilon$-transformation’ that moves mass to the
left:

######  Definition 54 ($\varepsilon$-transformation)

Suppose ${\boldsymbol{r}}=(r_{j})_{j\geq 1}$ is an $\alpha$-sequence. Fix
$k$,$l$ $\in\mathbb{N}$. We call
${\boldsymbol{r}}^{k,l}(\varepsilon)=(r^{k,l}_{j}(\varepsilon))_{j\geq 1}$ an
$\varepsilon$-transformation on the co-ordinates $(k,k+l)$ if it satisfies
that $r^{k,l}_{i}(\varepsilon)=r_{i}$ for $i\notin\\{k,k+l\\}$, while

$r^{k,l}_{k}(\varepsilon)=r_{k}+\frac{\varepsilon}{p_{k}}\qquad\text{and}\qquad
r^{k,l}_{k+l}(\varepsilon)=r_{k+l}-\frac{\varepsilon}{p_{k+l}}.$ (3.20)

Note that ${\boldsymbol{r}}^{k,l}(\varepsilon)$ is also an $\alpha$-sequence
for $\varepsilon\leq p_{k+l}r_{k+l}.$ Thus, the domain of $\varepsilon$ is
$[0,p_{k+l}r_{k+l}]$. $\blacktriangleleft$

Let $\rho^{k,l}(\varepsilon)$ denote the limiting proportion of vertices in
the giant after the vertex removal procedure according to
${\boldsymbol{r}}^{k,l}(\varepsilon)$.

######  Remark 55 (Supercritical regime)

Throughout this section we assume that we start with the supercritical regime,
i.e., $\nu_{\boldsymbol{r}}>1$, recall $\nu_{\boldsymbol{r}}$ from (1.13).
$\blacktriangleleft$

######  Remark 56 (Graph remains supercritical after
$\varepsilon$-transformation)

Starting in the supercritical regime, the sequence of random graphs remain in
the supercritical regime even after the $\varepsilon$-transformation. In other
words,
$\nu_{\boldsymbol{r}}>1\implies\nu_{\boldsymbol{r}^{k,l}(\varepsilon)}>1.$
Indeed, we can compute that

$\displaystyle\nu_{\boldsymbol{r}^{k,l}(\varepsilon)}$
$\displaystyle=\frac{\mathbb{E}[D(D-1)(1-r_{D}^{k,l}(\varepsilon))]}{\mathbb{E}[D]}$
$\displaystyle=\frac{\mathbb{E}[D(D-1)(1-r_{D})]}{\mathbb{E}[D]}+\frac{k(k-1)(-\varepsilon)+(k+l)(k+l-1)\varepsilon}{\mathbb{E}[D]}>\nu_{\boldsymbol{r}}.$

$\blacktriangleleft$

####  3.3.1 Monotonicity of the half-edge extinction probability

In this section, we investigate the effect of the $\varepsilon$-transformation
on the half-edge extinction probability of the configuration model after
vertex explosion. Let $\tilde{D}$ with probability mass function
$(\tilde{p}_{j})_{j\geq 1}$ be as described in Section 3.1. $\tilde{D}$ was
computed for the $\alpha$-sequence $\boldsymbol{r}$. Let
$\tilde{D}_{\varepsilon}$ be the corresponding $\tilde{D}$ for the
$\alpha$-sequence $\boldsymbol{r}^{k,l}(\varepsilon)$. Let
$g_{\varepsilon}(\cdot)$ and $g(\cdot)$ be the generating functions of
$\tilde{D}_{\varepsilon}$ and $\tilde{D}$, respectively. Let
$\eta_{\varepsilon},\eta\in(0,1)$ satisfy

$\displaystyle
g_{\varepsilon}^{\prime}(\eta_{\varepsilon})=\frac{\mathbb{E}[D]}{\beta_{\varepsilon}}\eta_{\varepsilon}\qquad\text{
and }\qquad g^{\prime}(\eta)=\frac{\mathbb{E}[D]}{\beta}\eta,$ (3.21)

where

$\displaystyle\beta_{\varepsilon}=\mathbb{E}[Dr^{k,l}_{D}(\varepsilon)]+1-\alpha\qquad\text{
and }\qquad\beta=\mathbb{E}[Dr_{D}]+1-\alpha.$ (3.22)

Then $\eta$ and $\eta_{\varepsilon}$ are the half-edge extinction
probabilities in the configuration model with limiting degree distributions
$\tilde{D}$ and $\tilde{D}_{\varepsilon}$, respectively. By the definition of
$r_{D}^{k,l}(\varepsilon)$,

$\mathbb{E}[Dr^{k,l}_{D}(\varepsilon)]=\mathbb{E}[Dr_{D}]-l\varepsilon.$
(3.23)

This means that $\beta_{\varepsilon}=\beta-l\varepsilon$. We can also relate
$g_{\varepsilon}$ and $g$ by noting that

$\displaystyle
g_{\varepsilon}(s)=\mathbb{E}[s^{\tilde{D}_{\varepsilon}}]=\beta_{\varepsilon}^{-1}(\sum_{j\geq
1}$ $\displaystyle
p_{j}(1-r^{k,l}_{j}(\varepsilon))s^{j}+\mathbb{E}[Dr^{k,l}_{D}(\varepsilon)]s),$

so that

$\beta_{\varepsilon}g_{\varepsilon}(s)=\sum_{j\geq
1}p_{j}(1-r_{j})s^{j}+\mathbb{E}[Dr_{D}]s-l\varepsilon
s+\sum_{j\in\\{k,k+l\\}}p_{j}(r_{j}-r^{k,l}_{j}(\varepsilon))s^{j}.$

In turn, this means that

$\beta_{\varepsilon}g_{\varepsilon}(s)=\beta
g(s)-\varepsilon(s^{k}-s^{k+l}+ls).$ (3.24)

Recall that the proportion of vertices in the giant component of the graph
obtained after vertex removal with respect to
$\boldsymbol{r}^{k,l}(\varepsilon)$ is $\rho^{k,l}(\varepsilon)$. By (3.12),

$\rho^{k,l}(\varepsilon)=1-\alpha+(\mathbb{E}[Dr_{D}]-l\varepsilon)\eta_{\varepsilon}-\beta_{\varepsilon}g_{\varepsilon}(\eta_{\varepsilon}).$
(3.25)

Substituting (3.24) into (3.25) gives

$\displaystyle\rho^{k,l}(\varepsilon)=1-\alpha-\beta
g(\eta_{\varepsilon})+\varepsilon(\eta_{\varepsilon}^{k}-\eta_{\varepsilon}^{k+l})+\mathbb{E}[Dr_{D}]\eta_{\varepsilon}.$
(3.26)

The following lemma shows that $\eta_{\varepsilon}$ is well-defined for
$\varepsilon$ such that $\nu_{\boldsymbol{r}^{k,l}(\varepsilon)}>1$:

######  Lemma 57 (Uniqueness)

Let $g(\cdot)$ be the generating function for $D$, let $p_{1}>0$, and let
$\eta\in(0,1]$ satisfy

$g^{\prime}(\eta)=\mathbb{E}[D]\eta,$ (3.27)

Then $\eta$ exists and is unique if
$\nu=\mathbb{E}[D(D-1)]/{\mathbb{E}[D]}>1.$ If $\nu\leq 1$, then $\eta=1$ is
the only solution to (3.27).

The above lemma follows from Janson and Luczak [30, Theorem 2.3]. For
$p_{1}=0$, we define $\eta=0$ instead. Then, $\eta$ can be interpreted as the
extinction probability of a branching process with offspring distribution
$p_{k}^{\star}=(k+1)p_{k}/\mathbb{E}[D]$. The next lemma is needed in the rest
of this section:

######  Lemma 58 (Negative polynomial)

For $s\in(0,1)$,

$(k+l)s^{k+l-1}-ks^{k-1}-l<0.$

###### Proof 3.4

Let $P(x):=(k+l)x^{k+l-1}-kx^{k-1}-l$, then

$P^{\prime}(x)=(k+l)(k+l-1)x^{k+l-2}-k(k-1)x^{k-2}.$

This means that

$P^{\prime}(x)>0\iff x^{l}>\frac{k(k-1)}{(k+l)(k+l-1)}.$

The only minimizer of $P(\cdot)$ in $(0,1)$, denoted by $\gamma$, equals

$\gamma=\left(\frac{k(k-1)}{(k+l)(k+l-1)}\right)^{1/l}.$

Since there is no maximum in the interval $(0,1)$, the maximum occurs either
in $0$ or $1$. We have $P(0)=-l$ and $P(1)=0$, so that $P(x)<0$ for all
$x\in(0,1)$.

In the next lemma, we compute the derivative of $\eta_{\varepsilon}$ with
respect to $\varepsilon$, and show that it is negative:

######  Lemma 59 (Half-edge extinction probability is decreasing in
$\varepsilon$)

Suppose $\nu_{\boldsymbol{r}}>1$. For all $\varepsilon\in[0,p_{k+l}r_{k+l}]$,

$\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}=\frac{(k+l)\eta_{\varepsilon}^{k+l-1}-k\eta_{\varepsilon}^{k-1}-l}{\mathbb{E}[D]-\beta_{\varepsilon}g_{\varepsilon}^{\prime\prime}(\eta_{\varepsilon})}<0.$

###### Proof 3.5

Differentiating (3.24) gives

$\beta_{\varepsilon}g_{\varepsilon}^{\prime}(s)=\beta
g^{\prime}(s)-\varepsilon(ks^{k-1}-(k+l)s^{k+l-1}+l).$ (3.28)

By definition of $\eta_{\varepsilon}$, we have
$\beta_{\varepsilon}g_{\varepsilon}^{\prime}(\eta_{\varepsilon})=\mathbb{E}[D]\eta_{\varepsilon}$.
Thus,

$\beta
g^{\prime}(\eta_{\varepsilon})-\varepsilon(k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1}+l)=\mathbb{E}[D]\eta_{\varepsilon}.$
(3.29)

Define $h\colon\mathbb{R}^{2}\to\mathbb{R}$, as

$h(x,y)=\beta g^{\prime}(x)-y(kx^{k-1}-(k+l)x^{k+l-1}+l)-\mathbb{E}[D]x.$
(3.30)

Due to Lemma 58, for $x\in[0,1)$, we have

$\frac{\partial h(x,y)}{\partial y}=(k+l)x^{k+l-1}-kx^{k-1}-l<0.$ (3.31)

Also, $h(\eta_{\varepsilon},\varepsilon)=0$ for every $\varepsilon>0$. The
implicit function theorem [40, Theorem 9.28] on
$h:\mathbb{R}^{2}\to\mathbb{R}$ implies that
$\varepsilon\mapsto\eta_{\varepsilon}$ is differentiable. Thus, we
differentiate (3.29) with respect to $\varepsilon$, to obtain

$\displaystyle\mathbb{E}[D]\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}=\beta
g^{\prime\prime}(\eta_{\varepsilon})\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}-(k$
$\displaystyle\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1}+l)$
$\displaystyle-\varepsilon\big{(}k(k-1)\eta_{\varepsilon}^{k-2}-(k+l)(k+l-1)\eta_{\varepsilon}^{k+l-2}\big{)}\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon},$

which gives

$\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}=\frac{(k+l)\eta_{\varepsilon}^{k+l-1}-k\eta_{\varepsilon}^{k-1}-l}{\mathbb{E}[D]-\beta
g^{\prime\prime}(\eta_{\varepsilon})+\varepsilon(k(k-1)\eta_{\varepsilon}^{k-2}-(k+l)(k+l-1)\eta_{\varepsilon}^{k+l-2})}.$
(3.32)

Differentiating (3.24) twice w.r.t. $s$, and putting $s=\eta_{\varepsilon}$,
we obtain

$\beta_{\varepsilon}g_{\varepsilon}^{\prime\prime}(\eta_{\varepsilon})=\beta
g^{\prime\prime}(\eta_{\varepsilon})-\varepsilon(k(k-1)\eta_{\varepsilon}^{k-2}-(k+l)(k+l-1)\eta_{\varepsilon}^{k+l-2}).$

This means that

$\beta
g^{\prime\prime}(\eta_{\varepsilon})=\beta_{\varepsilon}g_{\varepsilon}^{\prime\prime}(\eta_{\varepsilon})+\varepsilon(k(k-1)\eta_{\varepsilon}^{k-2}-(k+l)(k+l-1)\eta_{\varepsilon}^{k+l-2}).$
(3.33)

Substituting (3.33) in (3.32), we get

$\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}=\frac{(k+l)\eta_{\varepsilon}^{k+l-1}-k\eta_{\varepsilon}^{k-1}-l}{\mathbb{E}[D]-\beta_{\varepsilon}g_{\varepsilon}^{\prime\prime}(\eta_{\varepsilon})},$
(3.34)

as required. We next show that
$\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}<0$. Let
$h(x)=\beta_{\varepsilon}g_{\varepsilon}^{\prime}(x)-\mathbb{E}[D]x.$ Notice
that $h(\eta_{\varepsilon})=h(1)=0$. By Rolle’s theorem, there exists
$\phi\in(\eta_{\varepsilon},1)$ such that $h^{\prime}(\phi)=0.$ This implies
that

$g_{\varepsilon}^{\prime\prime}(\phi)=\frac{\mathbb{E}[D]}{\beta_{\varepsilon}}.$

Since $g_{\varepsilon}(\cdot)$ is a generating function,
$g_{\varepsilon}^{\prime\prime}(\cdot)$ is increasing, so that

$\beta_{\varepsilon}g_{\varepsilon}^{\prime\prime}(\eta_{\varepsilon})<\beta_{\varepsilon}g_{\varepsilon}^{\prime\prime}(\phi)=\mathbb{E}[D].$

Thus,

$\mathbb{E}[D]-\beta_{\varepsilon}g_{\varepsilon}^{\prime\prime}(\eta)>0,$
(3.35)

which means that (3.34) is a well-defined expression, which means that
$\eta_{\varepsilon}$ is differentiable and the derivative is given by (3.34).
By Lemma 58, the numerator in (3.34) is negative, which completes the proof.

Lemma 59 immediately implies that
$\varepsilon\mapsto\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}$ is
continuous:

######  Corollary 60 (Continuity of the derivative)

Suppose $\nu_{\boldsymbol{r}}>1$.
$\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}$ is a continuous
function.

We next show that the derivative of the half-edge extinction probability is
bounded, which is also a consequence of Lemma 59:

######  Corollary 61 (Bound on the derivative)

Suppose $\nu_{\boldsymbol{r}}>1$. There exists $\psi_{k,l}<0$ such that
$\psi_{k,l}<\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}<0$ for all
$\varepsilon\in[0,p_{k+l}r_{k+l}]$.

###### Proof 3.6

Let $h(\varepsilon)=\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}$.
Notice that $\varepsilon$ can only take values in $[0,p_{k+l}r_{k+l}]$, by the
Definition 54. This means that the domain of function $h(\cdot)$ is compact.
Further by Corollary 60, $h(\cdot)$ is continuous. This means that $h(\cdot)$
is bounded below. By Lemma 59 we already know that $h(\varepsilon)<0$ for all
$\varepsilon$. Thus, there exists $\psi_{k,l}<0$ such that
$\psi_{k,l}<h(\varepsilon)<0$ for all $\varepsilon\in[0,p_{k+l}r_{k+l}]$.

###  3.4 Derivative of vertex/edge limiting proportion in the giant of
$G_{n,\boldsymbol{r}}(\varepsilon)$

In this section, we compute the derivative of the limiting proportion of
vertices $\varepsilon\mapsto\rho^{k,l}(\varepsilon)$ and edges
$\varepsilon\mapsto e^{k,l}(\varepsilon)$ in the giant component in
$G_{n,\boldsymbol{r}}(\varepsilon)$, and show that these derivatives are
positive. In the next proposition, we compute $\frac{\partial
e^{k,l}(\varepsilon)}{\partial\varepsilon}$ and its sign:

######  Proposition 62 (Monotonicity of edge proportion)

Suppose $\nu_{\boldsymbol{r}}>1$. For all $\varepsilon\in[0,p_{k+l}r_{k+l}]$,
and $\alpha$-sequence $\boldsymbol{r}$,

$\frac{\partial
e^{k,l}(\varepsilon)}{\partial\varepsilon}=-\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}\mathbb{E}[D(\eta_{\varepsilon}-r^{k,l}_{D}(\varepsilon))]+l(1-\eta_{\varepsilon})>0.$
(3.36)

###### Proof 3.7

By Theorem 17,

$e^{k,l}(\varepsilon)=\frac{\mathbb{E}[D]}{2}(1-\eta_{\varepsilon}^{2})-(\mathbb{E}[Dr_{D}]-l\varepsilon)(1-\eta_{\varepsilon}).$
(3.37)

Differentiating (3.37) with respect to $\varepsilon$, we obtain

$\displaystyle\frac{\partial e^{k,l}(\varepsilon)}{\partial\varepsilon}$
$\displaystyle=-\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}(\mathbb{E}[D(\eta_{\varepsilon}-r_{D})]+l\varepsilon)+l(1-\eta_{\varepsilon})$
$\displaystyle=-\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}\mathbb{E}[D(\eta_{\varepsilon}-r^{k,l}_{D}(\varepsilon))]+l(1-\eta_{\varepsilon}),$

as required. By Lemma 59,
$\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}<0$. By Lemma 52, for
the $\alpha$-sequence $\boldsymbol{r}^{k,l}(\varepsilon)$,

$\eta_{\varepsilon}\geq\frac{\mathbb{E}[Dr^{k,l}_{D}(\varepsilon)]}{\mathbb{E}[D]}\implies\mathbb{E}[D(\eta_{\varepsilon}-r^{k,l}_{D}(\varepsilon))]>0.$

This completes the proof.

In the next proposition, we compute
$\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}$:

######  Proposition 63 (Derivative of vertex proportion)

Suppose $\nu_{\boldsymbol{r}}>1$. For all $\varepsilon\in[0,p_{k+l}r_{k+l}]$,
and $\alpha$-sequence $\boldsymbol{r}$,

$\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}=-A_{\varepsilon}\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}+B_{\varepsilon},$
(3.38)

where

$\displaystyle
A_{\varepsilon}=\mathbb{E}[D(\eta_{\varepsilon}-r^{k,l}_{D}(\varepsilon))]+(k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1})\varepsilon,$
(3.39) $\displaystyle
B_{\varepsilon}=\eta_{\varepsilon}^{k}(1-\eta_{\varepsilon}^{l})+(k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1})\varepsilon.$
(3.40)

Consequently,

$\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}\Big{|}_{\varepsilon=0}=-\mathbb{E}[D(\eta-
r_{D})]\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}\Big{|}_{\varepsilon=0}+\eta^{k}(1-\eta^{l})>0.$

###### Proof 3.8

Taking a derivative of (3.26) with respect to $\varepsilon$ gives

$\displaystyle\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}$
$\displaystyle=-\beta
g^{\prime}(\eta_{\varepsilon})\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}+\varepsilon(k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1})+(\eta_{\varepsilon}^{k}-\eta_{\varepsilon}^{k+l})+\mathbb{E}[Dr_{D}]\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}$
$\displaystyle=(\mathbb{E}[Dr_{D}]-\beta
g^{\prime}(\eta_{\varepsilon}))\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}+\eta_{\varepsilon}^{k}(1-\eta_{\varepsilon}^{l})+\varepsilon(k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1}).$

Thus,

$\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}=(\mathbb{E}[Dr_{D}]-\beta
g^{\prime}(\eta_{\varepsilon}))\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}+B_{\varepsilon}.$
(3.41)

By (3.29), we have

$\displaystyle\beta g^{\prime}(\eta_{\varepsilon})$
$\displaystyle=\mathbb{E}[D]\eta_{\varepsilon}+\varepsilon(k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1}+l)$
$\displaystyle=A_{\varepsilon}-\mathbb{E}[Dr^{k,l}_{D}(\varepsilon)]+l\varepsilon=A_{\varepsilon}-\mathbb{E}[Dr_{D}].$

Substituting this value in (3.41) proves the claim.

Proposition 63 implies that
$\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}\Big{|}_{\varepsilon=0}>0$.
We next extend this to all $\varepsilon$:

######  Proposition 64 (Monotonicity of vertex proportion)

Suppose $\nu_{\boldsymbol{r}}>1$. For all $\varepsilon\in[0,p_{k+l}r_{k+l}]$,

$\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}>0.$

###### Proof 3.9

By Lemma 52, we have

$\mathbb{E}[D(\eta_{\varepsilon}-r^{k,l}_{D}(\varepsilon))]>0\implies
A_{\varepsilon}>(k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1})\varepsilon,$
(3.42)

where $A_{\varepsilon}$ is as in (3.39). By Lemma 59,
$\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}<0$. Thus, by
Proposition 63 and (3.42),

$\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}>(1-\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon})(k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1})\varepsilon+\eta_{\varepsilon}^{k}(1-\eta_{\varepsilon}^{l}).$

We have $\eta_{\varepsilon}\in(0,1)$. By Lemma 58,
$k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1}>-l.$ This means

$\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}>\eta_{\varepsilon}^{k}(1-\eta_{\varepsilon}^{l})-l\varepsilon(1-\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}).$

Thus,

$\varepsilon<\frac{\eta_{\varepsilon}^{k}(1-\eta_{\varepsilon}^{l})}{l(1-\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon})}\implies\frac{\partial\rho^{k,l}(\varepsilon)}{\partial\varepsilon}>0.$
(3.43)

By Lemma 59 and Remark 53,

$\frac{\alpha}{\mathbb{E}[D]}\leq\eta_{\varepsilon}\leq\eta<1.$

By Corollary 61, we know that there exists $\psi_{k,l}<0$, such that
$\psi_{k,l}<\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}<0.$ Define
$\tau(\boldsymbol{r})$ as

$\tau(\boldsymbol{r}):=\frac{\alpha^{k}(1-\eta)}{\mathbb{E}[D]^{k}l(1-\psi_{k,l})}<\frac{\eta_{\varepsilon}^{k}(1-\eta_{\varepsilon}^{l})}{l(1-\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon})}.$

Thus, $\rho^{k,l}(\varepsilon)$ has a positive derivative in
$(0,\tau(\boldsymbol{r}))$, because of (3.43). If one iterates this on the
$\alpha$-sequence
$\boldsymbol{r}^{\prime}=\boldsymbol{r}^{k,l}(\tau(\boldsymbol{r}))$, we get
that $\rho^{k,l}(\varepsilon)$ has a positive derivative in
$(0,\tau(\boldsymbol{r})+\tau(\boldsymbol{r}^{\prime}))$. Next, we show
$\tau(\boldsymbol{r})\leq\tau(\boldsymbol{r}^{\prime})$. For that we note the
following facts:

  1. 1.

Both $\boldsymbol{r}$ and $\boldsymbol{r}^{\prime}$ have the same $\alpha$,
while $\mathbb{E}[D]$ is a constant.

  2. 2.

We are using the same $k,l$ for both $\varepsilon$-transformations
$\boldsymbol{r}$ and $\boldsymbol{r}^{\prime}$, which means that the exponents
in the expression of $\tau(\cdot)$ are the same.

  3. 3.

$\psi_{k,l}$ depends only on $k$ and $l$, and is thus the same for both cases.

This means that $\tau(\boldsymbol{r})$ and $\tau(\boldsymbol{r}^{\prime})$
differ only because of their dependence on $\eta=\eta(\boldsymbol{r})$ and
$\eta=\eta(\boldsymbol{r}^{\prime})$. Further,
$\varepsilon\mapsto\eta_{\varepsilon}$ is a decreasing function. Thus,
$\tau(\boldsymbol{r}^{\prime})\geq\tau(\boldsymbol{r})$. As a result,
$\rho^{k,l}(\varepsilon)$ has a positive derivative in the neighborhood
$(0,2\tau(\boldsymbol{r}))$. Iterate this to cover the full domain of the
function.

####  3.4.1 Proof of main result

In this section, we prove Theorem 31. We start by showing that we can go from
$\boldsymbol{r}$ to $\boldsymbol{r}^{\prime}$ by using
$\varepsilon$-transformations when
$\boldsymbol{r}^{\prime}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}$:

######  Lemma 65 (Stochastic ordering and $\varepsilon$-transformations)

Let ${\boldsymbol{r}}=(r_{j})_{j\geq 1}$ and
${\boldsymbol{r}}^{\prime}=(r^{\prime}_{j})_{j\geq 1}$ be two
$\alpha$-sequences such that
${\boldsymbol{r}}^{\prime}\preccurlyeq_{\boldsymbol{p}}{\boldsymbol{r}}$. Then
${\boldsymbol{r}}^{\prime}$ can be obtained from ${\boldsymbol{r}}$ through a
series of $\varepsilon$-transformations.

The proof of Lemma 65, which is straightforward yet technically involved, is
deferred to Appendix B. With these tools, we can now prove our main result in
Theorem 31:

######  Proof 3.10 (Proof of Theorem 31)

Recall $\bar{\boldsymbol{r}}(\alpha)$, and
$\underline{\boldsymbol{r}}(\alpha)$ from Definition 22. Let
$\boldsymbol{r}=(r_{i})_{i\geq 1}$ be an arbitrary $\alpha$-sequence. Then, by
definition of stochastic dominance,
$\underline{\boldsymbol{r}}(\alpha)\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}\preccurlyeq_{\boldsymbol{p}}\bar{\boldsymbol{r}}(\alpha).$
By Propositions 62 and 64, the proportion of edges and vertices in the giant
increases after each $\varepsilon$-transformation. Thus, we get the desired
result from Lemma 65.

We next prove Corollary 32, which relies on the following lemma that allows us
to compare $\alpha$-sequences with different $\alpha$’s:

######  Lemma 66 (Stochastic ordering)

Fix $\varepsilon>0$. Suppose $\boldsymbol{r}$ is an $\alpha$-sequence and
$\boldsymbol{r}^{\prime}$ is an $(\alpha+\varepsilon)$-sequence such that
$\boldsymbol{r}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}^{\prime}$. Then
there exists an $\varepsilon$-sequence, say
$\boldsymbol{\delta}=(\delta_{i})_{i\geq 1}$ satisfying
$\boldsymbol{r}+\boldsymbol{\delta}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}^{\prime}$.

The proof of Lemma 66 is again deferred to Appendix B.

######  Proof 3.11 (Proof of Corollary 32)

We know that $\mathbb{E}[r^{\prime}_{D}]\leq\mathbb{E}[r_{D}]$, since
$\boldsymbol{r}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}^{\prime}$.
Furthermore, if $\mathbb{E}[r^{\prime}_{D}]=\mathbb{E}[r_{D}]$, then the
result follows due to Theorem 31. Thus, suppose
$\mathbb{E}[r^{\prime}_{D}]<\mathbb{E}[r_{D}]$, which means that there exists
$\varepsilon>0$ such that
$\mathbb{E}[r_{D}]=\mathbb{E}[r^{\prime}_{D}]+\varepsilon$. By Lemma 66, there
exists an $\varepsilon$-sequence, say $\boldsymbol{\delta}$, such that
$\boldsymbol{r}+\boldsymbol{\delta}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}^{\prime}$.
Notice that both $\boldsymbol{r}+\boldsymbol{\delta}$ and
$\boldsymbol{r}^{\prime}$ are $\alpha$-sequences. Thus, from Theorem 31, we
have
$\rho(\boldsymbol{r}^{\prime})\leq\rho(\boldsymbol{r}+\boldsymbol{\delta})$.
Also, by the definition of vertex removal according to an $\alpha$-sequence,
it follows that
$\rho(\boldsymbol{r}+\boldsymbol{\delta})\leq\rho(\boldsymbol{r})$, because we
are removing $\boldsymbol{\delta}$ proportion more vertices after
$\boldsymbol{r}$-removal in $(\boldsymbol{r}+\boldsymbol{\delta})$-removal.
Thus, we get the desired result.

This work is supported in part by the Netherlands Organisation for Scientific
Research (NWO) through the Gravitation NETWORKS grant no. 024.002.003.

## References

  * [1] Aldous, D. and Steele, J. M. (2004).  The objective method: probabilistic combinatorial optimization and local weak convergence.  In Probability on discrete structures.  vol. 110 of Encyclopaedia Math. Sci. Springer, Berlin pp. 1–72.
  * [2] Anthonisse, J. M. (1971).  The rush in a directed graph.  Stichting Mathematisch Centrum. Mathematische Besliskunde.
  * [3] Avrachenkov, K. and Lebedev, D. (2006).  PageRank of scale-free growing networks.  Internet Math. 3, 207–231.
  * [4] Avrachenkov, K., Litvak, N., Nemirovsky, D. and Osipova, N. (2007).  Monte Carlo methods in PageRank computation: when one iteration is sufficient.  SIAM J. Numer. Anal. 45, 890–904.
  * [5] Banerjee, S. and Olvera-Cravioto, M. (2022).  PageRank asymptotics on directed preferential attachment networks.  Ann. Appl. Probab. 32, 3060–3084.
  * [6] Benjamini, I. and Schramm, O. (2001).  Recurrence of distributional limits of finite planar graphs.  Electron. J. Probab. 6, no. 23, 13.
  * [7] Bianchini, M., Gori, M. and Scarselli, F. (2005).  Inside PageRank.  ACM Trans. Internet Technol. 5, 92–128.
  * [8] Boldi, P., Santini, M. and Vigna, S. (2005).  PageRank as a function of the damping factor.  In Proceedings of the 14th International Conference on World Wide Web.  WWW ’05.  Association for Computing Machinery.  p. 557–566.
  * [9] Boldi, P. and Vigna, S. (2014).  Axioms for centrality.  Internet Math. 10, 222–262.
  * [10] Bollobás, B. (1980).  A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.  European J. Combin. 1, 311–316.
  * [11] Bollobás, B. and Riordan, O. (2015).  An old approach to the giant component problem.  J. Combin. Theory Ser. B 113, 236–260.
  * [12] Borgatti, S. P. (2005).  Centrality and network flow.  Social Networks 27, 55–71.
  * [13] Brin, S. and Page, L. (1998).  The anatomy of a large-scale hypertextual web search engine.  Computer Networks and ISDN Systems 30, 107–117.  Proceedings of the Seventh International World Wide Web Conference.
  * [14] Britton, T., Deijfen, M. and Martin-Löf, A. (2006).  Generating simple random graphs with prescribed degree distribution.  J. Stat. Phys. 124, 1377–1397.
  * [15] Chen, N., Litvak, N. and Olvera-Cravioto, M. (2014).  PageRank in scale-free random graphs.  In Algorithms and models for the web graph.  vol. 8882 of Lecture Notes in Comput. Sci. Springer, Cham pp. 120–131.
  * [16] Chen, N., Litvak, N. and Olvera-Cravioto, M. (2017).  Generalized PageRank on directed configuration networks.  Random Structures Algorithms 51, 237–274.
  * [17] Deijfen, M., Rosengren, S. and Trapman, P. (2018).  The tail does not determine the size of the giant.  Journal of Statistical Physics 173, 736–745.
  * [18] Evans, T. S. and Chen, B. (2022).  Linking the network centrality measures closeness and degree.  Communications Physics 5, 172\.
  * [19] Garavaglia, A., Hofstad, R. v. d. and Litvak, N. (2020).  Local weak convergence for PageRank.  Ann. Appl. Probab. 30, 40–79.
  * [20] Hinne, M. (2011).  Local approximation of centrality measures.  Radboud University Nijmegen, The Netherlands.
  * [21] Hofstad, R. v. d. (2017).  Random graphs and complex networks. Vol. 1.  Cambridge Series in Statistical and Probabilistic Mathematics, [43]. Cambridge University Press, Cambridge.
  * [22] Hofstad, R. v. d. (2021).  The giant in random graphs is almost local.  arXiv:2103.11733 [math.PR].
  * [23] Hofstad, R. v. d. (2023+).  Random Graphs and Complex Networks. Volume 2.  In preparation, see
http://www.win.tue.nl/$\sim$rhofstad/NotesRGCNII.pdf.

  * [24] Hofstad, R. v. d., Hooghiemstra, G. and Van Mieghem, P. (2005).  Distances in random graphs with finite variance degrees.  Random Structures Algorithms 27, 76–123.
  * [25] Hofstad, R. v. d., Hooghiemstra, G. and Znamenski, D. (2007).  Distances in random graphs with finite mean and infinite variance degrees.  Electron. J. Probab. 12, no. 25, 703–766.
  * [26] Hofstad, R. v. d., Hooghiemstra, G. and Znamenski, D. (2007).  A phase transition for the diameter of the configuration model.  Internet Math. 4, 113–128.
  * [27] Janson, S. (2009).  On percolation in random graphs with given vertex degrees.  Electron. J. Probab. 14, no. 5, 87–118.
  * [28] Janson, S. (2009).  The probability that a random multigraph is simple.  Combin. Probab. Comput. 18, 205–225.
  * [29] Janson, S. (2014).  The probability that a random multigraph is simple. II.  J. Appl. Probab. 51A, 123–137.
  * [30] Janson, S. and Luczak, M. J. (2009).  A new approach to the giant component problem.  Random Structures Algorithms 34, 197–216.
  * [31] Jelenković, P. R. and Olvera-Cravioto, M. (2010).  Information ranking and power laws on trees.  Adv. in Appl. Probab. 42, 1057–1093.
  * [32] Lee, J. and Olvera-Cravioto, M. (2020).  PageRank on inhomogeneous random digraphs.  Stochastic Process. Appl. 130, 2312–2348.
  * [33] Leskelä, L. and Ngo, H. (2015).  The impact of degree variability on connectivity properties of large networks.  In Algorithms and models for the web graph.  vol. 9479 of Lecture Notes in Comput. Sci. Springer, Cham pp. 66–77.
  * [34] Litvak, N., Scheinhardt, W. R. W. and Volkovich, Y. (2007).  In-Degree and PageRank: why do they follow similar power laws?  Internet Math. 4, 175–198.
  * [35] Mocanu, D. C., Exarchakos, G. and Liotta, A. (2018).  Decentralized dynamic understanding of hidden relations in complex networks.  Scientific Reports 8, 1571\.
  * [36] Molloy, M. and Reed, B. (1995).  A critical point for random graphs with a given degree sequence.  In Proceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, “Random Graphs ’93” (Poznań, 1993).  vol. 6.  pp. 161–179.
  * [37] Molloy, M. and Reed, B. (1998).  The size of the giant component of a random graph with a given degree sequence.  Combin. Probab. Comput. 7, 295–305.
  * [38] Newman, M. (2018).  Networks.  Oxford University Press, Oxford.  Second edition.
  * [39] Page, L., Brin, S., Motwani, R. and Winograd, T. (1999).  The PageRank citation ranking: Bringing order to the web.  Technical Report 1999-66.  Stanford InfoLab.  Previous number = SIDL-WP-1999-0120.
  * [40] Rudin, W. (1964).  Principles of mathematical analysis second ed.  McGraw-Hill Book Co., New York.
  * [41] Senanayake, U., Piraveenan, M. and Zomaya, A. (2015).  The Pagerank-Index: Going beyond citation counts in quantifying scientific impact of researchers.  PLoS One 10, e0134794.
  * [42] Wei, X., Zhao, J., Liu, S. and Wang, Y. (2022).  Identifying influential spreaders in complex networks for disease spread and control.  Scientific Reports 12, 5550\.

##  Appendix A Stochastic ordering and giant in Configuration Model

In this section, we prove Theorem 40. For that we first show Lemma 68, which
essentially proves Theorem 40 for a small subcase. Lemma 69 finishes the proof
by showing that this was sufficient. First we define
$\varepsilon$-transformations for probability measures:

######  Definition 67 ($\varepsilon$-transformations for probability measures)

Let $\boldsymbol{p}=(p_{i})_{i\geq 0}$ be a probability mass function on the
set of non-negative integers. For $\varepsilon\leq p_{k}$, define

$\boldsymbol{p}(\varepsilon):=(p_{1},p_{2},\ldots,p_{k-1},p_{k}-\varepsilon,p_{k+1},\ldots,p_{k+l-1},p_{k+l}+\varepsilon,p_{k+l+1},\ldots).$

Before moving to our first lemma, we recall that
$\rho_{\scriptscriptstyle\rm{CM}}(\boldsymbol{p})$ is the size of giant in the
configuration model with limiting degree distribution having probability mass
function $\boldsymbol{p}=(p_{i})_{i\geq 1}$. Recall that
$\rho_{\scriptscriptstyle\rm{CM}}(\boldsymbol{p})=1-g_{D}(\eta)$, where $\eta$
satisfies $g^{\prime}_{D}(\eta)=\mathbb{E}[D]\eta$.

###### Lemma 68

For all $\varepsilon\leq p_{k}$,
$\rho_{\scriptscriptstyle\rm{CM}}(\boldsymbol{p})\leq\rho_{\scriptscriptstyle\rm{CM}}(\boldsymbol{p}(\varepsilon)).$

###### Proof A.1

Let $g(\cdot)$ and $g_{\varepsilon}(\cdot)$ be the generating functions
corresponding to $\boldsymbol{p}$ and $\boldsymbol{p}(\varepsilon)$,
respectively. Let $\eta$ and $\eta_{\varepsilon}$ satisfy
$g^{\prime}(\eta)=\mathbb{E}[D]\eta\text{ and
}g_{\varepsilon}^{\prime}(\eta_{\varepsilon})=(\mathbb{E}[D]+l\varepsilon)\eta_{\varepsilon}$.
It is enough to show that $g_{\varepsilon}(\eta_{\varepsilon})\leq g(\eta)$,
since $\rho_{\scriptscriptstyle\rm{CM}}(\boldsymbol{p})=1-g(\eta)$. For this,
we note that

$g_{\varepsilon}(s)=\sum_{i\geq 0}p_{i}(\varepsilon)s^{i}=g(s)-\varepsilon
s^{k}(1-s^{l}).$ (A.1)

Thus, $g_{\varepsilon}(s)\leq g(s)\text{ for all }s\in[0,1].$ As a result, it
is enough to show that $\eta_{\varepsilon}\leq\eta$. We differentiate (A.1)
with respect to $s$ to obtain

$\displaystyle g^{\prime}_{\varepsilon}(s)=g^{\prime}(s)+(k+l)\varepsilon
s^{k+l-1}-k\varepsilon s^{k-1}.$ (A.2)

Substitution of $\eta_{\varepsilon}$ in (A.2) gives

$(\mathbb{E}[D]+l\varepsilon)\eta_{\varepsilon}=g^{\prime}(\eta_{\varepsilon})+(k+l)\varepsilon\eta_{\varepsilon}^{k+l-1}-k\varepsilon\eta_{\varepsilon}^{k-1}.$
(A.3)

Differentiating (A.3) with respect to $\varepsilon$, we get

$\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}=\frac{k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1}+l\eta_{\varepsilon}}{g^{\prime\prime}(\eta_{\varepsilon})-(\mathbb{E}[D]+l\varepsilon)+\varepsilon(k+l)(k+l-1)\eta_{\varepsilon}^{k+l-2}-\varepsilon
k(k-1)\eta_{\varepsilon}^{k-2})}.$ (A.4)

Differentiation of (A.1) twice gives

$g^{\prime\prime}_{\varepsilon}(s)=g^{\prime\prime}(s)-\varepsilon
k(k-1)s^{k-2}+\varepsilon(k+l)(k+l-1)s^{k+l-2}.$ (A.5)

Substituting (A.5) in (A.4) gives

$\frac{\partial\eta_{\varepsilon}}{\partial\varepsilon}=\frac{k\eta_{\varepsilon}^{k-1}-(k+l)\eta_{\varepsilon}^{k+l-1}+l\eta_{\varepsilon}}{g_{\varepsilon}^{\prime\prime}(\eta_{\varepsilon})-(\mathbb{E}[D]+l\varepsilon)}.$
(A.6)

Let $h(x)=g_{\varepsilon}^{\prime}(x)-(\mathbb{E}[D]+l\varepsilon)x$. We know
that $h(\eta_{\varepsilon})=h(1)=0$. Due to Rolle’s theorem, there exists
$\theta\in(\eta_{\varepsilon},1)$ so that $h^{\prime}(\theta)=0$, so that
$g_{\varepsilon}^{\prime\prime}(\theta)=\mathbb{E}[D]+l\varepsilon$. Since
$g_{\varepsilon}^{\prime\prime}(\cdot)$ is an increasing function,
$g_{\varepsilon}^{\prime\prime}(\eta_{\varepsilon})\leq
g_{\varepsilon}^{\prime\prime}(\theta)=\mathbb{E}[D]+l\varepsilon$. Thus,

$\displaystyle
g_{\varepsilon}^{\prime\prime}(\eta)-(\mathbb{E}[D]+l\varepsilon)<0.$ (A.7)

As a result, the denominator in (A.6) is negative. We claim that the numerator
in (A.6) as a polynomial in $\eta$ is always positive.

Let $P(x):=ks^{k-2}-(k+l)s^{k+l-2}+l$. It is enough to show that $P(\cdot)$ is
positive in $(0,1)$. Modifying the proof of Lemma 58, we see that $\gamma$,
the only maximiser of $P(\cdot)$ in $(0,1)$, is given by

$\gamma=\left(\frac{k(k-2)}{(k+l)(k+l-2)}\right)^{1/l}.$

Since there is no minimiser in the interval $(0,1)$, the minimum occurs either
in $0$ or in $1$. We have $P(0)=l$ and $P(1)=0$, so that $P(x)>0$ for all
$x\in(0,1)$. Thus, the right-hand side in (A.6) is always negative. This
completes the proof.

###### Lemma 69

Let $\boldsymbol{p}\preccurlyeq_{\rm{st}}\boldsymbol{q}$. Then
$\boldsymbol{q}$ can be reached from $\boldsymbol{p}$ by a series of
$\varepsilon$-transformations.

###### Proof A.2

Define the sets $I$ and $J$ that partition $\mathbb{N}$ as

$I:=\\{i\in\mathbb{N}\colon p_{i}<q_{i}\\}\qquad\text{and}\qquad
J:=\\{i\in\mathbb{N}\colon p_{i}\geq q_{i}\\}.$ (A.8)

Applying our $\varepsilon$-transformation on $(i,j)$ with
$\varepsilon=\varepsilon_{i,j}$ for all $i\in I$ and $j\in J\cap[i+1,\infty)$
on the $\alpha$-sequence $\boldsymbol{p}$, we obtain the $\alpha$-sequence,
say ${\boldsymbol{p}}_{\varepsilon}$, which satisfies

${\boldsymbol{p}}_{\varepsilon}=\Bigg{(}\Big{(}p_{i}+\sum_{j>i,j\in
J}\varepsilon_{i,j}\Big{)}_{i\in I},\Big{(}p_{j}-\sum_{i<j,i\in
I}\varepsilon_{i,j}\Big{)}_{j\in J}\Bigg{)}.$

Then, ${\boldsymbol{p}}_{\varepsilon}={\boldsymbol{q}}$, if
$(\varepsilon_{i,j})_{(i,j)\in I\times J}$ satisfies

$\displaystyle\sum_{j>i,j\in J}\varepsilon_{i,j}=q_{i}-p_{i}\text{ for all
}i\in I\quad\text{and}\quad\sum_{i<j,i\in
I}\varepsilon_{i,j}=p_{j}-q_{j}\text{ for all }j\in J.$ (A.9)

Thus, it is enough to prove that the solution to (A.9) exists. We construct
this solution recursively to complete this proof. Let
$I=\\{i_{1},i_{2},\ldots\\}$, where $i_{1}=\min I$ and $i_{k}$ is defined
recursively as

$i_{k}=\min I\setminus\\{i_{1},i_{2},\ldots,i_{k-1}\\},$

and the minimum $\min I$ of a set of integers $I$ is its minimal element. Let
$J=\\{j_{1},j_{2},\ldots\\}$, where $j_{1}=\min J$ and $j_{k}$ is defined
recursively as

$j_{k}=\min J\setminus\\{j_{1},j_{2},\ldots,j_{k-1}\\}.$

Notice that $1\in I$ by stochastic domination. We next define some notation to
complete our proof:

######  Notation A.1 (Sums of differences)

Let $s_{0}=t_{0}=0$, and define $s_{n}=\sum_{k=1}^{n}(q_{i_{k}}-p_{i_{k}})$
and $t_{n}=\sum_{k=1}^{n}(p_{j_{k}}-q_{j_{k}}).$

We define $\varepsilon_{i,j}$ recursively to satisfy (A.9) in the following
way: We define $n_{0}=l_{0}=0$. We first prove that there exists $0\leq
n_{1}<j_{1}-1$ such that

$\displaystyle s_{n_{1}}<t_{1}\qquad\text{and}\qquad s_{n_{1}+1}\geq t_{1},$
(A.10)

and there exists $1\leq l_{1}$, such that

$\displaystyle s_{n_{1}}<t_{l_{1}}\qquad\text{and}\qquad s_{n_{1}}\geq
t_{l_{1}+1}.$ (A.11)

Indeed, by stochastic domination,

$s_{j_{1}-1}-t_{1}=\sum_{k=1}^{j_{1}-1}(q_{k}-p_{k})-(p_{j_{1}}-q_{j_{1}})=\sum_{k=1}^{j_{1}}q_{k}-\sum_{k=1}^{j_{1}}p_{k}>0.$

We have $n_{1}+1=\min\\{i\in\mathbb{N}\colon s_{i}\geq t_{1}\\}$, and
$s_{j_{1}-1}\geq t_{1}$. Thus, $n_{1}<j_{1}-1$. Since $j_{1}=\min J$, this
means that $\\{1,2,3,\ldots,j_{1}-1\\}\subset I$. Thus,
$i_{n_{1}}=n_{1}<j_{1}-1$ and $i_{n_{1}+1}=n_{1}+1<j_{1}$. Having obtained
$n_{1}$ and $l_{1}$, we define $\varepsilon_{i,j}$ for $1\leq i\leq
i_{n_{1}+1}$ and $j_{1}\leq j\leq j_{l_{1}+1}$ by substituting $i^{\prime}=0$
in Table 1. This defines $\varepsilon_{i,j}$ for $1\leq i\leq i_{n_{1}+1}$ and
$j_{1}\leq j\leq j_{l_{1}+1}$. Further, we set $\varepsilon_{i,j}=0$ for all
$i>n_{1}+1$ and $j<j_{l_{1}}$.

We next iterate this argument, and prove that, similarly, there exists
$n_{2}>n_{1}$ satisfying

$\displaystyle s_{n_{2}}-s_{n_{1}}<t_{l_{1}+1}-t_{l_{1}}\quad\text{and}\quad
s_{n_{2}+1}-s_{n_{1}}\geq t_{l_{1}+1}-t_{l_{1}},$ (A.12)

and there exists $l_{2}>l_{1}$, such that

$\displaystyle s_{n_{2}}-s_{n_{1}}<t_{l_{2}}-t_{l_{1}}\quad\text{and}\quad
s_{n_{2}+1}-s_{n_{1}}\geq t_{l_{2}+1}-t_{l_{1}}.$ (A.13)

Similarly as before, by stochastic domination, $i_{n_{2}+1}<j_{l_{1}+1}$.
Having gotten $n_{2}$ and $l_{2}$, we define $\varepsilon_{i,j}$ for
$i_{n_{1}+1}\leq i\leq i_{n_{2}+1}$ and $j_{l_{1}+1}\leq j\leq j_{l_{2}+1}$ by
substituting $i^{\prime}=1$ in Table 1.

Table 1: Values of $\varepsilon_{i,j}$ $i$ $j$ | $j_{{l_{i^{\prime}}}+1}$ | $j_{{l_{i}^{\prime}}+2}$ | $\cdots$ | $j_{l_{i^{\prime}+1}}$ | $j_{l_{i^{\prime}+1}+1}$ | . | .
---|---|---|---|---|---|---|---
$i_{n_{i^{\prime}}+1}$ | $s_{n_{i^{\prime}}+1}-t_{l_{i^{\prime}}}$ | 0 | $\cdots$ | 0 | 0 | . | .
$i_{n_{i^{\prime}}+2}$ | $q_{n_{i^{\prime}}+2}-p_{n_{i^{\prime}}+2}$ | 0 | $\cdots$ | 0 | 0 | . | .
$i_{n_{i^{\prime}}+3}$ | $q_{n_{i^{\prime}}+3}-p_{n_{i^{\prime}}+3}$ | 0 | $\cdots$ | 0 | 0 | . | .
. | . | . | $\cdots$ | . | . | . | .
. | . | . | $\cdots$ | . | . | . | .
$i_{n_{i^{\prime}+1}}$ | $q_{n_{i^{\prime}+1}}-p_{n_{i^{\prime}+1}}$ | 0 | $\cdots$ | . | . | . | .
$i_{n_{i^{\prime}+1}+1}$ | $t_{l_{i^{\prime}}+1}-s_{n_{i^{\prime}+1}}$ | $t_{l_{i^{\prime}}+2}-t_{l_{i^{\prime}}+1}$ | $\cdots$ | $t_{l_{i^{\prime}+1}}-t_{l_{i^{\prime}+1}-1}$ | $s_{n_{i^{\prime}+1}+1}-t_{l_{i^{\prime}+1}}$ | 0 | .

We next distinguish different cases, depending on whether $I$ and $J$ are
finite or infinite.

Suppose first that both $I$ and $J$ are infinite sets. In that case the
recursion never stops and we keep on defining $(n_{s},j_{s})$, and, in turn,
$\varepsilon_{i,j}$ for all values of $(i,j)$, hence getting the solution for
(A.9).

Suppose next that one of $I$ or $J$ is finite, then due to stochastic
domination, the set $I$ will have to be the one to be finite. Suppose $\max
I=k$. Then there will exist $m\in\mathbb{N}$ such that $i_{n_{m}+1}=k$. Then
we define $\varepsilon_{i,j}$ in Table 2. To complete the proof, we need to
show

$s_{n_{m}+1}=\lim_{n\to\infty}t_{n}.$ (A.14)

This is because the sum of the $k$th row is
$\lim_{n\to\infty}t_{n}-s_{n_{m}}$. If (A.14) is true, then the $k$th row sum
becomes $q_{k}-p_{k}$, which is as desired in (A.9).

Table 2: Values of $\varepsilon_{i,j}$ $i$ $j$ | $j_{{l_{m-1}}+1}$ | $j_{{l_{m-1}}+2}$ | $\cdots$ | $j_{n}$ | $j_{n+1}$ | $j_{n+2}$
---|---|---|---|---|---|---
$i_{n_{m-1}+2}$ | $q_{n_{1}+2}-p_{n_{1}+2}$ | $0$ | $\cdots$ | $0$ | $0$ | $\cdots$
$i_{n_{m-1}+3}$ | $q_{n_{1}+3}-p_{n_{1}+3}$ | $0$ | $\cdots$ | $0$ | $0$ | $\cdots$
. | . | . | $\cdots$ | . | . | .
. | . | . | $\cdots$ | . | . | .
$i_{n_{m}}$ | $q_{n_{2}}-p_{n_{2}}$ | $0$ | $\cdots$ | $0$ | $0$ | $\cdots$
$k=i_{n_{m}+1}$ | $t_{l_{m-1}+1}-s_{n_{m}}$ | $t_{l_{m-1}+2}-t_{l_{m-1}+1}$ | $\cdots$ | $t_{n}-t_{n-1}$ | $t_{n+1}-t_{n}$ | $\cdots$

Now we show (A.14). Since $I$ and $J$ partition the natural numbers, we have
$I\cup J=\mathbb{N}$ and thus

$\displaystyle\sum_{i\in I\cup J}p_{i}=\sum_{j\in I\cup J}q_{i}=1\text{, so
that }\sum_{i\in I}p_{i}+\sum_{i\in J}p_{i}=\sum_{i\in I}q_{i}+\sum_{j\in
J}q_{j}.$

In turn this implies that

$\sum_{i\in I}(p_{i}-q_{i})=\sum_{j\in J}(q_{j}-p_{j}).$

Notice that, by definition, $\lim_{n\to\infty}t_{n}=\sum_{i\in
I}(p_{i}-q_{i})$ and $s_{n_{m}+1}=\sum_{j\in J}(q_{j}-p_{j})$. This finishes
the proof.

######  Proof A.3 (Proof of Theorem 40)

Lemma 68 and 69 complete the proof.

##  Appendix B Characterization of stochastic ordering in $\alpha$-sequences

In this section, we prove Lemmas 65 and 66. By definition of stochastic
domination,
$\boldsymbol{r}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}^{\prime}\iff\boldsymbol{p}\boldsymbol{r}\preccurlyeq_{st}\boldsymbol{p}\boldsymbol{r}^{\prime}.$
Thus, Lemma 65 follows from Lemma 69. Therefore, we only prove Lemma 66:

######  Proof B.1 (Proof of Lemma 66)

We define our $\varepsilon$-sequence $(\delta_{i})_{i\geq 1}$ recursively.
First, we define

$k_{1}:=\left.\begin{cases}\min\left\\{n\in\mathbb{N}:r^{\prime}_{n}<r_{n}\right\\}&\text{if
the minimum is attained},\\\ \infty&\text{otherwise}.\end{cases}\right.$ (B.1)

We know that $k_{1}>1$, due to
$\boldsymbol{r}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}^{\prime}$. Define
$\delta_{i}=r^{\prime}_{i}-r_{i}$ for each $i<k_{1}$. If $k_{1}=\infty$, we
define $\delta_{i}=r^{\prime}_{i}-r_{i}$ for all $i\in\mathbb{N}$, so that, by
definition of $k_{1}$, $\delta_{i}=r^{\prime}_{i}-r_{i}\geq 0$, and thus it
satisfies the required condition. Suppose instead that $k_{1}<\infty$. Then we
define

$l_{1}=\min\left\\{n>k_{1}:\sum_{i=k_{1}}^{n}p_{i}(r^{\prime}_{i}-r_{i})>0\right\\}.$

Since $\boldsymbol{r}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}^{\prime}$ and
$k_{1}<\infty$, by definition we have
$\sum_{i=k_{1}}^{\infty}p_{i}(r^{\prime}_{i}-r_{i})>0$. As a result, there
exists $m$ such that $\sum_{i=k_{1}}^{m}p_{i}(r^{\prime}_{i}-r_{i})>0$, which
means that the set whose minimum we want to compute is non-empty. By the well
ordering principle for natural numbers, we can conclude that the minimum is
attained and thus, $l_{1}<\infty$. Having obtained that $l_{1}<\infty$, we
define $\delta_{i}$ for all $1\leq i\leq l_{1}$ as

$\delta_{i}:=\left.\begin{cases}r^{\prime}_{i}-r_{i},&\text{for }i<k_{1},\\\
0,&\text{for }k_{1}\leq i<l_{1},\\\
\frac{1}{p_{l_{1}}}\sum_{i=k_{1}}^{l_{1}}(r^{\prime}_{i}-r_{i})p_{i},&\text{for
}i=l_{1}.\end{cases}\right.$ (B.2)

Next we define $k_{2}$, similarly to $k_{1}$, as

$k_{2}:=\left.\begin{cases}\min\left\\{n>l_{1}:r^{\prime}_{n}<r_{n}\right\\}&\text{if
the minimum is attained},\\\ \infty&\text{otherwise}.\end{cases}\right.$ (B.3)

If $k_{2}=\infty$, then we define $\delta_{i}=r^{\prime}_{i}-r_{i}$ for all
$i>l_{1}$ and it again satisfies the required condition. Suppose instead that
$k_{2}<\infty$, then we define $l_{2}$ similarly to $l_{1}$ as

$l_{2}=\min\left\\{n>k_{2}:\sum_{i=k_{2}}^{n}p_{i}(r^{\prime}_{i}-r_{i})>0\right\\}.$

Since $\boldsymbol{r}\preccurlyeq_{\boldsymbol{p}}\boldsymbol{r}^{\prime}$, it
can be shown that the above minimum is always attained and $l_{2}<\infty$. We
define, $\delta_{i}$ for all $k_{2}\leq i\leq l_{2}$ as

$\delta_{i}:=\left.\begin{cases}r^{\prime}_{i}-r_{i}&\text{for }l_{1}\leq
i<k_{2},\\\ 0&\text{for }k_{2}\leq i<l_{2},\\\
\frac{1}{p_{l_{1}}}\sum_{i=k_{1}}^{l_{1}}(r^{\prime}_{i}-r_{i})p_{i}&\text{for
}i=l_{1}.\end{cases}\right.$ (B.4)

We keep on defining $k_{i}$ and $l_{i}$ similarly, unless $k_{i}=\infty$ for
some $i\geq 1$. In this way, we get the desired $\varepsilon$-sequence
iteratively.