# Bond Percolation in Small-World Graphs with Power-Law Distribution

Luca Becchetti
Sapienza Università di Roma
Rome, Italy
<EMAIL_ADDRESS>Andrea Clementi
Università di Roma Tor Vergata
Rome, Italy
<EMAIL_ADDRESS>Francesco Pasquale
Università di Roma Tor Vergata
Rome, Italy
<EMAIL_ADDRESS>Luca Trevisan
Università Bocconi
Milan, Italy
<EMAIL_ADDRESS>Isabella Ziccardi
Università dell’Aquila
L’Aquila, Italy
<EMAIL_ADDRESS>
###### Abstract

_Full-bond percolation_ with parameter $p$ is the process in which, given a
graph, for every edge independently, we keep the edge with probability $p$ and
delete it with probability $1-p$. Bond percolation is motivated by problems in
mathematical physics and it is studied in parallel computing and network
science to understand the resilience of distributed systems to random link
failure and the spread of information in networks through unreliable links.

Full-bond percolation is also equivalent to the _Reed-Frost process_ , a
network version of _SIR_ epidemic spreading, in which the graph represents
contacts among people and $p$ corresponds to the probability that a contact
between an infected person and a susceptible one causes a transmission of the
infection.

We consider _one-dimensional power-law small-world graphs_ with parameter
$\alpha$ obtained as the union of a cycle with additional long-range random
edges: each pair of nodes $(u,v)$ at distance $L$ on the cycle is connected by
a long-range edge $(u,v)$, with probability proportional to $1/L^{\alpha}$.
Our analysis determines three phases for the percolation subgraph $G_{p}$ of
the small-world graph, depending on the value of $\alpha$.

  * •

If $\alpha<1$, there is a $p<1$ such that, with high probability, there are
$\Omega(n)$ nodes that are reachable in $G_{p}$ from one another in
$\mathcal{O}(\log n)$ hops;

  * •

If $1<\alpha<2$, there is a $p<1$ such that, with high probability, there are
$\Omega(n)$ nodes that are reachable in $G_{p}$ from one another in
$\log^{\mathcal{O}(1)}(n)$ hops;

  * •

If $\alpha>2$, for every $p<1$, with high probability all connected components
of $G_{p}$ have size $\mathcal{O}(\log n)$.

Percolation in power-law small-world graphs is well studied in the case of
infinite graphs. In finite graphs, previous work has addressed the long-range
percolation process, in which the ring edges are all preserved with
probability one. The setting of full-bond percolation in finite graphs studied
in this paper, which is the one that corresponds to the network SIR model of
epidemic spreading, had not been analyzed before.

##  1 Introduction

Given a graph $G=(V,E)$ and a probability $p(e)$ associated to each edge $e\in
E$, the _full-bond percolation_ process111We simply write bond percolation
when no confusion arises. on $G$ is the construction of a random subgraph
$G_{p}=(V,E_{p})$ of $G$, called the percolation graph, obtained by selecting
each edge $e\in E$ to belong to $E_{p}$ with probability $p(e)$, independently
of the other edges. Often, the focus is on the homogeneous case in which all
probabilities $p(e)$ are equal to the same parameter $p$. The main questions
of interest in this case are, depending on the choice of $G$ and $p$, what is
the typical size of the connected components of $G_{p}$ and the typical
distances between reachable vertices.

The study of the percolation process originates in mathematical physics [20,
28, 31] and it has several applications in parallel and distributed computing
and network science [1, 12, 19, 13, 18, 25]. For example, the study of network
reliability in the presence of random link failures is equivalent to the study
of the connectivity properties of the percolation graph of the network of
links [18, 22].

The independent cascade is a process that models the spread of information and
the influence of individual choices on others in social networks, and it is
equivalent to a percolation process in a way that we explain next. In the
independent cascade, we have a network $G=(V,E)$, an influence probability
$p(e)$ associated to each edge, and a set $I_{0}\subseteq V$ of network nodes
that initially have a certain opinion222Or hold a certain piece of
information, or perform a certain action, these are all equivalent views that
lead to the same distributed process.. The process evolves over time according
to the following natural local rule: if a node $u$ acquired the opinion at
time $t$, the node $v$ does not have the opinion, and the edge $(u,v)$ exists
in $G$, then node $u$ will attempt to convince node $v$ of the opinion, and it
will succeed with probability $p(u,v)$. All nodes that were successfully
convinced by at least one of their neighbors at time $t$ will acquire the
opinion, and will attempt to convince their neighbors at time $t+1$ and so on.
The independent cascade is studied in [19], where the problem of interest is
to find the most “influential” initial set $I_{0}$. The resulting epidemic
process is shown in [19] to be equivalent to percolation in the following
sense: the distribution of nodes influenced by $I_{0}$ in the independent
cascade process has the same distribution as the set of nodes reachable from
$I_{0}$ in the percolation graph of $G$ derived using the probabilities $p(e)$
(this important equivalence and its useful consequences are presented in
Appendix A).

The _Reed-Frost_ process is one of the simplest and cleanest models of
_Susceptible-Infectious-Recovered_ (_SIR_) epidemic spreading on networks [30,
32]. This process is identical to independent cascade with a fixed probability
$p(e)=p$ for all edges $e$. We can interpret nodes that acquired the opinion
in the previous step as Infectious nodes that can spread the disease/opinion,
nodes that do not have the disease/opinion as nodes Susceptible to the
infection, and nodes that acquired the disease/opinion two or more steps in
the past as Recovered nodes that do not spread the disease any more and are
immune to it. The probability $p$ corresponds to the probability that a
contact between an infectious person and a susceptible one causes a
transmission of the disease from the former to the latter. The set $I_{0}$ is
the initial set of infectious people at time $0$. This process, being
equivalent to independent cascade, is also equivalent to percolation [19]: the
distribution of nodes that are infected and eventually recover in the Reed-
Frost process is the same as the distribution of the set of nodes reachable
from $I_{0}$ in the percolation graph of $G$ derived using the probabilities
$p(e)$. Furthermore, the distribution of nodes that are infectious at time $t$
is precisely the distribution of nodes at distance $t$ from $I_{0}$ in the
percolation graph (see Appendix A and [11]).

We are interested in studying full-bond percolation (and hence reliability
under random link failure, independent cascade, and Reed-Frost epidemic
spreading) in one-dimensional small-world graphs with power-law distribution
of edges. We shall now explain what each of these terms mean. Small-world
graphs are a collection of generative models of graphs, designed to capture
certain properties of real-life social networks [13, 30] and communication
networks [17]. In the model introduced by Watts and Strogatz [33], the network
is obtained as a one-dimensional or two-dimensional lattice in which certain
edges are re-routed to random destinations. In a refined model introduced by
Kleinberg [10, 13], a possible edge between two nodes at distance $L$ in the
lattice exists with probability proportional to $L^{-\alpha}$, where the
exponent $\alpha$ is a parameter of the model.

We study full bond percolation in a variant of Kleinberg’s model that has
already been adopted in several previous papers [4, 6, 10, 13, 21, 30] to
study bond percolation and epidemic processes: a _one-dimensional power-law
small-world graph_ with exponent $\alpha$ is the union of a cycle with a
collection of random edges, that we call bridges. For each pair of vertices
$(u,v)$ that are at distance $L\geqslant 2$ on the cycle, the edge $(u,v)$ is
chosen to be part of the graph with probability proportional to $L^{-\alpha}$.
The choices for different pairs are mutually independent333This is the main
difference with respect to Kleinberg’s model, in which the edges are not
mutually independent. and we choose the factor of proportionality so that on
average each vertex has one of the random edges incident on it (so that the
overall average degree of the graph is 3, counting the cycle edges). This
variant of small-world graphs has been adopted, for instance, to discover
structural key-properties that determine the performances of some important
diffusion and navigation problems in real networks [34].

Before proceeding with a statement of our results, we formally define our
generative model for future reference.

######  Definition 1.1 (1-D power-law small-world graphs).

For every $n\geqslant 3$ and $\alpha>0$, a random graph $G=(V,E)$ with
$V=\\{0,\dots,n-1\\}$ is sampled according to the distribution
$\mathcal{SW}(n,\alpha)$ if $E=E_{1}\cup E_{2}$, where: $(V,E_{1})$ is a cycle
and its edges are called _ring-edges_ , and, for each pair of non-adjacent
vertices $u,v\in V$, the _bridge_ $(u,v)$ is included in $E_{2}$
independently, with probability

$\mathbf{Pr}\left((u,v)\in
E_{2}\right)=\frac{1}{d(u,v)^{\alpha}}\cdot\frac{1}{C(\alpha,n)},$

where $d(\cdot,\cdot)$ is the shortest-path distance in the ring and
$C(\alpha,n)$ is the normalizing constant444Note that $C(n,\alpha)$ is not,
strictly speaking, a constant, but rather a normalizing factor that depends on
both $\alpha$ and $n$. It is always upper bounded by an absolute constant
across the entire range of $\alpha$, while it falls within an interval bounded
by two constants when $\alpha>1$. For the sake of conciseness, abusing
terminology we write “constant” instead of normalizing factor.

$C(\alpha,n)=2\sum_{x=2}^{n/2}\frac{1}{x^{\alpha}}\,.$

The process of long-range percolation on finite power-law small-world graphs
is the variant of the percolation process applied to the generative model
described above in which ring edges are preserved with probability one. The
resulting percolation graphs are always connected, and the main question of
interest is their diameter. Long-range percolation in power-law small-world
graph distributions is well understood, and the one-dimensional case is
studied in [4, 21, 33]. In particular, [4] provide bounds on the diameter and
on the expansion of such graphs as a function of the power-law exponent
$\alpha$. Such results have been then sharpened and generalized to multi-
dimensional boxes in [7]. The long-range percolation process, however, is not
a realistic generative model for epidemiological processes, because even the
most contagious diseases, including Ebola, do not have $100\%$ probability of
spreading through close contacts (see [26, 29, 30] for a discussion of this
point).

Full-bond percolation in power-law small-world graphs has been studied in the
case of infinite lattices, including the one-dimensional case that is the
infinite analog of the model that we study in this paper. In the infinite
case, the main questions of interest, which are studied in [6], are whether
the percolation graph has an infinite connected component and, given two
vertices, what is their typical distance in the percolation conditioned on
them both being in the infinite component, as a function of their distance in
the lattice. Although there are similarities, techniques developed to study
infinite percolation graphs do not immediately apply to the finite case,
particularly when one of the technical goals is to obtain rigorous results in
concentration.

In this paper, we study full-bond percolation in power-law small-world graphs,
a key question left open by previous research. The rest of this paper is
organized as follows. Section 2 provides an overview of our results and
techniques we use. A more extensive review of previous work is given in
Section 3. Section 4 introduces notation and some key preliminary notions,
while Sections 5, 6 and 7 provide the full analysis of full-bond percolation
in one-dimensional power-law, small-world graphs. Finally, the proofs of some
technical results are presented in the appendix.

##  2 Our Contribution

Previous work on full-bond percolation in power-law small-world infinite
graphs and on long-range percolation in power-law small-world finite graphs
identified three phases for the value of $\alpha$. Infinite graphs exhibit an
infinite connected component after full-bond percolation when $\alpha<2$ and
no infinite connected component when $\alpha>2$; furthermore distances within
the infinite component scale differently in the $\alpha<1$ versus the
$1<\alpha<2$ case. Finite graphs remain connected under long-range percolation
(because the ring-edges are not subject to percolation), but distances scale
differently in the $\alpha<1$, in the $1<\alpha<2$ and the $\alpha>2$ case. We
postpone a fuller discussion of previous work in these models to Section 3.

Our analysis of the full-bond percolation process on power-law small-world
finite graphs shows that the process exhibits different behaviours in the same
three phases. The behaviors are of a somewhat different kind than in previous
work. In the $\alpha<2$ case, we find, for $p$ sufficiently large, a connected
component of size $\Omega_{\alpha}(n)$, which is best possible, and in the
$\alpha>2$ case we show that all connected components have size
$\mathcal{O}_{\alpha}(\log n)$. Furthermore, when $\alpha<1$, we identify
$\Omega_{\alpha}(n)$ vertices all reachable from each other in
$\mathcal{O}_{\alpha}(\log n)$ steps, and when $1<\alpha<2$ we identify
$\Omega_{\alpha}(n)$ vertices all reachable from each other in
$\mathcal{O}(\log^{\mathcal{O}_{\alpha}(1)}(n))$ steps.

Our analysis is fully rigorous and the obtained results hold _with high
probability_ 555As usual, we say that an event $E$ holds with high probability
if a constant $\gamma>0$ exists such that $\mathbf{Pr}\left(E\right)\geqslant
1-n^{-\gamma}$. (for short, _w.h.p._).

The three phases are characterized by sharply different distributions of the
typical length (measured according to the ring metric) of the bridges. To
gauge the difference, consider the expectation, for a fixed vertex, of the sum
of the lengths (in ring metric) of the bridges incident on the vertex, and
call this expectation $BL_{\alpha,n}$.

When $\alpha<1$, we have that $BL_{\alpha,n}$ is linear in $n$. When
$1<\alpha<2$, then $BL_{\alpha,n}$ is of the form $O(n^{2-\alpha})$, going to
infinity with $n$, but sublinearly in $n$. Finally, when $\alpha>2$,
$BL_{\alpha,n}$ is a constant that depends only on $\alpha$ and is independent
of $n$. Nodes have, in expectation, only one bridge, so $BL_{\alpha,n}$ is an
indication of how much we can advance on the ring by following one bridge.

When $\alpha<1$, the bridges are basically as good as random edges, and we
would expect a giant component to emerge even after full-bond percolation, if
$p$ is large enough. When $\alpha>2$, the bridges behave like a constant
number of ring-edges, and we would not expect a large component when $p<1$.
The case $1<\alpha<2$ is the one for which it is hardest to build intuition,
and the fact that the bridges have typically length of the form
$n^{1-\Omega(1)}$ might suggest that it would take $n^{\Omega(1)}$ steps to
reach antipodal nodes.

Previous work on long-range percolation had established a polylogarithmic
diameter bound in the model in which ring-edges are not subject to
percolation. In that model, all pairs of nodes are reachable in a
polylogarithmic number of steps even though the typical bridge has length
$n^{1-\Omega(1)}$, and this suggests that the shortest path structure is such
that a small number of long bridges is used by several shortest paths. One
thus would expect such a structure to be sensitive to full-bond percolation,
and indeed the proof of [4] relies on the deterministic presence of the ring-
edges.

Instead, we prove that, when $1<\alpha<2$, w.h.p, most pairs of nodes are
reachable from one another in a polylogarithmic number of hops after the full-
bond percolation process.

### Our results

We next provide the analytical results for each of the three regimes.

When $\alpha>2$, we show that the percolation graph $G_{p}$, for every
possible percolation probability $p<1$, has w.h.p. all connected components of
size at most $\mathcal{O}(\log n)$ and of small ring-diameter.

######  Theorem 2.1 (Case $\alpha\in(2,+\infty)$).

Let $\alpha>2$ be a constant and $p<1$ a percolation probability. Sample a
graph $G=(V,E)$ from the $\mathcal{SW}(n,\alpha)$ distribution and let $G_{p}$
be the percolation graph of $G$ with percolation probability $p$. The
following holds:

  1. 1.

W.h.p., the connected components of $G_{p}$ have size at most
$\mathcal{O}(\log n)$;

  2. 2.

For each node $v\in V$ and for any sufficiently large $\ell$, with probability
$1-\Omega(\ell^{-(\alpha-2)/2})$, every node connected to $v$ in $G_{p}$ Is at
ring-distance no larger than $\mathcal{O}(\ell^{2})$ from $v$.

From an epidemiological point of view, this first regime is thus characterized
by a negligible chance to observe an outbreak according to the Reed-Frost
process, even in the presence of a large number (say some small root of $n$)
of initial infected nodes (i.e. sources). In particular, the second claim of
the theorem above strongly bounds the possible infected area of the ring
graph.

The following case, determined by the range $1<\alpha<2$, shows the most
interesting behaviour.

######  Theorem 2.2 (Case $\alpha\in(1,2)$).

Let $\alpha\in(1,2)$ be a constant and $p$ a percolation probability. Sample a
graph $G=(V,E)$ from the $\mathcal{SW}(n,\alpha)$ distribution and let $G_{p}$
be the percolation graph of $G$ with percolation probability $p$. Then,
constants $\underline{p},\overline{p}\in(0,1)$ (with
$\underline{p}\leqslant\overline{p}$) exist such that the following holds:

  1. 1.

If $p>\overline{p}$, w.h.p., there exists a set of $\Omega(n)$ nodes that
induces a connected sub-component in $G_{p}$ with diameter
$\mathcal{O}(\mathrm{polylog}(n))$;

  2. 2.

If $p<\underline{p}$, w.h.p. all the connected components of $G_{p}$ have size
$\mathcal{O}(\log n)$.

The first claim above implies that, if $p$ is sufficiently large (but still a
constant smaller than $1$), then, there is a good chance that few source nodes
are able to infect a large (i.e. $\Omega(n)$) number of nodes and,
importantly, this outbreak takes place at an almost exponential speed.

Finally, when $\alpha<1$, we show the emergence of a behaviour similar to that
generated by one-dimensional small-world models with bridges selected
according to the Erdős-Rényi distribution [3, 27].

######  Theorem 2.3 (Case $\alpha\in(0,1)$).

Let $\alpha\in(0,1)$ and $p$ a percolation probability. Sample a graph
$G=(V,E)$ from the $\mathcal{SW}(n,\alpha)$ distribution and let $G_{p}$ be
the percolation graph of $G$ with percolation probability $p$. Then, constants
$\overline{p},\underline{p}\in(0,1)$ (with
$\underline{p}\leqslant\overline{p}$) exist, such that the following holds:

  1. 1.

If $p>\overline{p},$ w.h.p., there exists a set of $\Omega(n)$ nodes that
induces a connected sub-component in $G_{p}$ with diameter $\mathcal{O}(\log
n)$. Moreover, for a sufficiently large $\beta>0$, for any subset $S\subseteq
V$ of size $|S|\geqslant\beta\log n$, the subset of nodes within distance
$\mathcal{O}(\log n)$ in $G_{p}$ from $S$ has size $\Omega(n)$, w.h.p.

  2. 2.

If $p<\underline{p}$, w.h.p. all the connected components of $G_{p}$ have size
$\mathcal{O}(\log n)$.

In this last case, the presence of a sparse subset of relatively-long random
bridges implies, above the probability threshold, that a few (i.e.
$\Omega(\log n)$) sources w.h.p. generate a large outbreak at exponential
speed.

### Technical contribution: an overview

The analysis techniques we use, like our main results, differ as the parameter
$\alpha$ varies. We recall that $G_{p}$ is the percolation graph of $G$,
sampled from the $\mathcal{SW}(n,\alpha)$ distribution.

When $\alpha>2$, we show that each component of the percolation graph $G_{p}$
has w.h.p. at most $\mathcal{O}(\log n)$ nodes. To prove this fact, we need to
cope with the complex “connectivity” of $G_{p}$ yielded by the percolation of
both ring-edges and the random bridges. To better analyze this structure, we
introduce the notion of _$\ell$ -graph_ $G_{p}^{(\ell)}$ of $G_{p}$, where
$\ell$ is any fixed integer $\ell>0$. This new graph $G_{p}^{(\ell)}$ is in
turn a one-dimensional small-world graph of $n/\ell$ “supernodes”. It is
defined by any fixed partition of $V$ of disjoint ring intervals, each of them
formed by $\ell$ nodes: such $n/\ell$ intervals are the nodes, called _super-
nodes_ , of $G_{p}^{(\ell)}$. The set of edges of $G_{p}^{(\ell)}$ is formed
by two types of random links: the _super-edges_ that connect two adjacent
super-nodes and the _super-bridges_ connecting two non adjacent super-nodes of
the $n/\ell$-size ring (for the formal definition of $G_{p}^{(\ell)}$ see
Definition 5.3). We then prove that, for any $\alpha>2$ and any $p<1$, each
super-node of this graph has:

  1. 1.

Constant probability to have no neighbors (for every value of $\ell$);

  2. 2.

Probability $\mathcal{O}(1/\ell^{\alpha-2})$ to be incident to a super-bridge.

We then design an appropriate BFS visit of $G_{p}^{(\ell)}$ (see Algorithm 1
in Section 5) that keeps the role of super-edges and super-bridges well-
separated. In more detail, starting from a single super-node s, we show that
the number of super-nodes explored at each iteration of the visit turns out to
be dominated by a branching process having two distinct additive
contributions: one generated by the new, visited percolated super-edges and
the other generated by the new, visited percolated super-bridges. Special care
is required to avoid too-rough redundancy in counting possible overlapping
contributions from such two experiments. Then, thanks to Claims 1 and 2 above,
we can prove that, for $\ell=\mathcal{O}(1)$ sufficiently large, w.h.p. this
branching process ends after $\mathcal{O}(\log n)$ steps, and this proves that
the connected component of s in $G_{p}^{(\ell)}$ has $\mathcal{O}(\log n)$
super-nodes. We also remark that our approach above also implies the following
interesting result: with probability $1-\mathcal{O}(1/\ell^{\alpha-2})$, all
super-nodes connected to $v$ are at ring distance at most $\ell$ from $v$.
This implies that, for each node $s$, the nodes in the connected component of
$s$ in $G_{p}$ are within ring distance $\mathcal{O}(\ell^{2})$ from $s$, with
the same probability.

When $1<\alpha<2$, we make a different analysis, based on a suitable inductive
interval partitioning of the initial ring. In this case, our technique is
inspired by the partitioning method used in [28] and [4]. However, though the
high level idea is similar, our analysis needs to address technical challenges
that require major adjustments. In particular, the analysis of [28] only
addresses and relies upon properties of infinite one-dimensional lattices with
additional long-range links, applying Kolmogorov 0-1 law to the tail event of
percolation. On the other hand, [4] borrows from and partly extends [28] to
the finite case, proving a result similar to ours for finite one-dimensional
lattices, but with important differences both in the underlying percolation
model and in the nature of the results they obtain. As for the first point, in
their model, ring-edges are deterministically present, while only long-range
edges (what we call bridges in this paper) are affected by percolation. In
contrast, in our model, _all_ edges are percolated to obtain a realization of
$G_{p}$. Consequently, the graph is deterministically connected in [4], while
connectivity is something that only occurs with some probability in our
setting. In particular, we face a subtler challenge, since we need to show the
existence of a connected component that both spans a constant fraction of the
node _and_ has polylogarithmic diameter666As an example, we might have a
connected component including a constant fraction of the nodes and linear
diameter, containing a smaller connected component, still spanning a constant
fraction of the nodes, but of polylogarithmic diameter. . Moreover, their
result for the diameter of the percolated graph only holds with probability
tending to $1$ in the limit, as the number of nodes grows to infinity, while
we are able to show high probability.

We next provide a technical overview of our approach, highlighting the main
points of the proof in which our percolation model requires a major departure
from the approach of [4].

Similarly to [4], we consider a diverging sequence $\\{N_{k}\\}_{k}$ and for
each $k$ we consider in $G_{p}$ an interval of length $N_{k}$ consisting of
adjacent nodes on the ring. Departing from [4], we then prove that each
interval of size $N_{k}$ contains a constant fraction
$(1-\varepsilon_{k})N_{k}$ of nodes, that induces a connected component of
diameter $D_{k}$, with probability $1-\delta_{k}$, considering only edges
_internal_ to the interval and were $\varepsilon_{k}$ and $\delta_{k}$ are
suitable constants that only depend on $k$, $p$ and $\alpha$. To prove this
fact, for each $k$, we consider an arbitrary interval $I_{k}$ of size $N_{k}$
and we proceed inductively as follows:

  1. 1.

We divide $I_{k}$ in $N_{k}/N_{k-1}$ smaller intervals of size $N_{k-1}$;

  2. 2.

We assume inductively that each of these intervals contains
$(1-\varepsilon_{k-1})N_{k-1}$ nodes that induces a connected component of
diameter $D_{k-1}$, with probability $1-\delta_{k-1}$;

  3. 3.

With a concentration arguments, we prove that a constant fraction of the
intervals in which we divide $I_{k}$ have the above property, with probability
that increases with $k$ (we call these intervals _good_);

  4. 4.

We consider all good intervals of the previous point, and we prove that all
these intervals are connected to each other with probability increasing in
$k$.

The above reasoning therefore implies, for some $\varepsilon_{k}$, the
existence of a fraction $(1-\varepsilon_{k})N_{k}$ of nodes in $I_{k}$, that
with increasing probability in $k$, induce a connected component of diameter
$D_{k}=2D_{k}+1$. More details about the sequences $N_{k},\varepsilon_{k}$ and
$\delta_{k}$ can be found in the full proof. As mentioned earlier, our proof
needs to specifically address percolation of both ring-edges and bridges. This
in particular, means tackling points (2) - (4) above, which is a major
challenge not present in [4] and is taken care of in the technical Lemma 6.3
and in the proof of the main Lemma 6.1 itself. In particular, considering only
edges internal to the interval is very important, since, in this way, the
events denoting the connection of disjoint intervals are independent. The
recurrence of the diameter derives from the fact that the path connecting two
nodes $u$ and $v$ in $I_{k}$ consists of the following three sub-paths:

  1. 1.

The first part has length at most $D_{k}$, and it is a path in the
aforementioned “good” interval of size $(1-\varepsilon_{k-1})N_{k-1}$
containing $u$;

  2. 2.

The second part consist of a single edge, connecting the good interval
containing $u$ with the good interval of $v$;

  3. 3.

The third has length at most $D_{k}$, and is a path of the good interval of
size $(1-\varepsilon_{k-1})N_{k-1}$ containing $v$.

Finally (Lemma 6.1), we consider $k$ such that $N_{k}=\Omega(n)$. For such
$k$, we prove that

$\delta_{k}=\mathcal{O}(1/n^{\varepsilon}),\quad\varepsilon_{k}\ll 1,\quad
D_{k}=\mathrm{polylog}(n),$

so this implies the existence in $G_{p}$ of $\Omega(n)$ nodes inducing a
connected component with diameter $\mathrm{polylog}(n)$, w.h.p.

When $\alpha<1$, we notice that every bridge-edges $(u,v)$ is in $G_{p}$ with
probability at least $pc/n$, for some constant $c$. This reduces our problem
to the analysis of the percolation graph $H_{p}$ of a graph $H$, where $H$ is
the union of a ring and an Erdős-Rényi graph $\mathcal{G}_{n,q}$. [3] contains
a detailed analysis of this case, and we use their results to prove that
$G_{p}$, for any sufficiently large $p$, contains a connected component with
diameter $\mathcal{O}(\log n)$.

We finally remark that, for every value $\alpha$, when $p<1/3$ the connected
components of $G_{p}$ have at most $\mathcal{O}(\log n)$ nodes. This fact easy
follows from concentration techniques, and the fact that every node in $G_{p}$
has expected degree at most $3$.

##  3 Related work

As discussed in the previous sections, variants of bond-percolation have been
investigated in different areas, including computer and network science,
mathematical physics, and epidemiology. In the rest of this section, we only
discuss rigorous analytical results that are most related to our work.

### Small-world graphs

#### Power-law graphs.

As we briefly discussed in the introduction, a number of variants were
considered in previous work, differing in key aspects. E.g., whether the graph
has infinite size (e.g., $\mathbb{Z}^{d}$) or bounded size, the dimension $d$
of the underlying lattice/torus and, very importantly, whether bond-
percolation is applied to all edges (_full-bond percolation_) or only to a
subset of long-range edges (_long-range bond percolation_).

Long-range percolation in finite small-world graphs with power-law bridge
distributions was investigated in [4, 21, 33] in the one-dimensional case. In
particular, [4] provides bounds on the diameter and on the expansion of the
augmented ring as a function of the power-law exponent $\alpha$. These results
have been then sharpened and generalized to multi-dimensional boxes by Biskup
in [7]. These results are consistent with the three regimes we characterize in
this paper for the full-bond percolation process. However, none of our results
can be derived from these previous results because of a crucial aspect we
discussed in the previous section: in long-range percolation models, the
percolation graph is deterministically connected and arguments of the works
above, showing upper bounds on the diameter, strongly rely on the existence of
sub-paths including that include deterministic grid edges. Importantly, such
previous analyses leave open the key question of whether or not, in the range
$\alpha<2$, full-percolation can still result (for suitable values of the
percolation probability $p$) in the emergence of a large connected subgraph of
small diameter: an affirmative answer to this question and its consequences
are in fact one of the main novelties of our work. On the other hand, lower
bounds on the diameter of the connected component given in [4, 7] do not
exclude the existence of a large connected component of smaller diameter and,
thus, a potential epidemic outbreaks. Finally, the bounds given in [4, 7], are
not proved in “concentration” (i.e., w.h.p.).

As for full-bond percolation on infinite graphs, [6] studies infinite lattices
of any dimension $d$ augmented with long-range bridges selected according to a
class of distributions that includes power-laws. In more detail, they derive
bounds on the “typical distance” between any two points of the grid that are
consistent with our results for finite graphs. However, as discussed in the
previous section, their argument to prove both upper and lower bounds on the
typical distance (and, so, on the diameter of any induced subgraph) does not
extend to finite graphs. Moreover, no explicit bounds on the confidence
probability of their bounds can be derived as a functions of the size of the
induced subgraphs, which is a major technical goal in the finite setting.

#### Other models of small-world graphs.

[3] studies a small-world model resulting from a cycle augmented with a subset
of bridge edges sampled from the Erdős-Rényi distribution $\mathcal{G}_{n,q}$.
They provide a sharp threshold for the percolation probability $p$ as a
function of the bridge-probability parameter $q$. As remarked in Subsection 2,
our analysis for the case $\alpha<1$ relies on some technical results from
[3], since in this case, the distribution of bridges is very close to
$\mathcal{G}_{n,q}$, for a suitable choice of the parameter $q$.

A further analysis of the percolation process in [3] considers the case in
which the graph consists of a cycle and a random perfect matching. Also for
this regular case, the authors prove a sharp threshold for the percolation
probability $p$: it turns out that this threshold is smaller than the one for
the Erdős-Rényi small-world graphs when $q$ is chosen, so as to yield the same
expected number of bridges.

Bond percolation on the class of $1$-dimensional small-world networks (that
is, graphs obtained as the union of a cycle and of randomly chosen edges) has
been studied in [27]: using numerical approximations on the moment generating
function, non-rigorous bounds on the critical threshold have been derived
while analytical results are given neither for the expected size of the number
of infected nodes above the transition phase of the independent-cascade
process nor for the infection time. Further non-rigorous results on the
critical points of several classes of complex networks have been derived in
[25, 23] (for good surveys see [30, 32]).

### Other classes of graphs

In [14], for a symmetric, connected graph $G=(V,E)$, Draief et al prove a
general lower bound on the critical point in terms of spectral properties.
Further versions of such bounds for special cases have been subsequently
derived in [23, 24]. We remark here that such approaches are not useful to
discover different behaviours depending on the value $\alpha$ in our model.

A fundamental and rigorous study of bond percolation in random graphs has been
proposed by Bollobás et al in [8]. They establish a coupling between the bond
percolation process and a suitably defined branching process. In the general
class of inhomogenous Erdős-Rényi random graphs, calling $Q=\\{q_{u,v}\\}$ the
edge-probability matrix, they derived the critical point (threshold) of the
phase transition and the size of the giant component above the transition. The
class of inhomogeneous random graphs to which their analysis applies includes
generative models that have been studied in the complex network literature.
For instance, a version of the Dubin’s model [16] can be expressed in this
way, and so can the _mean-field scale-free model_ [9], which is, in turn,
related to the Barabási–Albert model [2], having the same individual edge
probabilities, but with edges present independently. Finally, we observe that
the popular CHKNS model introduced by Callaway et al [10] can be analyzed
using an edge-independent version of this model. Indeed, they consider a
random graph-formation process where, after adding each node, a Poisson number
of edges is added to the graph, again choosing the endpoints of these edges
uniformly at random. For all such important classes of random graph models,
they show tight bounds for the critical points and the relative size of the
giant component beyond the phase transition.

In our setting, if we sample a graph from $\mathcal{SW}(n,\alpha)$ and then
consider the percolation graph $G_{p}$, the distribution of $G_{p}$ is that of
an inhomogenous Erdős-Rényi graph in which the cycle edges have probability
$p$ and each bridge $(x,y)$ has probability $\sim p\cdot 1/d(x,y)^{\alpha}$.

We observe that the results of [8] to the inhomogenous random graph equivalent
to the above percolation graph do not lead to tractable conditions on the
existence of threshold values of $p$ for which a large induced subgraph of
small diameter emerges, which is the kind of results we are interested on.

Finally, sharp threshold for bond percolation on bounded-degree expanders are
given in [5].

##  4 Model and Preliminaries

In this paper, we study bond percolation of graphs sampled from
$\mathcal{SW}(n,\alpha)$, as formalized in Definition 1.1. In this section, we
define notation, key notions and tools that will be used throughout the rest
of this paper. Further notation used in the proofs of specific results is
introduced wherever it is used.

Key notions and notation. For the sake of completeness, we begin with the
formal definition of bond percolation.

######  Definition 4.1 (Bond percolation).

Given a graph $G=(V,E)$ and a real $p\in[0,1]$, its (bond) _percolation graph_
$G_{p}$ is the random subgraph obtained from $G$ by removing each edge $e\in
E$ independently, with probability $1-p$.

Considered any graph $G=(V,E)$ and $v\in V$, we denote by $\mathcal{N}_{G}(v)$
the neighborhood of $v$ in $G$, while $\deg_{G}(v)=|\mathcal{N}_{G}(v)|$
denotes the degree of $v$ in $G$. We omit the subscript when $G$ is clear from
context.

If $G=(V,E_{1}\cup E_{2})$ is sampled from $\mathcal{SW}(n,\alpha)$ as in
Definition 1.1, we say that a bridge $(u,v)\in E_{2}$ has _length_ $d(u,v)$
(where $d(\cdot,\cdot)$ is as in Definition 1.1). We also say that $u$ is at
_ring-distance_ $d(u,v)$ from $v$ (and viceversa). Considered a bridge
$(u,v)$, we say that $(u,v)$ is on the _clockwise_ (respectively, _counter-
clockwise_) side of $u$ if $d(u,v)$ corresponds to moving clockwise
(respectively, counter-clockwise) along the cycle $(V,E_{1})$ from $u$ to $v$.

Given a graph $G=(V,E)$ and $s\in V$, we denote by $\Gamma_{G}(s)$ the
connected component containing $s$ in $G$. We may omit $G$ when clear from
context, while with a slight abuse of notation, we simply write
$\Gamma_{p}(s)$ for $\Gamma_{G_{p}}(s)$ when we refer to the percolation
$G_{p}$ of some graph $G$, which will always be understood from context. Given
$G=(V,E)$ and $S\subseteq V$, $\text{diam}_{G}(S)$ is equal to the diameter of
the subgraph of $G$ induced by $S$ if this is connected, otherwise
$\text{diam}_{G}(S)=\infty$. With a slight abuse of notation, we write
$\text{diam}_{p}(S)$ when $G$ is the percolation graph $G_{p}$. Given
$G=(V,E)$ sampled from $\mathcal{SW}(n,\alpha)$ and any subgraph
$H=(V,E^{\prime})$ such that $E^{\prime}\subseteq E$ (e.g., $G_{p}$), we
associate a _ring-metric_ to $H$, so that the _ring-distance_ between $u,v$ is
simply $d(u,v)$ defined above on $G$.

#### Remarks.

In the sections that follow, unless stated otherwise, probabilities are always
taken over both the randomness in the sampling of $G$ from
$\mathcal{SW}(n,\alpha)$ and over the randomness of the percolation. We
further remark that our choice of the normalizing constant $C(\alpha,n)$ in
Definition 1.1 entails $\mathbf{E}\left[\deg(v)\right]=3$, while the
following, preliminary fact follows from a straightforward application of
Chernoff bound (Theorem C.1):

######  Fact 4.2.

Sample a graph $G=(V,E)$ from $\mathcal{SW}(n,\alpha)$. Then,

$\mathbf{Pr}\left(\max_{v}\deg(v)\leqslant 4\log n+2\right)\geqslant
1-\frac{1}{n}\,.$ (1)

Galton-Watson branching processes. Our analysis of the percolation process in
part relies on a reduction to the analysis of appropriately defined branching
processes.

######  Definition 4.3 (Galton-Watson Branching Process).

Let $W$ be a non-negative integer random variable, and let
$\\{W_{t,1}\\}_{t\geqslant 1,i\geqslant 1}$ be an infinite sequence of
independent identically distributed copies of $W$. The _Galton-Watson
branching process_ generated by the random variable $W$ is the process
$\\{X_{t}\\}_{t\geqslant 0}$ defined by $X_{0}=1$ and by the recursion

$X_{t}=\sum_{i=1}^{X_{t-1}}W_{t,i}\,.$

All properties of the process $\\{X_{t}\\}_{t\geqslant 0}$ (in particular,
population size and extinction probability) are captured by the equivalent
process $\\{B_{t}\\}_{t\geqslant 0}$, recursively defined as follows:

$B_{t}=\left\\{\begin{array}[]{ll}1,&t=0;\\\ B_{t-1}+W_{t}-1,&t>0\ \text{and}\
B_{t-1}>0;\\\ 0,&t>0\ \text{and}\ B_{t-1}=0\,,\end{array}\right.$

where $W_{1},\ldots,W_{t},\ldots$ are an infinite sequence of independent and
identically distributed copies of $W$.

In the remainder, when we refer to the Galton-Watson process generated by $W$,
we always mean the process $\\{B_{t}\\}_{t\geqslant 0}$. In particular, we
define $\sigma=\min\\{t>0:B_{t}=0\\}$ (we set $\sigma=+\infty$ if no such $t$
exists). Note that, for any $T<\sigma$, we have $B_{T}=\sum_{t=1}^{T}W_{t}-T$.

##  5 The case $\alpha>2$

The aim of this section is to prove Theorem 2.1, which follows from the two
lemmas below.

######  Lemma 5.1.

Let $\alpha<2$ be a constant and $p<1$ a percolation probability. Sample a
graph $G=(V,E)$ from the $\mathcal{SW}(n,\alpha)$ distribution and let $G_{p}$
its percolation graph. For every $s\in V=\\{0,\dots,n-1\\}$, the connected
component $\Gamma_{p}(s)$ contains $\mathcal{O}(\log n)$ nodes with
probability at least $1-1/n^{2}$.

######  Lemma 5.2.

Under the same hypotheses of Lemma 5.1, for every $s\in V=\\{0,\dots,n-1\\}$
and for any sufficiently large $\ell$,

$\mathbf{Pr}\left(\forall u\in\Gamma_{p}(s):d(s,u)\leqslant
2\ell^{2}\right)\geqslant 1-\frac{8}{(\alpha-2)\ell^{(\alpha-2)/2}}\,.$ (2)

We remark that (2) implies that, for any increasing distance function
$\ell=\ell(n)=\omega(1)$, every node in $\Gamma_{p}(s)$ has ring-distance from
$s$ not exceeding $2\ell^{2}$ with probability $1-o(1)$.

The proof of Lemma 5.1 is given in Subsection 5.1, while the proof of Lemma
5.2 in Subsection 5.2. To prove these lemmas, we rely on the notion of
$\ell$-graph, defined in the following paragraph, together with supplementary
notation that will be used in the remainder of this section.

####  $\ell$-graphs.

In what follows, we define a new graph on the vertex set
$V=\\{0,\dots,n-1\\}$, starting from any one-dimensional small-world graph
$G=(V,E_{1}\cup E_{2})$, where $(V,E_{1})$ is a cycle, which defines a ring-
metric, and $E_{2}$ is an arbitrary subset of bridges. In the remainder, we
always assume $n\geqslant 3$.

######  Definition 5.3 ($\ell$-graph).

Let $H=(V,E_{H})$ be a subgraph of a one-dimensional small-world graph $G$,
where $E_{H}\subseteq E_{1}\cup E_{2}$. For $\ell\geqslant 1$, consider an
arbitrary partition of $V$ into $n/\ell$ disjoint intervals of length $\ell$,
$\\{I^{(1)},\ldots,I^{(n/\ell)}\\}$ with respect to the ring metric induced by
$(V,E_{1})$. The _$\ell$ -graph_ associated to $H$ is the graph
${H}^{(\ell)}=(V^{(\ell)},E_{H}^{(\ell)})$, where
$V^{(\ell)}=\\{I^{(1)},\ldots,I^{(n/\ell)}\\}$, and

$E_{H}^{(\ell)}=\\{(I^{(h)},I^{(k)}):\exists u\in I^{(h)},v\in I^{(k)}\text{
s.t. }(u,v)\in E_{H}\\}\,.$

A generic element in $V^{(\ell)}$ thus corresponds to $\ell$ consecutive nodes
in the ring $(V,E_{1})$, it is called _super-node_ , and, depending on the
context, is denoted by v or by its corresponding interval $I_{\mbox{\sc v}}$
in the partition $\\{I^{(1)},\ldots,I^{(n/\ell)}\\}$ of $V$. Fixed a
partition, we denote with $E_{1}^{(\ell)}$ the set of links connecting two
adjacent super-nodes in $V^{(\ell)}$ (that is, two adjacent intervals in
$(V,E_{1})$): notice that $(V^{(\ell)},E_{1}^{(\ell)})$ is a ring of $n/\ell$
super-nodes, called _$\ell$ -ring_. Then, given a subgraph $H=(V,E_{H})$ as in
the definition above, the elements in $E_{H}^{(\ell)}$ can be partitioned into
two subsets: the elements in $E_{H}^{(\ell)}\cap E_{1}^{(\ell)}$ are called
_super-edges_ , while all the remaining elements in $E_{H}^{(\ell)}$ are
called _super-bridges_. $H^{(\ell)}$ can thus be seen as a subgraph of a one-
dimensional small-world graph $G^{(\ell)}$ with $n/\ell$ super-nodes, formed
by a ring $(V^{(\ell)},E_{1}^{(\ell)})$, and an additional set of super-
bridges. The example in Figure 1 summarizes the above definitions.

Figure 1: (a) A graph $G=(V,E)$ with a ring-metric. (b) The $3$-graph of $G$.

Let $H=(V,E_{H})$ as in Definition 5.3 and assume $u,v\in V$, with $u\in
I^{(h)}$ and $v\in I^{(k)}$. Clearly, if $(u,v)\in E_{H}$ then
$(I^{(h)},I^{(k)})\in E_{H}^{(\ell)}$. Moreover, the following fact
straightforwardly holds:

######  Fact 5.4.

Let $H=(V,E_{H})$ as in Definition 5.3 and let $s\in I^{(k)}$ for some
$k\in\\{1,\ldots,n/\ell\\}$. Then,

$|\Gamma_{H}(s)|\leqslant\ell|\Gamma_{{H}^{(\ell)}}(I^{(k)})|.$

The following, preliminary lemma is used in the proofs of Lemma 5.1 and Lemma
5.2. Its proof is in Appendix B.1.

######  Lemma 5.5.

Assume the hypotheses of Lemma 5.1 (and Lemma 5.2), so that
${G_{p}}^{(\ell)}=(V^{(\ell)},{E_{p}}^{(\ell)})$ is the $\ell$-graph of
$G_{p}$ generated by any fixed interval partition of $V$. Then, for each
$\mbox{\sc v}\in V^{(\ell)}$, we have:

$\mathbf{Pr}\left(\deg_{{G_{p}}^{(\ell)}}(\mbox{\sc
v})=0\right)\geqslant(1-p)^{2}e^{-2/(\alpha-2)},$ (3)
$\mathbf{Pr}\left(\text{$\mbox{\sc v}$ is incident to a super-bridge in
${G_{p}}^{(\ell)}$}\right)\leqslant\frac{2}{(\alpha-2)\ell^{\alpha-2}}\,.$ (4)

###  5.1 Proof of Lemma 5.1

To prove Lemma 5.1, we consider Algorithm 1 below that performs a BFS visit of
the $\ell$-graph of the percolation graph $G_{p}$. Then, in Lemma 5.6, we
prove that this algorithm terminates after visiting (only) $\mathcal{O}(\log
n)$ super-nodes, w.h.p., for a sufficiently large $\ell=\mathcal{O}(1)$.
Together with Fact 5.4, this proves Lemma 5.1.

Algorithm 1 BFS visit of ${G_{p}}^{(\ell)}$

1:Input: The $\ell$-graph ${G_{p}}^{(\ell)}=(V^{(\ell)},{E_{p}}^{(\ell)})$ of
$G_{p}$; an initiator (super-node) $\mbox{\sc s}\subseteq V^{(\ell)}$

2:$Q=\\{\mbox{\sc s}\\}$

3:while $Q\neq\emptyset$ do

4: $\mbox{\sc w}=\texttt{dequeue}(Q)$

5: $\texttt{visited}(\mbox{\sc w})=\texttt{True}$

6: for each x s.t. $(\mbox{\sc x},\mbox{\sc w})$ is a super-edge of
${E_{p}}^{(\ell)}$ and $\texttt{visited}(x)=\texttt{False}$ do

7: $\texttt{enqueue}(\mbox{\sc x},Q)$

8: for each y s.t. $(\mbox{\sc y},\mbox{\sc w})$ is a super-bridge of
${E_{p}}^{(\ell)}$ and $\texttt{visited}(\mbox{\sc y})=\texttt{False}$ do

9: $\texttt{enqueue}(\mbox{\sc y},Q)$

10: $\mbox{\sc y}_{\text{left}}=\text{the super-node at distance $1$ from
$\mbox{\sc y}$ on the ring at its left}$

11: if $\texttt{visited}(\mbox{\sc y}_{\text{left}})=\texttt{False}$ and
$(\mbox{\sc y}_{\text{left}},\mbox{\sc y})\in{E_{p}}^{(\ell)}$ then

12: $\texttt{enqueue}(\mbox{\sc y}_{\text{left}},Q)$

#### Remark

Note that, each time we add a super-node to queue $Q$, we also also add the
super-node to its left on the ring. So, in each while loop at line 3 of the
algorithm, for each super-node $\mbox{\sc w}\in Q$, its left neighbor on the
ring will also be in $Q$. This implies that, in each while loop, a single
super-node is added to the queue at line 7.

######  Lemma 5.6.

Assume the hypotheses of Lemma 5.1 and fix any node $s\in V$. For any fixed
interval partition777According to Definition 5.3. of the vertex set $V$,
consider the $\ell$-graph ${G_{p}}^{(\ell)}$ and the super-node $\mbox{{s}}\in
V^{(\ell)}$ such that $s\in I_{\mbox{{s}}}$. Then, a sufficiently large
$\ell=\mathcal{O}(1)$ exists, depending only on $p$ and $\alpha$, such that
Algorithm 1 terminates within $\mathcal{O}(\log n)$ iterations of the while
loop in line 3, with probability at least $1-1/n^{2}$.

###### Proof.

For $t=1,2,\dots$, let $Q_{t}$ contents of $Q$ at the end of the $t$-th
iteration of the while loop of Algorithm 1 and let $W_{t}$ denote the subset
of super-nodes that were added to $Q$ during the $t$-th iteration. We have
$|Q_{0}|=1$ and

$|Q_{t}|=\begin{cases}0\text{ if $|Q_{t-1}|=0$}\\\ |Q_{t-1}|+|W_{t}|-1\text{
otherwise},\end{cases}$

Let $X_{t}$ and $Y_{t}$ denote the sets of super-nodes that were added to $Q$
in the $t$-th iteration of the while loop, respectively at line 7 and at line
9. For $t\geqslant 2$, whenever a super-node is added to the queue, the queue
contains a super-node at ring-distance $1$ from it on the ring
$(V^{(\ell)},E_{1}^{(\ell)})$, so that $|W_{t}|=|X_{t}|+2|Y_{t}|$, where
$|X_{t}|\leqslant 1$ for $t\geqslant 2$ and $|X_{1}|\leqslant 2$ . Let
$\delta=1-p$, $\epsilon=2-\alpha$ and note that, from (3) and (4),

$\mathbf{Pr}\left(|X_{t}|=1\right)\leqslant
1-\delta^{2}e^{-2/\epsilon}\quad\text{and}\quad\mathbf{E}\left[|Y_{t}|\right]\leqslant\frac{2}{\epsilon\ell^{\epsilon}}.$
(5)

Moreover, note that for every $t$, $|Q_{t}|=0$, whenever
$\sum_{i=1}^{t}|W_{i}|\leqslant t$. Then, we can write

$\sum_{i=1}^{t}|W_{i}|-t=\sum_{i=1}^{t}|X_{i}|+2\sum_{i=1}^{t}|Y_{i}|-t\,,$

where $|X_{i}|$ are $\\{0,1\\}$ random variables and, if we $w$ is the node
extracted from $Q$ in the $i$-th iteration of the while loop, $|Y_{i}|$ is the
number of super-bridge neighbors of w, so that it can also be written as the
sum of random variables in $\\{0,1\\}$. Note that $\\{X_{t}\\}_{t}$ and
$\\{Y_{t}\\}_{t}$ are not independent random variables, because of the
conditions that appear in lines 6, 8 and 11 of Algorithm 1. Still, it is easy
to show that $X_{t}$’s and $Y_{t}$’s are dominated by independent copies of
two random variables $X$ and $Y$, such that
$\mathbf{Pr}\left(|X|=1\right)=1-\delta^{2}e^{-2/\epsilon}$ and
$\mathbf{E}\left[|Y|\right]\leqslant 1/(\epsilon\ell^{\epsilon})$. Hence,
Chernoff bound and (5) imply that, for a certain $t=\mathcal{O}(\log n)$
depending on $\delta$ and $\epsilon$,

$\displaystyle\mathbf{Pr}\left(\sum_{i=1}^{t}|X_{i}|\geqslant\left(1-\frac{\delta^{2}}{2}e^{-2/\epsilon}\right)t\right)\leqslant\frac{1}{2n^{2}},$
$\displaystyle\mathbf{Pr}\left(\sum_{i=1}^{t}|Y_{i}|\geqslant\frac{2t}{\epsilon\ell^{\epsilon}}\right)\leqslant\frac{1}{2n^{2}}.$

As a result, with probability at least $1-1/n^{2}$, we have:

$\sum_{i=1}^{t}|X_{i}|+2\sum_{i=1}^{t}|Y_{i}|-t\leqslant
t\left(\frac{4}{\epsilon\ell^{\epsilon}}-\frac{\delta^{2}}{2}e^{-2/\epsilon}\right).$

Hence, we can choose $\ell=\mathcal{O}(1)$ (depending only on $\epsilon$ and
$\delta$) large enough, so that with probability at least $1-1/n^{2}$,
$\sum_{i=1}^{t}|W_{i}|<t$, so that $|Q_{t}|=0$ for $t=\mathcal{O}(\log n)$. ∎

###  5.2 Proof of Lemma 5.2

Lemma 5.2 follows from Fact 5.4 and Lemma 5.7 below.

######  Lemma 5.7.

Assume the hypotheses of Lemma 5.2. For sufficiently large $\ell$ depending
only on $p$ and $\alpha$, consider the $\ell$-graph ${G_{p}}^{(\ell)}$ and the
super-node $\textsc{s}\in V^{(\ell)}$ such that $s\in I_{\textsc{s}}$. Then,
with probability at least

$1-\tfrac{8}{(\alpha-2)}\cdot\ell^{-(\alpha-2)/2}\,,$

all nodes in $\Gamma_{{G_{p}}^{(\ell)}}(\textsc{s})$ are within ring-distance
$\ell$ from s in the ring $({V}^{(\ell)},{E_{1}}^{(\ell)})$.

###### Proof.

Without loss of generality, we assume $\textsc{s}=0$ and let
${V}^{(\ell)}=\\{0,\dots,n/\ell\\}$ . Next, we consider nodes on the ring at
increasing distance from $\textsc{s}=0$ moving counter-clockwise, proving that
nodes at distance exceeding $\ell^{(2-\alpha)/2}$ are not part of
$\Gamma_{{G_{p}}^{(\ell)}}(\textsc{s})$, the connected component of s. To this
purpose, denote by $K$ be the random variable indicating the ring-distance of
the super-node v closest to s, such that v has no incident super-edges in
${G_{p}}^{(\ell)}$. From (3), and setting $\epsilon=2-\alpha$ and
$\delta=1-p$, we have

$\mathbf{Pr}\left(\text{{v} has no super-edges in
${G_{p}}^{(\ell)}$}\right)\geqslant\delta^{2}e^{-2/\epsilon},$

So, for $k=\ell^{\epsilon/2}$ and for $\ell$ large enough

$\mathbf{Pr}\left(K>k\right)\leqslant(1-\delta^{2}e^{-2/\epsilon})^{k}\leqslant\frac{1}{\ell^{\epsilon/2}}\,.$

Moreover, denote by $B_{k}$ be the following event

$B_{k}=\\{\text{the $k$ nodes nearest to $\textsc{s}$ have no super-
bridges}\\}.$

From (4), from the independence of the edge percolation events and using a
union bound, we have for the complementary event $B_{k}^{C}$

$\mathbf{Pr}\left(B_{k}^{C}\right)\leqslant
k\cdot\frac{2}{\epsilon\ell^{\epsilon}}\,.$

Iterating the same argument for nodes on the clockwise side of s, if
$k=\ell^{\epsilon/2}$ we have

$\displaystyle\mathbf{Pr}\left(\text{there is a node at distance $\leqslant k$
from $\textsc{s}$ in ${\Gamma}^{(\ell)}_{p}(\textsc{s})$}\right)$
$\displaystyle\leqslant 2\mathbf{Pr}\left(\\{K>k\\}\cup
B_{k}^{C}\right)\leqslant\frac{4}{\ell^{\epsilon/2}}+\frac{4}{\epsilon\ell^{\epsilon/2}},$

which completes the proof. ∎

##  6 The case $1<\alpha<2$

The aim of this section is to prove Theorem 2.2, which follows from the two
lemmas below.

######  Lemma 6.1.

Under the hypotheses of Theorem 2.2, assume $G=(V,E)$ is sampled from
$\mathcal{SW}(n,\alpha)$ and let $G_{p}$ be its percolation graph. Then two
constants $\overline{p}<1$ and $\eta>1$ exist such that, if $p>\overline{p}$,
w.h.p. there is a set of $\Omega(n)$ nodes in $G_{p}$ that induces a connected
sub-component with diameter $\mathcal{O}(\log^{\eta}n)$.

######  Lemma 6.2.

Under the hypotheses of Theorem 2.2, assume $G=(V,E)$ is sampled from
$\mathcal{SW}(n,\alpha)$ and let $G_{p}$ its percolation graph. Then, a
constant $\underline{p}>0$ exists (in particular, $\underline{p}=1/3$) such
that, if $p<\underline{p}$, w.h.p. each connected component of $G_{p}$ has
size at most $\mathcal{O}(\log n)$.

The proof of Lemma 6.1 is given in Subsection 6.1, while the proof of Lemma
6.2 follows an approach, based on Galton-Watson processes, similar to that of
Lemma 5.1, and it is given in Appendix B.2.

###  6.1 Proof of Lemma 6.1

The lemma that follows is our new key ingredient to apply an inductive
approach similar to the one in [4] in the case of full-bond percolation.

Figure 2: Visualization of the proof of Lemma 6.1. Red dotted boxes identify
“good” intervals in $H_{k+1}$ (intervals for which the event $A_{k}$ holds);
for each good box, the included blue box contains the subset of nodes that
induce a connected subgraph of size at least $(1-\varepsilon_{k})N_{k}$ nodes
and diameter $D_{k}$. In the lemma, we have to prove the existence of at least
a certain number of red boxes, and that blue boxes are all mutually connected
(i.e. the existence of the red edges in the picture).

######  Lemma 6.3.

Assume the hypotheses of Lemma 6.1, let $\beta=\frac{1}{2}\alpha(3-\alpha)$
and

$N_{k}=e^{\beta^{k}}\quad\text{and}\quad C_{k}=e^{\beta^{k-1}(\beta-1)}.$

Let $I_{k}$ be an arbitrary interval of $N_{k}$ adjacent nodes in the cycle
$(V,E_{1})$, $D_{k}$ any finite integer. Define the following event:

$A_{k}=\\{\exists S\subseteq I_{k}:|S|\geqslant(1-\varepsilon_{k})N_{k}\
\wedge\text{diam}_{p}(S)\leqslant D_{k}\\}.$

Assume further that, for suitable, real constants $\varepsilon_{k},\delta_{k}$
and $p_{k}$ in $(0,1)$,

$\mathbf{Pr}\left(A_{k}\right)\geqslant 1-\delta_{k},\quad\text{if $p\geqslant
p_{k}$}.$

Then, if we consider an interval $I_{k+1}$ of $N_{k+1}$ adjacent nodes, it
holds:

$\mathbf{Pr}\left(A_{k+1}\right)\geqslant 1-\delta_{k+1},\quad\text{ if
$p\geqslant p_{k+1}$},$

where

$\displaystyle\delta_{k+1}=2C_{k+1}^{-0.2},\quad\varepsilon_{k+1}=\varepsilon_{k}+\delta_{k}+C_{k+1}^{-0.2},$
$\displaystyle D_{k+1}=2D_{k}+1,\quad
p_{k+1}=\frac{0.9(\alpha-1)(2-\alpha)}{(1-\varepsilon_{k})^{2}(4.2-2\alpha)}C(n,\alpha).$

###### Proof.

In words, $A_{k}$ is the event that there exists a subset of the nodes in
$I_{k}$ that induces a connected component of $G_{p}$ of size
$\geqslant(1-\varepsilon_{k})N_{k}$ nodes and diameter $\leqslant D_{k}$.
Consider the interval $I_{k+1}$ and divide it into $C_{k+1}$ disjoint
intervals of size $N_{k}$ (note that $N_{k+1}=N_{k}\cdot C_{k+1}$). Denote by
$H_{k+1}$ the set of sub-intervals of $I_{k+1}$ of size $N_{k}$ for which
event $A_{k}$ holds. In particular, for every $i=1,2,\dots,C_{k+1}$, we use
the indicator variable $A_{k}^{(i)}$ to specify whether or not $A_{k}$ holds
for the $i$-th sub-interval, so that

$|H_{k+1}|=\sum_{i=1}^{C_{k+1}}A_{k}^{(i)}.$

where independence of the $A_{k}^{(i)}$’s follows from disjointness of the
sub-intervals of $I_{k+1}$. For the sake of brevity, let $B_{k+1}$ denote the
event $\\{|H_{k+1}|\geqslant(1-\delta_{k})C_{k+1}-C_{k+1}^{0.8}\\}$.
Application of Chernoff’s bound then implies

$\mathbf{Pr}\left(B_{k+1}\right)\geqslant 1-e^{-2C_{k+1}^{0.6}}\geqslant
1-C_{k+1}^{-0.2}.$

Note that by definition, each sub-intervals in $H_{k+1}$ contains at least one
subset (of the nodes) that induces a connected component in $G_{p}$ with at
least $(1-\varepsilon_{k})N_{k}$ nodes and diameter at most $D_{k}$. Our goal
is to show that, with some probability, these intervals are all connected to
each other: this in turn implies the existence of a set of nodes that induces
a larger connected component, with diameter at most $2D_{k}+1$ and containing
at least $|H_{k+1}|(1-\varepsilon_{k})N_{k}$ nodes, see see Figure 2 for a
visual intuition of the proof. In the remainder of this proof, we denote by
$F_{k+1}$ the event that all connected components associated to intervals in
$H_{k+1}$ are mutually connected. In particular, we prove that
$\mathbf{Pr}\left(F_{k+1}\mid B_{k+1}\right)\geqslant 1-C_{k+1}^{-0.2}$, so
that

$\displaystyle\mathbf{Pr}\left(A_{k+1}\right)=\mathbf{Pr}\left(F_{k+1}\cap
B_{k+1}\right)=\mathbf{Pr}\left(B_{k+1}\right)\mathbf{Pr}\left(F_{k+1}\mid
B_{k+1}\right)$ $\displaystyle\geqslant 1-2C_{k+1}^{-0.2},$

which implies that $A_{k+1}$ holds with probability at least $1-\delta_{k+1}$,
whenever we set

$\delta_{k+1}=2C_{k+1}^{-0.2}\quad\varepsilon_{k+1}=\varepsilon_{k}+\delta_{k}+C_{k+1}^{-0.2}\quad\text{and}\quad
D_{k+1}=2D_{k}+1.$

Now, we estimate the probability that, given $B_{k+1}$, $F_{k+1}$ holds. Two
nodes in $I_{k+1}$ have distance at most $N_{k+1}$ on the cycle. Moreover, if
we consider two sub-intervals of $I_{k+1}$ both belonging to $H_{k+1}$, the
corresponding connected components contain at least $(1-\varepsilon_{k})N_{k}$
nodes each, accounting for at least $(1-\varepsilon_{k})^{2}N_{k}^{2}$ pairs
$(u,v)$, with $u$ belonging to the first and $v$ to second connected
component. So, two given sub-intervals in $H_{k+1}$, they are not connected
with probability at most

$\displaystyle\left(1-\frac{p}{cN_{k+1}^{\alpha}}\right)^{(1-\varepsilon_{k})^{2}N_{k}^{2}}\leqslant\exp\left(-\frac{p}{c}(1-\varepsilon_{k})^{2}\frac{e^{2\beta^{k}}}{e^{\alpha\beta^{k+1}}}\right)$
$\displaystyle=\exp\left(-\frac{p}{c}(1-\varepsilon_{k})^{2}e^{\beta^{k}(2-\alpha\beta)}\right),$

where in the remainder of this proof, we write $c$ for $C(\alpha,n)$, for the
sake of readability. If we consider all pairs of intervals in $H_{k+1}$, a
simple union bound allows us to conclude that the probability that the
intervals in $H_{k+1}$ are not all mutually connected is at most

$\displaystyle
C_{k+1}^{2}\exp\left(-\frac{p}{c}(1-\varepsilon_{k})^{2}e^{\beta^{k}(2-\alpha\beta)}\right)$
$\displaystyle\leqslant\exp\left(\beta^{k}\left(2(\beta-1)-\frac{p}{c}(1-\varepsilon_{k})^{2}(2(2-\alpha)+0.2)\right)\right),$

where the last inequality follows from the definition of $\beta$. Finally, the
quantity above can be upper bounded as follows

$\displaystyle\exp\left(-\beta^{k}0.1(\alpha-1)(2-\alpha)\right)=\exp(-0.2\beta^{k}(\beta-1))=C_{k+1}^{-0.2},$

whenever $p$ satisfies

$p\geqslant\frac{c(2-\alpha)(\alpha-1)0.9}{(1-\varepsilon_{k})^{2}(2(2-\alpha)+0.2)}.$

∎

Now we are ready to prove the lemma.

###### Proof of Lemma 6.1.

Let $C_{k}$ and $N_{k}$ defined as in the claim of Lemma 6.3. First, we
consider the series $\sum_{k}C_{k}^{-0.2}$ and, since
$C_{k}=e^{\beta^{k-1}(\beta-1)}$ with $\beta>1$, we notice that the series is
convergent, i.e. $\sum_{k=1}^{\infty}C_{k}^{-0.2}<+\infty$.888We did not try
to optimize constants and the choice $0.2$ for the exponent is not necessarily
optimal. This means that the tail of the series converges to zero, and this
implies that there exists a constant $h$ such that

$\sum_{k=h}^{+\infty}C_{k}^{-0.2}\leqslant\frac{1}{100}.$ (6)

The constant $h$ depends only on $\alpha$. In particular, it increases as
$\alpha\rightarrow 2^{-}$ and $\alpha\rightarrow 1^{+}$.

Now we consider $I_{h}$, an arbitrary interval of size $N_{h}=e^{\beta^{h}}$.
Next, we let

$\delta_{h}=1-p^{e^{\beta^{h}}},\quad\varepsilon_{h}=0,\quad
D_{h}=e^{\beta^{h}},\quad p_{h}=p,$

and we consider the event $A_{h}$, defined as in the statement of Lemma 6.3.
If no ring edge belonging to $I_{h}$ is percolated, $A_{h}$ is trivially true:
this implies that, for every $p\geqslant p_{h}$,
$\mathbf{Pr}\left(A_{h}\right)\geqslant 1-\delta_{h},$ where probability is
over the edges with endpoints in $I_{h}$. If $A_{h+1}$ and $N_{h+1}$ are
defined like in its statement, Lemma 6.3 then implies that, for an arbitrary
interval $I_{h+1}$ of size $N_{h+1}$, we have

$\mathbf{Pr}\left(A_{h+1}\right)\geqslant 1-\delta_{h+1},$

if $p\geqslant p_{h+1}$ and whenever we take

$\displaystyle\delta_{h+1}=2C_{h+1}^{-0.2},\quad\varepsilon_{h+1}=1-p^{e^{\beta^{h}}}+C_{h+1}^{-0.2},$
$\displaystyle D_{h+1}=2e^{\beta^{h}}+1,\quad
p_{h+1}=\frac{0.9c(\alpha-1)(2-\alpha)}{(4.2-2\alpha)},$

where the probability is taken over the randomness of the edges with endpoints
in $I_{h+1}$.999Recall that $c=C(\alpha,n)$ in the remainder of this proof.

If we iteratively apply Lemma 6.3, we thus have for each $k\geqslant 1$ such
that $N_{k}\leqslant n$,

$\mathbf{Pr}\left(A_{k}\right)\geqslant 1-\delta_{k},$

where $\delta_{k}=2C_{k}^{-0.2}$,
$p_{k}=\frac{0.9c(\alpha-1)(2-\alpha)}{(1-\varepsilon_{k-1})^{2}(4.2-2\alpha)}$,
and $\varepsilon_{k}$ and $D_{k}$ are defined by the recurrencies:

$\begin{cases}\varepsilon_{k}=\varepsilon_{k-1}+\delta_{k-1}+C_{k}^{-0.2},\
\text{if $k>h$}\\\ \varepsilon_{h}=1-p^{e^{\beta^{h}}}\end{cases}$

$\begin{cases}D_{k}=2D_{k-1}+1,\ \text{if $k>h$}\\\
D_{h}=e^{\beta^{h}}.\end{cases}$

Now, we solve the recurrence for $\varepsilon_{k}$, obtaining
$\varepsilon_{k}=1-p^{e^{\beta^{h}}}+3\sum_{i=h}^{k}C_{i}^{-0.2},$ where,
leveraging (6), we take $p>\sigma$, with $\sigma>0$ such that
$1-\sigma^{e^{\beta^{h}}}=1/50$. With this choice, for each $k\geqslant 1$ we
obtain

$\varepsilon_{k}\leqslant
1-p^{e^{\beta^{h}}}+\frac{3}{100}\leqslant\frac{1}{20}.$

Moreover, for each $i\leqslant k$, we have that $D_{k}\leqslant
2^{k-h+1}e^{\beta^{h}}$. If we take $m=\log_{\beta}(\log n)$, then
$N_{m}=e^{\beta^{m}}=n$ and $C_{m}=n^{(\beta-1)/\beta}$. We also have:

$\displaystyle
D_{m}\leqslant\frac{e^{\beta^{h}}}{2^{h-1}}2^{\log_{\beta}(\log(n))}=\frac{e^{\beta^{h}}}{2^{h-1}}(\log
n)^{\log_{\beta}2}.$

Setting $\eta=\log_{\beta}2$, we have $\eta>1$, since $\beta<2$. We thus have

$D_{m}=O((\log^{\eta}(n))).$

Moreover, if $p\geqslant\sigma$

$\delta_{m}\leqslant 2n^{-0.2(\beta-1)/\beta},\
\varepsilon_{m}\leqslant\frac{1}{20},\
p_{m}\geqslant\frac{0.9c(\alpha-1)(2-\alpha)}{(19/20)^{2}(4.2-2\alpha)}.$

Finally, if

$p\geqslant\max\left\\{\sigma,\frac{0.9c(\alpha-1)(2-\alpha)}{(19/20)^{2}(4.2-2\alpha)}\right\\}:=\overline{p}$

then,

$\mathbf{Pr}\left(A\right)\geqslant 1-\delta_{m}\geqslant
1-2n^{-0.2(\beta-1)/\beta},$

where

$A=\left\\{\exists S\subseteq
V:|S|>\frac{19}{20}n\,\wedge\,\text{diam}_{p}(S)=O(\log^{\eta}(n))\right\\},$

i.e., w.h.p. $G_{p}$ contains an induced subgraph of size at least $(19/20)n$
nodes and diameter $O(\log^{\eta}(n))$. ∎

##  7 The case $\alpha<1$

In this section, we prove Theorem 2.3, which follows from the two lemmas
below.

######  Lemma 7.1.

Under the hypotheses of Theorem 2.3, sample a $G=(V,E)$ from the
$\mathcal{SW}(n,\alpha)$ distribution and let $G_{p}$ be its percolation
subgraph. Then, a constant $\overline{p}<1$ exists such that, if
$p>\overline{p}$ then, w.h.p., there is a set of $\Omega(n)$ nodes in $G_{p}$
that induce a connected subgraph of diameter $\mathcal{O}(\log n)$.

######  Lemma 7.2.

Under the hypothesis of Theorem 2.3, sample a $G=(V,E)$ from the
$\mathcal{SW}(n,\alpha)$ distribution and let $G_{p}$ be the percolation
subgraph of $G$. Then, a constant $\underline{p}>0$ exists such that, if
$p<\underline{p}$ then, w.h.p., each connected component of $G_{p}$ has size
at most $\mathcal{O}(\log n)$.

A key observation to prove Lemma 7.1 is that, when $\alpha<1$, the percolation
graph of a graph sampled from $\mathcal{SW}(n,\alpha)$ stochastically
dominates a cycle with additional Erdős-Rényi random edges. To prove Lemma 7.1
we thus use a previous result in [3] for this class of random graphs. In
particular, we first give an equivalent formulation of Lemma 5.1 in [3],
stating that, with constant probability the sequential BFS visit (Algorithm 2)
reaches $\Omega(\log n)$ nodes within $\mathcal{O}(\log n)$ rounds. We then
consider a parallel BFS visit (see Algorithm 4 in Subsection B.3 of the
Appendix) and show an equivalent formulation of Lemma 5.2 in [3], stating
that, w.h.p., the parallel BFS visit starting with $\Omega(\log n)$ nodes
reaches a constant fraction of nodes within $\mathcal{O}(\log n)$ rounds.

The full proof of Lemma 7.1 is given in Subsection B.3 of the Appendix, while
the proof of Lemma 7.2 is omitted, since it proceeds along the very same lines
as the proof of Lemma 6.2, which does not depends on the value of $\alpha$.

## References

  * [1] Noga Alon, Benjamini Itai, and Stacey Alan.  Percolation on finite graphs and isoperimetric inequalities.  Annals of Probability, 32:1727–1745, 2004.
  * [2] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  Science, 286(5439):509–512, 1999.
  * [3] Luca Becchetti, Andrea Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi.  Sharp thresholds for a sir model on one-dimensional small-world networks, 2021.
  * [4] Itai Benjamini and Noam Berger.  The diameter of long-range percolation clusters on finite cycles.  Random Struct. Algorithms, 19(2):102–111, 2001.
  * [5] Itai Benjamini, Stephane Boucheron, Gabor Lugosi, and Raphael Rossignol.  Sharp threshold for percolation on expanders.  The Annals of Probability, 40(1):130 – 145, 2012.
  * [6] Marek Biskup.  On the scaling of the chemical distance in long-range percolation models.  The Annals of Probability, 32(4):2938 – 2977, 2004.
  * [7] Marek Biskup.  Graph diameter in long-range percolation.  Random Structures & Algorithms, 39(2):210–227, 2011.
  * [8] Béla Bollobás, Svante Janson, and Oliver Riordan.  The phase transition in inhomogeneous random graphs.  Random Structures & Algorithms, 31(1):3–122, 2007.
  * [9] Béla Bollobás and Oliver Riordan.  The diameter of a scale-free random graph.  Comb., 24(1):5–34, 2004.
  * [10] Duncan S. Callaway, John E. Hopcroft, Jon Kleinberg, Mark E. J. Newman, and Steven H. Strogatz.  Are randomly grown graphs really random?  Phys. Rev. E, 64:041902, Sep 2001.
  * [11] Wei Chen, Laks Lakshmanan, and Carlos Castillo.  Information and influence propagation in social networks.  Synthesis Lectures on Data Management, 5:1–177, 10 2013.
  * [12] Hyeongrak Choi, Mihir Pant, Saikat Guha, and Dirk Englund.  Percolation-based architecture for cluster state creation using photon-mediated entanglement between atomic memories.  npj Quantum Information, 5(1):104, 2019.
  * [13] Easley David and Kleinberg Jon.  Networks, Crowds, and Markets: Reasoning About a Highly Connected World.  Cambridge University Press, USA, 2010.
  * [14] Moez Draief, Ayalvadi Ganesh, and Laurent Massoulié.  Thresholds for virus spread on networks.  In Proceedings of the 1st International Conference on Performance Evaluation Methodolgies and Tools, valuetools ’06, page 51–es, New York, NY, USA, 2006. Association for Computing Machinery.
  * [15] Devdatt Dubhashi and Alessandro Panconesi.  Concentration of Measure for the Analysis of Randomized Algorithms.  Cambridge University Press, USA, 1st edition, 2009.
  * [16] Rick Durrett and Harry Kesten.  The critical parameter for connectedness of some random graphs.  A Tribute to P. Erdos, pages 161–176, 1990.
  * [17] Michele Garetto, Weibo Gong, and Donald F. Towsley.  Modeling malware spreading dynamics.  In Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30 - April 3, 2003, pages 1869–1879. IEEE Computer Society, 2003.
  * [18] Anna R. Karlin, Greg Nelson, and Hisao Tamaki.  On the fault tolerance of the butterfly.  In Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing, pages 125–133, 1994.
  * [19] David Kempe, Jon Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  Theory of Computing, 11(4):105–147, 2015.
  * [20] Harry Kesten.  The critical probability of bond percolation on the square lattice equals 1/2.  Communications in mathematical physics, 74(1):41–59, 1980.
  * [21] Jon Kleinberg.  Navigation in a small world.  Nature, 406:845, 2000.
  * [22] Alexander Kott and Igor Linkov.  Cyber resilience of systems and networks.  Springer, 2019.
  * [23] Eun Jee Lee, Sudeep Kamath, Emmanuel Abbe, and Sanjeev R. Kulkarni.  Spectral bounds for independent cascade model with sensitive edges.  In 2016 Annual Conference on Information Science and Systems, CISS 2016, Princeton, NJ, USA, March 16-18, 2016, pages 649–653. IEEE, 2016\.
  * [24] Remi Lemonnier, Kevin Scaman, and Nicolas Vayatis.  Tight bounds for influence in diffusion networks and application to bond percolation and epidemiology.  In Advances in Neural Information Processing Systems, volume 27, pages 846–854. Curran Associates, Inc., 2014.
  * [25] Rémi Lemonnier, Kevin Seaman, and Nicolas Vayatis.  Tight bounds for influence in diffusion networks and application to bond percolation and epidemiology.  In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1, NIPS’14, page 846–854, Cambridge, MA, USA, 2014. MIT Press.
  * [26] Cristopher Moore and Mark E. J. Newman.  Epidemics and percolation in small-world networks.  Physical Review E, 61(5):5678, 2000.
  * [27] Cristopher Moore and Mark E. J. Newman.  Exact solution of site and bond percolation on small-world networks.  Phys. Rev. E, 62:7059–7064, Nov 2000.
  * [28] Charles M. Newman and Lawrence S. Schulman.  One dimensional $1/|j-i|^{s}$ percolation models: The existence of a transition for $s\leqq 2$.  Communications in Mathematical Physics, 104(4):547–571, 1986.
  * [29] Mark E. J. Newman and Duncan J. Watts.  Scaling and percolation in the small-world network model.  Physical review E, 60(6):7332, 1999.
  * [30] Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani.  Epidemic processes in complex networks.  Rev. Mod. Phys., 87:925–979, Aug 2015.
  * [31] Vinod K.S. Shante and Scott Kirkpatrick.  An introduction to percolation theory.  Advances in Physics, 20(85):325–357, 1971.
  * [32] Wei Wang, Ming Tang, H Eugene Stanley, and Lidia A Braunstein.  Unification of theoretical approaches for epidemic spreading on complex networks.  Reports on Progress in Physics, 80(3):036603, feb 2017.
  * [33] Duncan J. Watts and Steven H. Strogatz.  Collective dynamics of ‘small-world’ networks.  nature, 393(6684):440–442, 1998.
  * [34] Tongfeng Weng, Michael Small, Jie Zhang, and Pan Hui.  Lévy walk navigation in complex networks: A distinct relation between optimal transport exponent and network dimension.  Scientific Reports, 5(1):17309, 2015.

Appendix

##  Appendix A Full-bond Percolation vs Independent Cascade

We first give the formal definitions of full-bond percolation and independent
cascade processes.

######  Definition A.1 (Full-bond percolation).

Given a graph $G=(V,E)$, and given, for every edge $e\in E$, a _percolation
probability_ $p(e)\in[0,1]$, the _bond percolation_ process consists to
_remove_ each edge $e\in E$, independently, with probability $1-p(e)$. The
random subgraph, called the _percolation graph_ $G_{p}=(V,E_{p})$, is defined
by the edges that are not removed (i.e. they are activated), i.e.,
$E_{p}=\\{e\in E\,:\,\mbox{edge $e$ is not removed}\\}$. Given an initial
subset $A_{0}\subseteq V$ of _active_ nodes, for every integer $t\leqslant
n-1$, we define the random subset $A_{t}$ of $t$-active nodes as the subset of
nodes that are at distance $t$ from $A_{0}$ in the percolation graph
$G_{p}=(V,E_{p})$, i.e., $A_{t}=N_{G_{p}}^{t}(A_{0})$. Finally, the subset of
all active nodes from $A_{0}$ is the subset $N^{*}_{G_{p}}(A_{0})$.

######  Definition A.2 (Independent cascade).

Given a graph $G=(V,E)$, an assignment of _transmission probabilities_
$\\{p(e)\\}_{e\in E}$ to the edges of $G$, and a non-empty set $I_{0}\subseteq
V$ of initially infectious nodes, the Independent Cascade (for short,
$\mathrm{IC}$) protocol defines the stochastic process
$\\{S_{t},I_{t},R_{t}\\}_{t\geqslant 0}$ on $G$, where $S_{t},I_{t},R_{t}$ are
three sets of vertices, respectively called _susceptible_ , _infectious_ , and
_recovered_ , which form a partition of $V$ and that are defined as follows.

  * •

At time $t=0$ we have $R_{0}=\emptyset$ and $S_{0}=V-I_{0}$.

  * •

At time $t\geqslant 1$:

    * –

$R_{t}=R_{t-1}\cup I_{t-1}$, that is, the nodes that were infected at the
previous step become recovered;

    * –

independently for each edge $e=\\{u,v\\}$ such that $u\in I_{t-1}$ and $v\in
S_{t-1}$, with probability $p(e)$ the event that “$u$ transmits the infection
(i.e. a copy of the source message) to $v$ at time $t$” takes place. The set
$I_{t}$ is the set of all vertices $v\in S_{t-1}$ such that for at least one
neighbor $u\in I_{t-1}$ the event that $u$ transmits the infection to $v$
takes place as described above.

    * –

$S_{t}=S_{t-1}-I_{t}$

The process stabilizes when $I_{t}=\emptyset$.
The Reed-Frost $\mathrm{SIR}$ protocol (for short, _RF Protocol_) is the
special case of the $\mathrm{IC}$ protocol in which all transmission
probabilities are the same.

In [19], given any fixed graph $G=(V,E)$, the Independent Cascade process is
shown to be _equivalent_ to the full-bond percolation process.

If we consider the set $I_{t}$ of nodes that are infectious at time $t$ in a
graph $G=(V,E)$ according to the IC process with transmission probabilities
$\\{p(e)\\}_{e\in E}$ and with initiator set $I_{0}$, we see that such a set
has precisely the same distribution as the set of nodes at distance $t$ from
$I_{0}$ in the percolation graph $G_{p}$ generated by the bond-percolation
process with probabilities $\\{p(e)\\}_{e\in E}$ (see Definition A.1).
Furthermore, the set of recovered nodes $R_{t}$ is distributed precisely like
the set of nodes at distance $<t$ from $I_{0}$ in $G_{p}$.

We formalize this equivalence by quoting a theorem from [11].

######  Theorem A.3 (Bond percolation and IC processes are equivalent, [19]).

Consider the bond-percolation process and the $\mathrm{IC}$ protocol on the
same graph $G=(V,E)$ and let $I_{0}=A_{0}=V_{0}$, where $V_{0}$ is any fixed
subset of $V$, and with transmission probabilities and percolation
probabilities equal to $\\{p(e)\\}_{e\in E}$.

Then, for every integer $t\geqslant 1$ and for every subsets
$V_{1},\dots,V_{t-1}\subseteq V$, the events
$\\{I_{0}=V_{0},\dots,I_{t-1}=V_{t-1}\\}$ and
$\\{A_{0}=V_{0},\dots,A_{t-1}=V_{t-1}\\}$ have either both zero probability or
non-zero probability, and, in the latter case, the distribution of the
infectious set $I_{t}$, conditional to the event
$\\{I_{0}=V_{0},\dots,I_{t-1}=V_{t-1}\\}$, is the same to that of the
$t$-active set $A_{t}$, conditional to the event
$\\{A_{0}=V_{0},\dots,A_{t-1}=V_{t-1}\\}$.

The strong equivalence shown in the previous theorem is obtained by applying
the principle of deferred decision on the percolation/infection events that
take place on every edge since they are mutually independent. This result can
be exploited to analyze different aspects and issues of the IC (and, thus, the
RF) process. We here summarize such aspects in an informal way.

As a first immediate consequence of Theorem A.3, we have that, starting from
any source subset $I_{0}$, to bound the size of the final set $R_{\tau}$ of
the nodes informed by $I_{0}$, we can look at the size of the union of the
connected components in $G_{p}$ that include all nodes of $I_{0}$, i.e., we
can bound the size of $N^{*}_{G_{p}}(I_{0})$.

A further remark is that in the bond-percolation process there is no time, and
we can analyze the connected component of the percolation graph in any order
and according to any visit process. Furthermore, if we want a lower bound to
the number of nodes reachable from $I_{0}$ in the percolation graph, we can
choose to focus only on vertices reachable through a subset of all possible
paths, and, in particular, we can restrict ourselves to paths that are easier
to analyze. In our analysis we will only consider paths that alternate between
using a bounded number of local edges and one bridge edge.

##  Appendix B Omitted proofs

###  B.1 Proof of Lemma 5.5

We first prove the following, preliminary fact.

######  Lemma B.1.

Let $n\geqslant 3$ and $\alpha>2$ and let $G=(V,E_{1}\cup E_{2})$ be a
$\mathcal{SW}(n,\alpha)$ graph. Then, for every $v\in V$ and $x\geqslant 0$,
we have:

$\mathbf{Pr}\left(\text{$v$ has a bridge of length
$>x$}\right)\leqslant\frac{1}{x^{\alpha-1}}\,,$ $\mathbf{Pr}\left(\text{$v$
has a bridge with length $>x$ on one
side}\right)\leqslant\frac{1}{2x^{\alpha-1}}\,.$

###### Proof.

We have

$\displaystyle\mathbf{Pr}\left(\text{$v$ has a bridge with length $>x$ in one
side}\right)\leqslant\sum_{y=x+1}^{n/2}\frac{1}{C(\alpha,n)y^{\alpha}}$
$\displaystyle\leqslant\int_{x+1}^{+\infty}\frac{1}{C(\alpha,n)(y-1)^{\alpha}}dy\leqslant\frac{1}{(\alpha-1)C(\alpha,n)x^{\alpha-1}}\leqslant\frac{1}{x^{\alpha-1}},$

where the last inequality follows from the fact that $C(\alpha,n)\geqslant
1/2^{\alpha-1}$. Then, the lemma follows from

$\displaystyle\mathbf{Pr}\left(\text{$v$ has a bridge of length $>x$ }\right)$
$\displaystyle\leqslant 2\mathbf{Pr}\left(\text{$v$ has a bridge with length
$>x$ on one side}\right).$

∎

Consider now any super-node $\mbox{\sc v}\in{V}^{(\ell)}$ and, for the rest of
this proof, denote by $w_{1}$ and $w_{2}$ the two boundary nodes of
$I_{\mbox{\sc v}}$. Without loss of generality, we assume $I_{\mbox{\sc v}}$
includes the ring-edges that we traverse if we move on the cycle $(V,E_{1})$
from $w_{1}$ to $w_{2}$ counter-clockwise. We first prove (3). The super-node
v has no out-edges in ${G_{p}}^{(\ell)}$ if and only if i) each node in
$I_{\mbox{\sc v}}$ has no bridge to a node in $V\setminus I_{\mbox{\sc v}}$
and ii) $w_{1}$ and $w_{2}$ share no-ring edges with nodes in $V\setminus
I_{\mbox{\sc v}}$ in $G_{p}$. Condition i) above is equivalent to the
following: for every $x=1,\ldots,\ell$, the node $u\in I_{v}$ at distance
$d(w_{1},u)=x$ from $w_{1}$ has no bridge of length exceeding $x$ on the
clockwise side and of length exceeding $\ell-x$ on the counter-clockwise side.

Since, from Lemma B.1, the probability that a node has a bridge of length
larger than $x$ on one side is at most $1/(2x^{\alpha-1})$,

$\displaystyle\mathbf{Pr}\left(\deg_{{G_{p}}^{(\ell)}}({\mbox{\sc
v}})=0\right)\geqslant\left[(1-p)\cdot\prod_{x=1}^{\ell}\left(1-\frac{1}{2x^{\alpha-1}}\right)\right]^{2}$
$\displaystyle\geqslant(1-p)^{2}\cdot
e^{-2\sum_{x=1}^{\ell}\frac{1}{x^{\alpha-1}}}\geqslant(1-p)^{2}e^{-2/(\alpha-2)}\,.$

We next prove (4). Let $v_{i}$ a node in $V\setminus I_{\mbox{\sc v}}$ at
ring-distance $i+\ell$ from $I_{\mbox{\sc v}}$, i.e., such that
$\min\\{d(w_{1},v_{i}),d(w_{2},v_{i})\\}=i+\ell$. We have:

$\displaystyle\mathbf{Pr}\left(\text{$v_{i}$ is not a neighbor of any node in
$I_{\mbox{\sc v}}$ in $G_{p}$}\right)$
$\displaystyle\geqslant\prod_{x=1}^{\ell}\left(1-\frac{1}{C(\alpha,n)(x+\ell+i)^{\alpha}}\right)\geqslant
e^{-\sum_{x=1}^{\ell}\frac{1}{(x+\ell+i)^{\alpha}}}\geqslant
e^{-\frac{1}{(i+\ell)^{\alpha-1}}}\,.$

Then, let ${(E_{p})_{2}}^{(\ell)}$ denote the set of super-bridges in
${G_{p}}^{(\ell)}$, we use the above inequality to bound the expected number
of super-bridges that are incident in v:

$\displaystyle\mathbf{E}\left[|\mathcal{N}_{{G_{p}}^{(\ell)}}(\mbox{\sc
v})\cap{(E_{p})_{2}}^{(\ell)}|\right]=2\sum_{i=1}^{n/2-\ell}\mathbf{Pr}\left(\text{$v_{i}$
has a neighbor in $I_{\mbox{\sc v}}$}\right)$ $\displaystyle\leqslant
2\sum_{i=1}^{+\infty}1-e^{-\frac{1}{(i+\ell)^{\alpha-1}}}\leqslant
2\sum_{i=1}^{+\infty}\frac{2}{(i+\ell)^{\alpha-1}}\leqslant\frac{2}{(\alpha-2)\ell^{\alpha-2}}.$

Finally, the proof follows from

$\displaystyle\mathbf{Pr}\left(\text{\mbox{\sc v} has a super-bridge in
${G_{p}}^{(\ell)}$}\right)\leqslant\mathbf{E}\left[|\mathcal{N}_{{G_{p}}^{(\ell)}}(\mbox{\sc
v})\cap{(E_{p})_{2}}^{(\ell)}|\right].$

###  B.2 Proof of Lemma 6.2

Let $\underline{p}=1/3$ and consider an arbitrary node $s\in V$. We consider
an execution of the BFS in Algorithm 2 with input the percolation subgraph
$G_{p}=(V,E_{p})$ of $G=(V,E)$ and the source $s$.

Algorithm 2 BFS visit of $G_{p}$

1:Input: the subgraph $G_{p}=(V,E_{p})$, a source $s\in V$

2:$Q=\\{s\\}$

3:$R=\emptyset$

4:while $Q\neq\emptyset$ do

5: $w=\texttt{dequeue}(Q)$

6: $R=R\cup\\{w\\}$

7: for each neighbor $x$ of $w$ in $G_{p}$ such that $x\not\in R$ do

8: $\texttt{enqueue}(x,Q)$

We consider the generic $t$-th iteration of the while loop at line 4 and we
denote by $W_{t}$ the number of nodes added to the queue $Q$ at line 8.
Moreover, $B_{t}$ is the set of nodes that are in $R$ in the $t$-th iteration.
By its definition, $B_{t}$ is a branching process described by the following
recursion:

$\displaystyle\begin{cases}B_{t}=B_{t-1}+W_{t}-1&\quad\text{if $B_{t-1}\neq
0$}\\\ B_{t}=0&\quad\text{if $B_{t-1}=0$}\\\ B_{0}=1.\end{cases}$ (7)

Note that, from Definition 1.1, each node $w\in V$ has expected degree
$\mathbf{E}\left[\deg(w)\right]=3$. So, since each edge in $G$ is also in
$G_{p}$ with probability $p$, we have $\mathbf{E}\left[W_{1}\right]=3p$ and
$\mathbf{E}\left[W_{t}\right]\leqslant 3p$ for $t>1$.101010We have not strict
equality for $t>1$, which follows since the $W_{t}$’s are not independent in
general, since line 8 is only executed if $x\not\in R$. Since
$p<\underline{p}$, there is a constant $\delta$ such that $p=(1-\delta)/3$
and, for each $t\geqslant 0$

$\mathbf{E}\left[W_{t}\right]=1-\delta.$

We consider the $T$-th iteration of the while loop, where $T=\gamma\log n$.
Note that the random variables $W_{1},\ldots,W_{T}$ are not independent as
noted earlier but, as remarked in the proof of Lemma 5.6, it is easy to show
that they are stochastically dominated by $T$ independent random variables
distributed as $W_{1}$. For the sake of simplicity, we abuse notation, by
using $W_{1},\dots,W_{T}$ to denote the $T$ independent copies of $W_{1}$ in
the remainder of this proof. Now, if

$\sum_{i=1}^{T}W_{i}-T<0,$

then $B_{T}=0$. We notice that each $W_{i}$ can be written as a sum of $n+2$
independent Bernoulli random variables.111111Assume node $v$ is visited in the
$t$-iteration. Then we have $2$ indicator variables for the $2$ ring edges
incident in $v$, plus $n$ indicator variables, corresponding to $n$ bridges
potentially incident in $v$. Hence, applying Chernoff’s bound to
$W=\sum_{i=1}^{T}W_{i}$ we obtain:

$\mathbf{Pr}\left(W>(1+\delta)\mathbf{E}\left[W\right]\right)\leqslant
e^{-\frac{\delta^{2}}{2}\mathbf{E}\left[W\right]}.$

Next, since $\mathbf{E}\left[W\right]<(1-\delta)T$,

$\mathbf{Pr}\left(W>(1-\delta^{2})T\right)\leqslant
e^{-\frac{\delta^{2}(1-\delta)}{2}T}\leqslant\frac{1}{n^{2}},$

where the last inequality follows if we take $\gamma\geqslant
4/(\delta^{2}(1-\delta))$. This allows us to conclude that

$\mathbf{Pr}\left(B_{T}=0\right)\geqslant 1-\frac{1}{n^{2}},$

for some $T=\mathcal{O}(\log n)$, which in turn implies that with the above
probability, the connected component of which $v$ is part contains at most
$\mathcal{O}(\log n)$ nodes. Finally, a union bound over all nodes in $V$
concludes the proof.

###  B.3 Proof of Lemma 7.1

We first prove the following fact.

######  Fact B.2.

Under the hypotheses of Lemma 7.1, a constant $c\in(0,1)$ (depending only on
$\alpha$) exists such that, for any $u,v\in V$,

$\mathbf{Pr}\left((u,v)\in E_{p}\right)\geqslant\frac{pc}{n}.$

###### Proof.

The normalizing constant $C(\alpha,n)$ (see Definition 1.1) can be upper
bounded as follows

$C(\alpha,n)=2\sum_{x=2}^{n/2}\frac{1}{x^{\alpha}}\leqslant\frac{2}{2^{\alpha}}+\int_{2}^{n/2}\frac{2}{x^{\alpha}}dx\leqslant
2^{1-\alpha}+\frac{2}{1-\alpha}\left(\frac{n}{2}\right)^{1-\alpha}.$

Hence, a constant $c\in(0,1)$ (depending only on $\alpha$) exists such that

$\displaystyle\mathbf{Pr}\left((u,v)\in E_{p}\right)$
$\displaystyle=\frac{p}{C(\alpha,n)d(u,v)^{\alpha}}\geqslant\frac{p}{C(\alpha,n)(n/2)^{\alpha}}$
$\displaystyle\geqslant\frac{p}{2^{1-\alpha}(n/2)^{\alpha}+n/(1-\alpha)}\geqslant\frac{p\cdot
c}{n}.$

∎

The above fact proves that, when $\alpha<1$, the percolation subgraph $G_{p}$
of a graph sampled from $\mathcal{SW}(n,\alpha)$ stochastically dominates a
cycle with additional Erdős-Rényi random edges. To prove Lemma 7.1 we thus use
a previous result in [3] on such class of random graphs. In particular, we
first give an equivalent formulation of Lemma 5.1 in [3], that states that,
with constant probability the sequential BFS visit (Algorithm 3) reaches
$\Omega(\log n)$ nodes within $\mathcal{O}(\log n)$ rounds. We then consider a
parallel-BFS visit (Algorithm 4) and give an equivalent formulation of Lemma
5.2 in [3], that states that, w.h.p., the parallel-BFS visit starting with
$\Omega(\log n)$ nodes reaches a constant fraction of nodes within
$\mathcal{O}(\log n)$ rounds.

We also introduce a slight different version of the BFS visit of Algorithm 4,
where we have also a set $R_{0}$ of removed nodes in input.

Algorithm 3 BFS visit of $G_{p}$

1:Input: the subgraph $G_{p}=(V,E_{p})$, an initiator $s\subseteq V$, a set of
removed nodes $R_{0}\subseteq V$.

2:$Q=\\{s\\}$

3:$R=R_{0}$

4:while $Q\neq\emptyset$ do

5: $w=\texttt{dequeue}(Q)$

6: $R=R\cup\\{w\\}$

7: for each neighbor $x$ of $w$ in $G_{p}$ such that $x\not\in R$ do

8: $\texttt{enqueue}(x,Q)$

######  Lemma B.3.

Under the hypothesis of Lemma 7.1, let $v\in V$ be a node and $c\in(0,1)$ be a
constant as in Fact B.2. For every $\beta>0$, $\varepsilon>0$, and percolation
probability $p>\frac{\sqrt{c^{2}+6c+1}-c-1}{2c}+\varepsilon$, there are
positive parameters $k$ and $\gamma$ (depending only on $\varepsilon$, $c$ and
$p$) such that the following holds: the BFS visit (Algorithm 3) with input
$G_{p}$, $v$, and a set $R_{0}$ with $|R_{0}|\leqslant\log^{4}n$, with
probability $\gamma$, a time $\tau_{1}=\mathcal{O}(\log n)$ exists such that

$|(R\setminus R_{0})\cup Q|\geqslant n/k\qquad\text{ OR
}\qquad|Q|\geqslant\beta\log n\,.$

Algorithm 4 Parallel BFS visit of $G_{p}$

Input: the subgraph $G_{p}=(V,E_{p})$, a set of initiators $I_{0}\subseteq V$,
a set of removed nodes $R_{0}\subseteq V$

1:$Q=I_{0}$

2:$R=R_{0}$

3:while $Q\neq\emptyset$ do

4: $A=R\cup Q$

5: $X=\text{neighbors}(Q)$

6: $Q^{\prime}=Q$

7: $Q=\emptyset$

8: while $Q^{\prime}\neq\emptyset$ do

9: $w=\texttt{dequeue}(Q^{\prime})$

10: $R=R\cup\\{w\\}$

11: for each $x\in X$ do

12: $\texttt{enqueue}(x,Q)$

######  Lemma B.4.

Under the hypothesis of Lemma 7.1, let $c\in(0,1)$ be a constant as in Fact
B.2. For every $\varepsilon>0$ and percolation probability
$p>\frac{\sqrt{c^{2}+6c+1}-c-1}{2c}+\varepsilon$, there are positive
parameters $k$, $\beta$ (depending only on $c$, $p$ and $\varepsilon$) such
that the following holds: For any pair of sets $I_{0},R_{0}\subseteq V$, with
$|I_{0}|\geqslant\beta\log n$ and $|R_{0}|\leqslant\log^{4}n$, in the parallel
BFS-visit (Algorithm 4) with input $G_{p}$, $I_{0}$, and $R_{0}$, with
probability at least $1-1/n$, a time $\tau_{2}=\mathcal{O}(\log n)$ exists
such that

$|(R\setminus R_{0})\cup Q|\geqslant n/k.$

Now we are ready to prove Lemma 7.1.

###### Proof of Lemma 7.1.

Let $c$ be as in Fact B.2 and $\overline{p}=\frac{\sqrt{c^{2}+6c+1}-c-1}{2c}$.
Let $p>\overline{p}+\varepsilon$, for an arbitrarily-small constant
$\varepsilon>0$, and let $\beta>0$ be the constant in Lemma B.4 and $k$ be the
constant in Lemmas B.3 and B.4. We consider the following process, where we
initialize $R_{0}=\emptyset$ and $\tau_{1}=\mathcal{O}(\log n)$ is as in Lemma
B.3.

  1. 1.

Consider a node $v\in V\setminus R_{0}$.

  2. 2.

From $v$, perform a sequential-BFS visit (Algorithm 2), with input $G_{p}$,
$v$, and $R_{0}$, for $\tau_{1}$ while loops and add to $R_{0}$ the sets $Q$
and $R$ as they are at the end of the $\tau_{1}$-th iteration of the while
loop ($R_{0}=R_{0}\cup R\cup Q$).

  3. 3.

If $|Q|\geqslant\beta\log n$ or $|Q\cup R|\geqslant n/k$, interrupt the
process.

  4. 4.

Restart from $1$.

Let $\gamma>0$ be the constant in Lemma B.3. We prove that the process above
terminates within $\sigma=\log_{1-\gamma}(n)$ iterations, w.h.p.

First we notice that, at each iteration of the process, the set $R_{0}$ grows,
w.h.p., at most of size $\mathcal{O}(\log^{2}n)$, since each node in $G_{p}$
has degree at most $\mathcal{O}(\log n)$, w.h.p. (Fact 4.2) and so, in
$\tau_{1}$ iteration of the parallel-BFS, at most $\mathcal{O}(\log^{2}n)$
nodes will be reached by $v$. This implies that, at each iteration
$i\leqslant\sigma$ of the process $|R_{0}|=\mathcal{O}(\log^{3}n)$, w.h.p.

From Lemma B.3 it follows that,a sequential-BFS with in input $G_{p}$, $v$ and
$R_{0}$ with $|R_{0}|=\mathcal{O}(\log^{3}n)$ is such that, at the end of
$\tau_{1}$-th iteration

$\mathbf{Pr}\left(|Q|\geqslant\beta\log n\text{ or }|R\cup Q|\geqslant
n/k\right)\geqslant\gamma>0\,.$

Therefore, the probability that the process exceeds $\sigma$ iterations is at
most $(1-\gamma)^{\sigma}\leqslant 1/n$.

So, w.h.p., a node $v$ exists such that the sequential-BFS starting from $v$,
after $\mathcal{O}(\log n)$ steps, satisfies at least one of the two
conditions: i) $|Q|\geqslant\beta\log n$ or ii) $|Q\cup R|\geqslant n/k$.

If ii) holds, the lemma is proven. Indeed, w.h.p. we have the existence of a
node $v$ such that there is a set of $\Omega(n)$ nodes at distance at most
$\mathcal{O}(\log n)$ from $v$.

If i) holds, it suffices to perform a sequential-BFS (Algorithm 2) with in
input $G_{p}$, $I_{0}=Q$ and $R_{0}$ and apply Lemma B.4 to claim that such
BFS reaches at least $\Omega(n)$ nodes in $\mathcal{O}(\log n)$ steps. ∎

##  Appendix C Mathematical Tools

######  Theorem C.1 (Chernoff Bound, [15]).

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}$ with $i\in[n]$ are independently
distributed in $[0,1]$. Let $\mu=\mathbf{E}\left[X\right]$ and
$\mu_{L}\leqslant\mu\leqslant\mu_{H}$. Then:

  * •

for every $t>0$

$\mathbf{Pr}\left(X>\mu_{H}+t\right),\mathbf{Pr}\left(X<\mu_{L}-t\right)\leqslant
e^{-2t^{2}/n};$

  * •

for $\varepsilon>0$

$\mathbf{Pr}\left(X>(1+\varepsilon)\mu_{H}\right)\leqslant
e^{-\frac{\epsilon^{2}}{2}\mu_{H}}\ \text{ and }\
\mathbf{Pr}\left(X<(1-\epsilon)\mu_{L}\right)\leqslant
e^{-\frac{\epsilon^{2}}{2}\mu_{L}}.$