# Are giants in random digraphs ‘almost’ local?

Remco van der Hofstad and Manish Pandey

###### Abstract.

Recently, the first author showed that the giant in random undirected graphs
is ‘almost’ local. This means that, under a necessary and sufficient
condition, the limiting proportion of vertices in the giant converges in
probability to the survival probability of the local limit. We extend this
result to the setting of random digraphs, where connectivity patterns are
significantly more subtle. For this, we identify the precise version of local
convergence for digraphs that is needed.

We also determine bounds on the number of strongly connected components, and
calculate its asymptotics explicitly for locally tree-like digraphs, as well
as for other locally converging digraph sequences under the ‘almost-local’
condition for the strong giant. The fact that the number of strongly connected
components is not local once more exemplifies the delicate nature of strong
connectivity in random digraphs.

##  1\. Introduction and main results

###  1.1. Introduction

In the realm of network and graph theory, the study of directed graphs, also
known as digraphs, has gained considerable interest due to their ubiquitous
presence in various real-world applications, such as social networks,
transportation systems, and information flow analysis. Understanding their
connectivity properties is fundamental for gaining insights into the dynamics
of complex systems that are modelled using random digraphs. A strongly
connected component is called a strong giant when its size is asymptotically
linear in the number of vertices. The giant size is crucial for the
understanding of connectivity in a network. There are other notions for graph
components and subsequently giants in digraphs, sometimes called weak giants,
which we discuss in more detail in Section 6.

In this paper, we explore the limiting connectivity structure of locally
converging digraphs. Specifically, our research focuses on the limiting
proportion of vertices in the largest strongly connected component, and the
number of connected components, in these graphs.

Local convergence of random graphs, first introduced in [1, 2], is a well-
studied notion. It describes what a graph looks like locally, as the number of
vertices grows large. It is discussed in detail in [9, Chapter 2] for
undirected graphs, and in [9, Section 9.2] for digraphs. When the local limit
of a sequence of random graphs/digraphs is known, we are able to predict
properties about the graph that are continuous with respect to the local
topology.

For undirected graphs, the number of vertices in the largest connected
component, which is also called the giant, is _not_ continuous under the local
topology, but [8] shows that this quantity is ‘almost’ local. Indeed, the
proportion of vertices in the giant converges to the survival probability of
the local limit if and only if a certain condition holds. In this paper we
show that the giant strongly connected component is also ‘almost’ local for
the case of random digraphs.

The difference between the directed and the undirected case is quite delicate.
One example to illustrate this subtlety is through the number of connected
components. In the undirected case, the asymptotics for the number of
connected components can easily be obtained since it is continuous in the
local topology. In contrast, the directed case turns out to be much more
complex due the stronger, and less local, notion of connectivity. In
particular, it is an open question whether it is ‘almost’ local or not, which
we answer affirmatively in this paper.

Connectivity properties of random digraphs have attracted substantial
attention. The diameter of the directed configuration model is studied in [3],
the size of the largest strongly connected component of a random digraph with
prescribed degrees in [4], Weak components of the directed configuration model
in [5], percolation in simple random digraphs with prescribed degrees in [11],
and graph distances in [10].

###  1.2. Preliminaries

In this section, we discuss different types of connected components in
digraphs, and informally introduce the notion of local convergence in directed
random graphs.

Let $G=(V(G),E(G))$ be a digraph. We denote the length of the shortest
directed path between $u,v\in V(G)$ by $d_{G}(u,v)$. We define
$d_{G}(u,v)=\infty$ if there is no directed path between $u$ and $v$. In
digraphs, the distance is not symmetric, i.e., $d_{G}(u,v)\neq d_{G}(v,u)$.

######  Definition 1.1 (Vertex-induced subgraph).

Let $G=(V(G),E(G))$ be a digraph and $U\subset V(G)$. Then, the digraph
induced by the vertex set $U$, which we denote by $G[U]$, is the digraph
obtained by removing all the vertices in $U^{c}=V(G)\setminus U$, along with
the edges incident to these vertices, from $G$. $\blacktriangleleft$

######  Definition 1.2 (Strongly connected component of a vertex).

Fix $v\in V(G)$, then we let $\mathscr{C}_{v}$ be the strongly connected
component of $v$, defined as

$\displaystyle\mathscr{C}_{v}:=G\left[\\{x\in V(G)\colon
d_{G}(x,v)<\infty,d_{G}(v,x)<\infty\\}\right].$ (1.1)

$\blacktriangleleft$

######  Definition 1.3 (In- and out-component, weak components of a vertex).

Fix $v\in V(G)$, then we let $\mathscr{C}^{\scriptscriptstyle-}_{v}$ and
$\mathscr{C}^{\scriptscriptstyle+}_{v}$ to be the in- and out-component of
$v$, respectively, defined as

$\displaystyle\mathscr{C}^{\scriptscriptstyle-}_{v}$
$\displaystyle:=G\left[\\{x\in V(G)\colon d_{G}(x,v)<\infty\\}\right],$ (1.2)
$\displaystyle\mathscr{C}^{\scriptscriptstyle+}_{v}$
$\displaystyle:=G\left[\\{x\in V(G)\colon d_{G}(v,x)<\infty\\}\right].$ (1.3)

$\blacktriangleleft$

The strongly connected components of a digraph partitions the vertex set. Let
$(\mathscr{C}_{\scriptscriptstyle(i)})_{i\geq 1}$ denote the unique partition
formed by the strongly connected components of $G_{n}$, ordered in such a way
that
$|\mathscr{C}_{\scriptscriptstyle(1)}|\geq|\mathscr{C}_{\scriptscriptstyle(2)}|\geq|\mathscr{C}_{\scriptscriptstyle(3)}|\geq\cdots$,
where $|\cdot|$ denote the size of the vertex set and ties are broken
arbitrarily. Thus, $\mathscr{C}_{\scriptscriptstyle(1)}$ is the largest
strongly connected component(LSCC) of the graph, which we also denote by
$\mathscr{C}_{\max}$.

##### Local convergence in random digraphs.

Local convergence of random digraphs describes what a digraph locally looks
like from the perspective of a uniformly chosen vertex, as the number of
vertices in the digraph tends to infinity. For example, the sparse Erdős-Rényi
random digraph, which is formed by bond percolation on the complete digraph of
size $n$ with probability $p=\lambda/n$, locally looks like a Poisson
branching process with parameter $\lambda$ in both directions, as $n$ tends to
infinity.

Now let us give the informal definition of local convergence. We write
$X_{n}\overset{\scriptscriptstyle\mathbb{P}}{\to}X$ when $X_{n}$ converges in
probability to $X$.

######  Definition 1.4 (Forward-backward neighbourhood).

Let $G$ be a digraph and $v\in V(G)$. Then $B_{r}^{\scriptscriptstyle(G)}(v)$
is the rooted digraph with root $v$, induced by the vertex set
$V(B_{r}^{\scriptscriptstyle(G)}(v))$, where

$V(B_{r}^{\scriptscriptstyle(G)}(v))=\left\\{u\in
V(G)\colon\min\\{d_{G}(u,v),d_{G}(v,u)\\}<r\right\\},$ (1.4)

where a rooted digraph is a digraph with a distinguished vertex, called a
root, defined formally in Definition 2.1. $\blacktriangleleft$

######  Definition 1.5 (Digraph isomorphism).

Two digraphs, $G_{1}$ and $G_{2}$ are said to be directed isomorphic if there
exists a bijection $\phi\colon V(G_{1})\to V(G_{2})$ such that
$(v_{1},v_{2})\in E(G_{1})$ precisely when $(\phi(v_{1}),\phi(v_{2}))\in
E(G_{1})$. This is abbreviated as $G_{1}\cong G_{2}$. $\blacktriangleleft$

######  Definition 1.6 (Rooted digraph isomorphism).

Two rooted digraphs, $(G_{1},o_{1})$ and $(G_{2},o_{2})$ are said to be
directed isomorphic if there exists a bijection $\phi\colon V(G_{1})\to
V(G_{2})$ such that $(v_{1},v_{2})\in E(G_{1})$ precisely when
$(\phi(v_{1}),\phi(v_{2}))\in E(G_{1})$. In addition to this, it should also
hold that $\phi(o_{1})=o_{2}$. This is abbreviated as
$(G_{1},o_{1})\cong(G_{2},o_{2})$. $\blacktriangleleft$

We will rely on two types of local convergence, namely, forward-backward local
weak convergence and forward-backward local convergence in probability. Let
$o_{n}$ denote a uniformly chosen vertex from $V(G_{n})$. Forward-backward
local weak convergence means that

$\mathbb{P}\left({B_{r}^{\scriptscriptstyle(G_{n})}(o_{n})\cong(H,o^{\prime})}\right)\to\bar{\mu}(B_{r}^{\scriptscriptstyle(\bar{G})}(o)\cong(H,o^{\prime})),$
(1.5)

for all rooted digraphs $(H,o^{\prime})$. In (1.5), $(\bar{G},o)\sim\bar{\mu}$
is a random rooted graph, which is called the forward-backward local weak
limit. For forward-backward 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\mathbb{P}}{\to}\mu(B_{r}^{\scriptscriptstyle(G)}(o)\cong(H,o^{\prime}))$
(1.6)

to hold for all rooted digraphs $(H,o^{\prime})$. In (1.6), $(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.5) and (1.6) describe the convergence of the proportions of vertices around
which the digraph locally looks like a certain specific digraph.

######  Remark 1.1 (Other notions of local convergence of digraphs).

Other notions of local convergence of digraphs exist. For example, one can
consider digraphs as undirected graphs with marks on the edges that indicate
their directions. Then one can define marked local convergence of such marked
undirected graphs. This notion is much stronger than forward-backward local
convergence. Further, sometimes only one direction is relevant. An example
arises in the study of the local limit of the PageRank distribution on a
digraph, as studied in [6]. There, the in-component matters, with as extra
vertex marks the out-degree of the vertices. We see that convergence of
different digraph properties require different local convergence notions.
Forward-backward convergence is exactly what we need for the convergence of
the strong giant and the number of strongly connected components.
$\blacktriangleleft$

We discuss the definition of forward-backward local convergence more formally
in Section 2. We now turn to our main results.

###  1.3. Main results

Our main results are divided into three subsections, the ‘almost’ locality of
the giant, the local limit of the giant, and the number of strongly connected
components.

####  1.3.1. Strong giant is ‘almost’ local

In this section we state a condition for the existence and size of a giant in
a sequence of random digraphs that converges locally in probability in the
forward-backward sense. We start by showing a generic probabilistic upper
bound on the size of the strong giant on random digraph sequences converging
locally in probability:

######  Theorem 1.1 (Upper bound on size of strong giant).

Let $(G_{n})_{n\geq 1}$ be a sequence of random digraphs, of size
$|V(G_{n})|=n$, converging locally in probability in the forward-backward
sense to $(G,o)\sim\mu$. Let
$\zeta=\mu(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty)$.
Then, for all $\varepsilon>0$,

$\mathbb{P}\left(\frac{|\mathscr{C}_{\max}|}{n}\geq\zeta+\varepsilon\right)\to
0.$ (1.7)

Theorem 1.1 implies that
$\zeta=\mu(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty)$
is always an upper bound on the size of the strong giant in locally converging
digraph sequences.

Next, we proceed towards a matching lower bound, for which we will state a
necessary and sufficient condition. Define

$N^{k}_{n}:=\\#\\{(x,y)\in
V(G_{n}):|\mathscr{C}^{\scriptscriptstyle-}_{x}|,|\mathscr{C}^{\scriptscriptstyle+}_{x}|,|\mathscr{C}^{\scriptscriptstyle-}_{y}|,|\mathscr{C}^{\scriptscriptstyle+}_{y}|\geq
k,x\nleftrightarrow y\\},$ (1.8)

which is the number of vertex pairs that have large in- and out-components but
are not in the same strongly connected component. In (1.8), $x\nleftrightarrow
y$ means that either $x$ is not connected to $y$, or $y$ is not connected to
$x$ (i.e., $x$ and $y$ are in different strongly connected components). Then,
our main result on the ‘almost-local’ nature of the strong giant is as
follows:

######  Theorem 1.2 (Strong giant is ‘almost’ local).

Let $(G_{n})_{n\geq 1}$ be a sequence of random digraphs, of size
$|V(G_{n})|=n$, converging locally in probability in the forward-backward
sense to $(G,o)\sim\mu$. Assume that

$\lim_{k\to\infty}\limsup_{n\to\infty}\frac{1}{n^{2}}\mathbb{E}\left[N^{k}_{n}\right]=0.$
(1.9)

Then

$\displaystyle\frac{|\mathscr{C}_{\max}|}{n}\overset{\scriptscriptstyle\mathbb{P}}{\to}\zeta=\mu(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty),\qquad\frac{|\mathscr{C}_{\scriptscriptstyle(2)}|}{n}\overset{\scriptscriptstyle\mathbb{P}}{\to}0.$
(1.10)

Under the assumption of forward-backward local convergence in probability, the
condition in (1.9) is necessary and sufficient for (1.10) to hold.

######  Remark 1.2 (The limiting value).

One might have expected Theorem 1.2 to hold under different conditions with a
different limit. Indeed, one may have thought that
$|\mathscr{C}_{\max}|/n\overset{\scriptscriptstyle\mathbb{P}}{\to}\mu(|\mathscr{C}_{o}|=\infty)$,
which might be true in some cases. However, in many directed random graphs,
the local limit is a tree in that $\mathscr{C}^{\scriptscriptstyle-}_{o}$ and
$\mathscr{C}^{\scriptscriptstyle+}_{o}$ are disjoint trees $\mu-$almost
surely. In such cases, $\mu(|\mathscr{C}_{o}|=\infty)=0$, while
$|\mathscr{C}_{\max}|/n\overset{\scriptscriptstyle\mathbb{P}}{\to}\zeta>0$ can
occur. This exemplifies the subtleties of strongly connected components in the
directed setting. It would be of interest to find examples for which
$\mu(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty)=\mu(|\mathscr{C}_{o}|=\infty).$
$\blacktriangleleft$

######  Remark 1.3 (Comparison to undirected setting).

The subtleties described in Remark 1.2 are not present in the undirected
setting, where
$|\mathscr{C}_{\max}|/n\overset{\scriptscriptstyle\mathbb{P}}{\to}\mu(|\mathscr{C}_{o}|=\infty)$
and $\mathscr{C}_{o}$ is the undirected connected component in $(G,o)$. This
can be understood by noting that if $u\in B_{r}^{\scriptscriptstyle(G)}(v)$ in
the undirected setting, then we know that $u\in\mathscr{C}_{v}$, while if
$u\in B_{r}^{\scriptscriptstyle(G)}(v)$ in the directed setting, then we do
not know that $u\in\mathscr{C}_{v}$. $\blacktriangleleft$

######  Remark 1.4 (Applications of Theorem 1.2).

Theorem 1.2 can be applied to the directed Erdős-Rényi random graph model, and
the directed configuration model with appropriate regularity conditions on the
degree distribution. Condition (1.9) for these models can be shown using
coupling arguments similar to the ones used in [9, Section 2.3] and [8],
respectively. We do not provide more details. $\blacktriangleleft$

######  Remark 1.5 (Simplification of condition in Theorem 1.2).

It is possible to simplify the conditions in Theorem 1.2. Indeed, define

$N^{k}_{n}(2)=\\#\\{(x,y)\in
V(G_{n}):|\mathscr{C}^{\scriptscriptstyle-}_{x}|,|\mathscr{C}^{\scriptscriptstyle+}_{x}|,|\mathscr{C}^{\scriptscriptstyle-}_{y}|,|\mathscr{C}^{\scriptscriptstyle+}_{y}|\geq
k,x\nrightarrow y\\},$ (1.11)

where $x\nrightarrow y$ means that there is no directed path from $x$ to $y$.
In Lemma 3.2 below, we show that $N^{k}_{n}(2)\leq N^{k}_{n}\leq
2N^{k}_{n}(2)$. Thus, one can replace $N^{k}_{n}$ by $N^{k}_{n}(2)$ in (1.9).
$\blacktriangleleft$

####  1.3.2. Local limit of the giant

In this section, we discuss the local convergence of the giant. Denote the
number of vertices $v$ in the giant component satisfying
$(d_{v}^{\scriptscriptstyle-},d_{v}^{\scriptscriptstyle+})=(l,m)$ by
$v_{1}(l,m)$. Then, we have the following asymptotics for $v_{1}(l,m)$:

######  Theorem 1.3 (Limiting degree distribution of the giant).

Under the assumptions of Theorem 1.2,

$\frac{v_{1}(l,m)}{n}\overset{\scriptscriptstyle\mathbb{P}}{\to}\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty,D_{o}=(l,m)\right).$
(1.12)

Further, when $D^{\scriptscriptstyle-}_{o_{n}}$ and
$D^{\scriptscriptstyle+}_{o_{n}}$ are both uniformly integrable,

$\frac{|E(\mathscr{C}_{\max})|}{n}\overset{\scriptscriptstyle\mathbb{P}}{\to}\frac{1}{2}\mathbb{E}[\left(D_{o}^{\scriptscriptstyle-}+D_{o}^{\scriptscriptstyle+}\right)\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty\\}}].$
(1.13)

The next theorem tells us what the strong giant and its complement look like
locally:

######  Theorem 1.4 (Local limit of the strong giant and its complement).

Under the assumptions of Theorem 1.2,

$\frac{1}{n}\sum_{v\in\mathscr{C}_{\max}}\mathbbm{1}_{\left\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\cong
H_{\star}\right\\}}\overset{\scriptscriptstyle\mathbb{P}}{\longrightarrow}\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty,B_{r}^{\scriptscriptstyle(G)}(o)\cong
H_{\star}\right),$ (1.14)

and

$\frac{1}{n}\sum_{v\notin\mathscr{C}_{\max}}\mathbbm{1}_{\left\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\cong
H_{\star}\right\\}}\overset{\scriptscriptstyle\mathbb{P}}{\longrightarrow}\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|<\infty,B_{r}^{\scriptscriptstyle(G)}(o)\cong
H_{\star}\right).$ (1.15)

####  1.3.3. Number of strongly connected components

In this section, we discuss the number of strongly connected components of
digraph sequences having a local limit:

######  Theorem 1.5 (Limiting number of SCCs).

Under the assumptions of Theorem 1.2, and further assuming that
$|\mathscr{C}_{\max}|\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\infty$
when $\zeta=0$,

$\frac{K_{n}}{n}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mathbb{E}_{\mu}\Bigg{[}\frac{1}{|\mathscr{C}(o)|}\mathbbm{1}_{\\{|\mathscr{C}^{-}(o)|<\infty\\}\cup\\{|\mathscr{C}^{+}(o)|<\infty\\}}\Bigg{]}.$
(1.16)

######  Remark 1.6 (Comparison to undirected setting).

In the undirected setting,
$K_{n}/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mathbb{E}_{\mu}[1/|\mathscr{C}(o)|]$
always holds when $G_{n}$ converges locally in probability, i.e., we do not
need to rely on the additional ‘giant-is-almost-local condition’ that is the
undirected equivalent of (1.9). This once again shows that strong connectivity
in digraphs is a more delicate notion than connectivity in undirected graphs.
Having Theorem 1.2 in mind, we can think of

$\mathbbm{1}_{\\{|\mathscr{C}^{-}(o)|<\infty\\}\cup\\{|\mathscr{C}^{+}(o)|<\infty\\}}=1-\mathbbm{1}_{\\{|\mathscr{C}^{-}(o)|=\infty\\}\cap\\{|\mathscr{C}^{+}(o)|=\infty\\}}$

as enforcing that $o$ is in the limit of the strong giant.
$\blacktriangleleft$

We next give a simpler limiting result for locally tree-like digraphs, which
we first define:

######  Definition 1.7 (Locally tree-like digraphs).

We say that a sequence of digraphs $(G_{n})_{n\geq 1}$ is _locally tree-like_
when the sequence converges locally in probability to $(G,o)\sim\mu$, which is
almost surely a random directed tree. By directed tree we mean that the
strongly connected component of each vertex is almost surely the vertex itself
i.e., a graph with no directed cycles. Directed configuration models, directed
Erdős-Rényi models, etc. are all locally tree-like digraphs.
$\blacktriangleleft$

######  Theorem 1.6 (Number of SCCs in locally tree-like digraphs).

Let $(G_{n})_{n\geq 1}$ be a sequence of random digraphs, of size
$|V(G_{n})|=n$, converging locally in probability in the forward-backward
sense to $(G,o)\sim\mu$, which is a random directed tree. Then, under the
assumption of Theorem 1.2,

$\frac{K_{n}}{n}\overset{\scriptscriptstyle\mathbb{P}}{\longrightarrow}1-\zeta.$
(1.17)

######  Remark 1.7 (Locally tree-like digraphs are special).

The limiting value for the number of strongly connected components in Theorem
1.5, if computed for locally tree-like digraphs, matches with the expression
in Theorem 1.6. Thus, Theorem 1.6 tells us that we do not need additional
conditions for locally tree-like digraphs, as in Theorem 1.5.
$\blacktriangleleft$

######  Remark 1.8 (Upper bound in terms of $\zeta$).

The upper bound in Theorem 1.6 holds more generally. Indeed, the bound

$\frac{K_{n}}{n}\leq 1-\frac{|\mathscr{C}_{\max}|}{n}+\frac{1}{n}$ (1.18)

always holds. Thus, under the assumptions of Theorem 1.6, whp for every
$\varepsilon>0$,

$\frac{K_{n}}{n}\leq 1-\zeta+\varepsilon.$ (1.19)

$\blacktriangleleft$

######  Remark 1.9 (Comparison of proofs between directed and undirected
graphs).

The complexity of proofs in digraphs in comparison to undirected graphs varies
depending on the connectivity property we are investigating. In particular,
the proofs for the size of the strong giant are similar to the proofs used for
the undirected case in [8]. In contrast, for digraphs, the number of connected
components is a non-local quantity, whereas, for undirected graphs, it is
local. Thus, the proof becomes more complicated and less general.
$\blacktriangleleft$

##  2\. Local convergence in digraphs

In this section, we formally define the notion of forward-backward local weak
convergence and local convergence in probability for digraphs. There are
several versions of local convergence in random digraphs. Amongst these, the
four most commonly discussed are forward, backward, forward-backward, and
marked (see Remark 1.1).

We start by defining rooted digraphs:

######  Definition 2.1 (Rooted digraph).

A digraph is $G=(V(G),E(G))$ together with a vertex $o\in V(G)$ is called a
rooted digraph. We denote a rooted digraph $G$ with root $o\in V(G)$ by
$(G,o)$. $\blacktriangleleft$

Next we define the forward-backward metric space over the rooted digraphs:

######  Definition 2.2 (Metric space).

Let $\mathscr{G}_{\star}$ be the space of all rooted digraphs. Let
$(G_{1},o_{1}),$ $(G_{2},o_{2})\in\mathscr{G}_{\star}$. Define the metric
$d_{\scriptscriptstyle\mathscr{G}_{\star}}\colon\mathscr{G}_{\star}\times\mathscr{G}_{\star}\to\mathbb{R}_{\geq
0}$ by

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

where $R^{\star}$ is given by

$\displaystyle R^{\star}:=$ $\displaystyle\sup\\{r\geq 0\text{ s.t.
}B^{\scriptscriptstyle(G_{1})}_{r}(o_{1})\cong
B^{\scriptscriptstyle(G_{2})}_{r}(o_{2})\\},$

where $\cong$ denotes rooted digraph isomorphism defined in Definition 1.6.
$\blacktriangleleft$

######  Remark 2.1 (Equivalence classes).

Obviously, $R^{\star}=\infty$ when $(G_{1},o_{1})\cong(G_{2},o_{2})$ so that
$d_{\scriptscriptstyle\mathscr{G}_{\star}}((G_{1},o_{1}),(G_{2},o_{2}))=0.$
Therefore, $d_{\scriptscriptstyle\mathscr{G}_{\star}}$ defines a metric on the
equivalence classes of isomorphic digraphs. $\blacktriangleleft$

######  Definition 2.3 (Forward-backward local convergence in probability of
digraphs).

The sequence $(G_{n})_{n\geq 1}$ of random digraphs is said to converge
locally in probability to the random rooted digraph $(G,o)$, a random variable
taking values in $\mathscr{G}_{\star}$ having law $\mu$, as $n\to\infty$, if
for every continuous and bounded function
$f\colon\mathscr{G}_{\star}\to\mathbb{R}$ in the forward-backward metric,

$\mathbb{E}_{n}[f(G_{n},o_{n})]\overset{\scriptscriptstyle\mathbb{P}}{\longrightarrow}\mathbb{E}_{\mu}[f(G,o)],$
(2.2)

where $o_{n}$ is a uniformly chosen vertex from $V(G_{n})$.
$\blacktriangleleft$

##  3\. Giants in converging digraphs: Proofs of Theorems 1.1 & 1.2

In this section we derive a condition for the existence of a giant in a
sequence of random digraphs that converges locally in probability in the
forward-backward sense. We start by proving the generic probabilistic upper
bound on the size of the strong giant in Theorem 1.1.

###### Proof of Theorem 1.1.

Let $Z_{\geq k}$ be the number of vertices in $G_{n}$ having in- and out-
components size at least $k$, i.e.,

$Z_{\geq k}=\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq k\\}}.$ (3.1)

Let $\zeta_{\geq k}=\mu(|\mathscr{C}^{\scriptscriptstyle-}_{o}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{o}|\geq k)$. Then, taking $k\to\infty$,
we have $\zeta_{\geq
k}\to\mu(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty)$.

Notice that
$(G,o)\mapsto\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq k\\}}$ is a bounded continuous
function in the forward-backward sense of random digraphs, and thus due to the
forward-backward local convergence in probability, $Z_{\geq
k}/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta_{\geq
k}$. Therefore, for all $\varepsilon>0$,

$\mathbb{P}\left(\Big{|}\frac{Z_{\geq k}}{n}-\zeta_{\geq
k}\Big{|}>\varepsilon\right)\to 0.$ (3.2)

Also, $\zeta_{\geq k}\to\zeta$ as $k\to\infty$, which means that there exists
$K\in\mathbb{N}$ such that $\zeta_{\geq k}\leq\zeta+\varepsilon/2$ for all
$k\geq K$. Further, $\left\\{|\mathscr{C}_{\max}|\geq
x\right\\}\subseteq\left\\{Z_{\geq k}\geq x\right\\}$, for every $x\geq 1$.
Thus,

$\mathbb{P}\left(\frac{|\mathscr{C}_{\max}|}{n}\geq\zeta+\varepsilon\right)\leq\mathbb{P}\left(\frac{|\mathscr{C}_{\max}|}{n}\geq\zeta_{\geq
k}+\frac{\varepsilon}{2}\right)\leq\mathbb{P}\left(\frac{Z_{\geq
k}}{n}\geq\zeta_{\geq k}+\frac{\varepsilon}{2}\right)\to 0.$ (3.3)

This completes the proof. ∎

######  Remark 3.1 (In- and out-components of strongly connected components).

Each vertex in a strongly connected component has the same in- and out-
component. This is illustrated in Figure 2 for the largest strongly connected
component. We denote the in- and out-component associated with
$\mathscr{C}_{\scriptscriptstyle(i)}$ by
$\mathscr{C}^{\scriptscriptstyle-}_{\scriptscriptstyle(i)}$ and
$\mathscr{C}^{\scriptscriptstyle+}_{\scriptscriptstyle(i)}$, respectively.
$\blacktriangleleft$

In the remainder of the proof, the following notation will be essential:

######  Notation 3.1.

Suppose $(X_{n})_{n\geq 1}$ and $(X_{n,k})_{n\geq 1,k\geq 1}$ are sequences of
random variables. We write $X_{n,k}=o_{k,\scriptscriptstyle\mathbb{P}}(X_{n})$
when

$\lim_{k\to\infty}\limsup_{n\to\infty}\mathbb{P}\left(|X_{n,k}|>\varepsilon|X_{n}|\right)=0.$

$\blacktriangleleft$

######  Lemma 3.1 (Sum of squares of cluster sizes).

Under the assumptions of Theorem 1.2,

$\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{(i)}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{(i)}|\geq
k\\}}=\zeta^{2}+o_{k,\scriptscriptstyle\mathbb{P}}(1).$ (3.4)

###### Proof.

By Remark 3.1, we can rewrite $Z_{\geq k}$ in (3.1) as

$Z_{\geq k}=\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq k\\}}=\sum_{i\geq
1}|\mathscr{C}_{(i)}|\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{(i)}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{(i)}|\geq k\\}}.$ (3.5)

Squaring (3.5) gives

$Z_{\geq k}^{2}=\sum_{i\geq
1}|\mathscr{C}_{(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{(i)}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{(i)}|\geq k\\}}+\sum_{i\neq
j}|\mathscr{C}_{(i)}||\mathscr{C}_{(j)}|\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{(i)}|,|\mathscr{C}^{\scriptscriptstyle+}_{(i)}|,|\mathscr{C}^{\scriptscriptstyle-}_{(j)}|,|\mathscr{C}^{\scriptscriptstyle+}_{(j)}|\geq
k\\}}.$ (3.6)

The second cross-product term counts the number of pairs of vertices that are
not in the same strongly connected component, but have at least $k$ vertices
in their in- and out-components. Thus, by (1.8),

$\frac{Z_{\geq k}^{2}}{n^{2}}=\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{(i)}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{(i)}|\geq
k\\}}+\frac{1}{n^{2}}N^{k}_{n}.$ (3.7)

Fix $\varepsilon>0$. By the Markov inequality,

$\lim_{k\to\infty}\limsup_{n\to\infty}\mathbb{P}\left(\frac{1}{n^{2}}N^{k}_{n}>\varepsilon\right)\leq\lim_{k\to\infty}\limsup_{n\to\infty}\frac{1}{\varepsilon
n^{2}}\mathbb{E}\left[N^{k}_{n}\right]=0,$ (3.8)

Thus, $N^{k}_{n}=o_{k,\scriptscriptstyle\mathbb{P}}(n^{2})$, proving (3.4).
This completes the proof. ∎

Next we prove Theorem 1.2:

###### Proof of Theorem 1.2.

Due to Theorem 1.1, it is sufficient to show (1.10) for $\zeta>0$. Thus, we
assume that $\zeta>0$. Observe that

$\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{(i)}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{(i)}|\geq
k\\}}\leq\frac{|\mathscr{C}_{\max}|}{n}\frac{1}{n}\sum_{i\geq
1}|\mathscr{C}_{(i)}|\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{(i)}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{(i)}|\geq k\\}},$ (3.9)

which means that

$\frac{|\mathscr{C}_{\max}|}{n}\geq\frac{\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{(i)}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{(i)}|\geq k\\}}}{\frac{1}{n}\sum_{i\geq
1}|\mathscr{C}_{(i)}|\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{(i)}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{(i)}|\geq
k\\}}}=\frac{\zeta^{2}+o_{k,\scriptscriptstyle\mathbb{P}}(1)}{\zeta_{\geq
k}+o_{\scriptscriptstyle\mathbb{P}}(1)}.$ (3.10)

Letting $k\to\infty$ in (3.9), for all $\varepsilon>0$, we get

$\lim_{n\to\infty}\mathbb{P}\left(\frac{|\mathscr{C}_{\max}|}{n}\geq\zeta-\varepsilon\right)=1.$
(3.11)

Equation (3.11), combined with Theorem 1.1, completes the proof of the law of
large numbers on the strong giant under the condition (1.9) in Theorem 1.2.

Next we show that (1.9) is also a necessary condition for the giant component
to converge to $\zeta$. Suppose that the condition in (1.9) fails. This
implies that

$\limsup_{k\to\infty}\limsup_{n\to\infty}\frac{1}{n^{2}}\mathbb{E}[N_{n}^{k}]=\kappa>0.$
(3.12)

In turn, this implies that there exists a subsequence $(n_{l})_{l\geq 1}$ such
that

$\lim_{l\to\infty}\limsup_{k\to\infty}\frac{1}{n_{l}^{2}}\mathbb{E}[N_{n_{l}}^{k}]=\kappa.$
(3.13)

Thus, along the subsequence $(n_{l})_{l\geq 1}$,

$\displaystyle\frac{1}{n_{l}^{2}}\mathbb{E}\left[|\mathscr{C}_{\max}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\max}^{+}|\geq
k,|\mathscr{C}_{\max}^{-}|\geq k\\}}\right]$
$\displaystyle\leq\frac{1}{n_{l}^{2}}\mathbb{E}\left[\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}^{+}|\geq
k,|\mathscr{C}_{\scriptscriptstyle(i)}^{-}|\geq k\\}}\right]$
$\displaystyle=\frac{1}{n_{l}^{2}}\mathbb{E}[Z_{\geq
k}^{2}-N_{n_{l}}^{k}]\to\zeta_{\geq k}^{2}-\kappa.$

Notice that

$\displaystyle\frac{1}{n_{l}^{2}}\mathbb{E}\left[|\mathscr{C}_{\max}|^{2}\right]$
$\displaystyle=\frac{1}{n_{l}^{2}}\mathbb{E}\left[|\mathscr{C}_{\max}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\max}^{+}|\geq
k,|\mathscr{C}_{\max}^{-}|\geq k\\}}\right]$ (3.14)
$\displaystyle\qquad+\frac{1}{n_{l}^{2}}\mathbb{E}\left[|\mathscr{C}_{\max}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\max}^{+}|<k\\}\cup\\{|\mathscr{C}_{\max}^{-}|<k\\}}\right].$

We know that $|\mathscr{C}_{\max}^{\pm}|\geq|\mathscr{C}_{\max}|$. Thus,

$\\{|\mathscr{C}_{\max}^{+}|<k\\}\cup\\{|\mathscr{C}_{\max}^{-}|<k\\}\subseteq\\{|\mathscr{C}_{\max}|<k\\},$

so that, in turn,

$\frac{1}{n_{l}^{2}}\mathbb{E}\left[|\mathscr{C}_{\max}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\max}^{+}|<k\\}\cup\\{|\mathscr{C}_{\max}^{-}|<k\\}}\right]\leq\left(\frac{k}{n_{l}}\right)^{2}\to
0,$ (3.15)

as $n_{l}\to\infty$. This implies

$\lim_{l\to\infty}\frac{1}{n_{l}^{2}}\mathbb{E}[|\mathscr{C}_{\max}|^{2}]\leq\zeta^{2}-\kappa<\zeta^{2}.$
(3.16)

We conclude that
$|\mathscr{C}_{\max}|/n\overset{\scriptscriptstyle\mathbb{P}}{\to}\zeta$
cannot hold. This is because by the bounded convergence theorem, it would
imply that
$\mathbb{E}\left[\left(|\mathscr{C}_{\max}|/n\right)^{2}\right]\to\zeta^{2}$
which gives a contradiction with (3.16). ∎

Recall the definition of $N_{n}^{k}$ in (1.8), and that of $N_{n}^{k}(2)$ in
(1.11). We now show that both are of the same order of magnitude:

######  Lemma 3.2 (Relaxing the assumption).

$N^{k}_{n}(2)\leq N^{k}_{n}\leq 2N^{k}_{n}(2).$

###### Proof.

For $x,y\in V(G_{n})$ we define the events $A_{x,y}$ and $B_{x,y}$ as

$\displaystyle
A_{x,y}=\left[|\mathscr{C}^{\scriptscriptstyle-}_{x}|,|\mathscr{C}^{\scriptscriptstyle+}_{x}|,|\mathscr{C}^{\scriptscriptstyle-}_{y}|,|\mathscr{C}^{\scriptscriptstyle+}_{y}|\geq
k,x\nrightarrow y\right],$ (3.17) $\displaystyle
B_{x,y}=\left[|\mathscr{C}^{\scriptscriptstyle-}_{x}|,|\mathscr{C}^{\scriptscriptstyle+}_{x}|,|\mathscr{C}^{\scriptscriptstyle-}_{y}|,|\mathscr{C}^{\scriptscriptstyle+}_{y}|\geq
k,x\nleftarrow y\right].$ (3.18)

Then,

$\displaystyle N^{k}_{n}$ $\displaystyle=\sum_{(x,y)\in
V(G_{n})^{2}}\\!\\!\\!\\!\mathbbm{1}_{A_{x,y}\cup B_{x,y}},\qquad
N^{k}_{n}(2)=\sum_{(x,y)\in
V(G_{n})^{2}}\\!\\!\\!\\!\mathbbm{1}_{A_{x,y}}=\sum_{(x,y)\in
V(G_{n})^{2}}\\!\\!\\!\\!\mathbbm{1}_{B_{x,y}}.$ (3.19)

Using the fact $\mathbbm{1}_{A}\leq\mathbbm{1}_{A\cup
B}\leq\mathbbm{1}_{A}+\mathbbm{1}_{B}$, we get

$\displaystyle N^{k}_{n}(2)=\sum_{(x,y)\in
V(G_{n})^{2}}\\!\\!\\!\\!\mathbbm{1}_{A_{x,y}}\leq N^{k}_{n}\leq\sum_{(x,y)\in
V(G_{n})^{2}}\\!\\!\\!\\!\left(\mathbbm{1}_{A_{x,y}}+\mathbbm{1}_{B_{x,y}}\right)=2N^{k}_{n}(2),$
(3.20)

which completes the proof. ∎

##  4\. Local limit of the giant: Proof of Theorems 1.3 & 1.4

In this section we prove local limit properties of the giant component:

###### Proof of Theorem 1.3.

When $\zeta=0$, there is nothing to prove, so we may again assume that
$\zeta>0$. For $A\subseteq\mathbb{N}^{2}$, we define

$Z_{A,\geq k}=\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|,|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq
k,(d^{\scriptscriptstyle-}_{v},d^{\scriptscriptstyle+}_{v})\in A\\}}.$ (4.1)

Assuming that $G_{n}$ converges locally in probability in the forward-backward
sense, we get

$\frac{Z_{A,\geq
k}}{n}\overset{\scriptscriptstyle\mathbb{P}}{\to}\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|,|\mathscr{C}^{\scriptscriptstyle+}_{o}|\geq
k,(d^{\scriptscriptstyle-}_{o},d^{\scriptscriptstyle+}_{o})\in A\right).$
(4.2)

Since $|\mathscr{C}_{\max}|>k$ with high probability (it is here that we use
that $\zeta>0$), we have

$\frac{1}{n}\sum_{(l,m)\in A}v_{1}(l,m)\leq\frac{Z_{A,\geq
k}}{n}\overset{\scriptscriptstyle\mathbb{P}}{\to}\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|,|\mathscr{C}^{\scriptscriptstyle+}_{o}|\geq
k,(d^{\scriptscriptstyle-}_{o},d^{\scriptscriptstyle+}_{o})\in A\right).$
(4.3)

Define

$\mu_{k}(A)=\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|,|\mathscr{C}^{\scriptscriptstyle+}_{o}|\geq
k,(d^{\scriptscriptstyle-}_{o},d^{\scriptscriptstyle+}_{o})\in A\right).$
(4.4)

Applying (4.3) for $A=\\{(l,m)\\}^{c}$, we get

$\lim_{n\to\infty}\mathbb{P}\left(\frac{1}{n}\left|\mathscr{C}_{\max}-v_{1}(l,m)\right|\leq\mu_{k}(A)+\frac{\varepsilon}{2}\right)=1.$
(4.5)

We argue by contradiction. Suppose that for some pair
$(l,m)\in\mathbb{N}^{2}$,

$\liminf_{n\to\infty}\mathbb{P}\left(\frac{1}{n}v_{1}(l,m)\leq\mu_{k}(\\{l,m\\})-\varepsilon\right)=\kappa>0.$
(4.6)

Then along the subsequence $(n_{j})_{j\geq 1}$, where the above liminf is
attained, with a non-zero probability the following holds:

$\frac{1}{n}|\mathscr{C}_{\max}|=\frac{1}{n}\left(|\mathscr{C}_{\max}|-v_{1}(l,m)\right)+\frac{1}{n}v_{1}(l,m)\leq\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty\right)-\frac{\varepsilon}{2},$
(4.7)

which contradicts Theorem 1.2. Thus, (1.12) holds.

For the next part, we just observe that

$\frac{|E(\mathscr{C}_{\max})|}{n}=\frac{1}{2n}\sum_{k,l}(k+l)v_{1}(k,l).$
(4.8)

Thus, for any natural number $N$.

$\frac{|E(\mathscr{C}_{\max})|}{n}=\frac{1}{2n}\sum_{k+l\leq
N}(k+l)v_{1}(k,l)+\frac{1}{2n}\sum_{k+l>N}(k+l)v_{1}(k,l).$ (4.9)

From (1.12) and the dominated convergence theorem, we conclude that

$\displaystyle\frac{1}{2n}\sum_{k+l\leq N}(k+l)v_{1}(k,l)$
$\displaystyle\overset{\scriptscriptstyle\mathbb{P}}{\longrightarrow}\frac{1}{2}\sum_{k+l\leq
N}(k+l)\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|=|\mathscr{C}^{\scriptscriptstyle+}_{o}|=\infty,D_{o}=(k,l)\right)$
$\displaystyle=\frac{1}{2}\mathbb{E}_{\mu}\left[\left(D^{\scriptscriptstyle-}_{o}+D^{\scriptscriptstyle+}_{o}\right)\mathbbm{1}_{\\{D^{\scriptscriptstyle-}_{o}+D^{\scriptscriptstyle+}_{o}<N\\}}\right].$
(4.10)

For the second term in (4.9), we bound $v_{1}(k,l)$ by the total number of
vertices with in- degree $k$ and out-degree $l$, which we denote by $n_{k,l}$,
to get

$\displaystyle\begin{split}\frac{1}{2n}\sum_{k+l>N}(k+l)v_{1}(k,l)&\leq\frac{1}{2}\sum_{k+l>N}(k+l)\frac{n_{k,l}}{n}\\\
&=\frac{1}{2}\mathbb{E}\left[\left(D^{\scriptscriptstyle-}_{o_{n}}+D^{\scriptscriptstyle+}_{o_{n}}\right)\mathbbm{1}_{\\{D^{\scriptscriptstyle-}_{o_{n}}+D^{\scriptscriptstyle+}_{o_{n}}>N\\}}\mid
G_{n}\right].\end{split}$ (4.11)

By uniform integrability of $D^{\scriptscriptstyle-}_{o_{n}}$ and
$D^{\scriptscriptstyle+}_{o_{n}}$,

$\lim_{N\to\infty}\limsup_{n\to\infty}\mathbb{E}\left[\left(D^{\scriptscriptstyle-}_{o_{n}}+D^{\scriptscriptstyle+}_{o_{n}}\right)\mathbbm{1}_{\\{D^{\scriptscriptstyle-}_{o_{n}}+D^{\scriptscriptstyle+}_{o_{n}}>N\\}}\right]=0.$
(4.12)

Thus, using the Markov inequality we can conclude that for each
$\varepsilon>0$, there exists a $N=N(\varepsilon)<\infty$ such that

$\mathbb{P}\left(\mathbb{E}\left[\left(D^{\scriptscriptstyle-}_{o_{n}}+D^{\scriptscriptstyle+}_{o_{n}}\right)\mathbbm{1}_{\\{D^{\scriptscriptstyle-}_{o_{n}}+D^{\scriptscriptstyle+}_{o_{n}}>N\\}}\mid
G_{n}\right]>\varepsilon\right)\to 0.$ (4.13)

This completes the proof for the second part of the theorem. ∎

###### Proof of Theorem 1.4.

When $\zeta=0$, there is nothing to prove, so we may again assume that
$\zeta>0$. The proof is a minor modification of that of Theorem 1.3. Let
$\mathscr{G}_{\star}$ be the space of all rooted digraphs. By forward-backward
local convergence in probability of $(G_{n})_{n\geq 1}$, for every
$\mathscr{H}_{\star}\subseteq\mathscr{G}_{\star},$

$\frac{1}{n}\sum_{v\in
V(G_{n})}\mathbbm{1}_{\left\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\in\mathscr{H}_{\star}\right\\}}\overset{\scriptscriptstyle\mathbb{P}}{\longrightarrow}\mu\left(B_{r}^{\scriptscriptstyle(G)}(o)\in\mathscr{H}_{\star}\right).$
(4.14)

Thus, (1.15) follows from (1.14). Therefore, we only need to show (1.14).
Define

$\displaystyle\begin{split}Z_{\geq
k,\mathscr{H}_{\star}}&=\frac{1}{n}\sum_{v\in
V(G_{n})}\mathbbm{1}_{\left\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq
k,B_{r}^{\scriptscriptstyle(G_{n})}(v)\in\mathscr{H}_{\star}\right\\}}\\\
&\overset{\scriptscriptstyle\mathbb{P}}{\longrightarrow}\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{o}|\geq
k,B_{r}^{\scriptscriptstyle(G)}(o)\in\mathscr{H}_{\star}\right).\end{split}$
(4.15)

Because of Theorem 1.2, we have that
$|\mathscr{C}_{\max}|/n\overset{\scriptscriptstyle\mathbb{P}}{\to}\zeta>0$.
Thus, on the high probability event $\left\\{|\mathscr{C}_{\max}|\geq
k\right\\}$,

$\frac{1}{n}\sum_{v\in\mathscr{C}_{\max}}\mathbbm{1}_{\left\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\in\mathscr{H}_{\star}\right\\}}\leq
Z_{\geq
k,\mathscr{H}_{\star}}\overset{\scriptscriptstyle\mathbb{P}}{\to}\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{o}|\geq
k,B_{r}^{\scriptscriptstyle(G)}(o)\in\mathscr{H}_{\star}\right).$ (4.16)

Define

$\mu_{k}(\mathscr{H}_{\star})=\mu\left(|\mathscr{C}^{\scriptscriptstyle-}_{o}|\geq
k,|\mathscr{C}^{\scriptscriptstyle+}_{o}|\geq
k,B_{r}^{\scriptscriptstyle(G)}(o)\in\mathscr{H}_{\star}\right).$ (4.17)

Then, by (4.16),

$\lim_{n\to\infty}\mathbb{P}\left(\frac{1}{n}\sum_{v\in\mathscr{C}_{\max}}\mathbbm{1}_{\left\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\in\mathscr{H}_{\star}\right\\}}\leq\mu_{k}\left(\mathscr{H}_{\star}\right)+\frac{\varepsilon}{2}\right)=1.$
(4.18)

Choosing $\mathscr{H}_{\star}=\\{H_{\star}\\}$, gives the upper bound. For,
$\mathscr{H}_{\star}=\\{H_{\star}\\}^{c}$ in (4.18),

$\lim_{n\to\infty}\mathbb{P}\left(\frac{1}{n}\left[|\mathscr{C}_{\max}|-\sum_{v\in\mathscr{C}_{\max}}\mathbbm{1}_{\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\cong
H_{\star}\\}}\right]\leq\mu_{k}(\mathscr{H}_{\star})+\frac{\varepsilon}{2}\right)=1.$
(4.19)

We again argue by contradiction. For this, we assume that

$\lim_{n\to\infty}\mathbb{P}\left(\frac{1}{n}\sum_{v\in\mathscr{C}_{\max}}\mathbbm{1}_{\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\cong
H_{\star}\\}}\leq\mu_{k}(\\{H_{\star}\\})-\frac{\varepsilon}{2}\right)=\kappa>0.$
(4.20)

Then, with asymptotic probability $\kappa$,

$\displaystyle\frac{|\mathscr{C}_{\max}|}{n}$
$\displaystyle=\frac{1}{n}\left[|\mathscr{C}_{\max}|-\sum_{v\in\mathscr{C}_{\max}}\mathbbm{1}_{\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\cong
H_{\star}\\}}\right]+\frac{1}{n}\sum_{v\in\mathscr{C}_{\max}}\mathbbm{1}_{\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\cong
H_{\star}\\}}$ $\displaystyle\leq\zeta_{\geq
k}-\varepsilon/2\leq\zeta-\varepsilon/2.$ (4.21)

This contradicts Theorem 1.2. Thus, (4.20) cannot hold. This completes the
proof. ∎

##  5\. Number of strong components: Proof of Theorems 1.5 & 1.6

In this section, we prove results concerning the number of strongly connected
components of random digraph sequences having a local limit.

###  5.1. Number of strong components is ‘almost’ local: Proof of Theorem 1.5

In this section, we prove Theorem 1.5. We prove a lower bound that holds more
generally, and an upper bound that holds under the assumptions stated in
Theorem 1.5.

We first use that

$\displaystyle K_{n}=\sum_{v\in V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}.$ (5.1)

Indeed, if one sums the right-hand side for the vertices as partitioned by the
strongly connected components, one obtains

$\displaystyle\sum_{v\in V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}=\sum_{1\leq
i\leq
K_{n}}\sum_{v\in\mathscr{C}_{\scriptscriptstyle(i)}}\frac{1}{|\mathscr{C}_{\scriptscriptstyle(i)}|}=\sum_{1\leq
i\leq K_{n}}1=K_{n}.$ (5.2)

Equation (5.1) is the starting point of our analysis. However, we emphasize
that, unlike in the undirected case, $h(G,o)=1/|\mathscr{C}_{v}|$ is not a
bounded and continuous function in the forward-backward sense.

For the lower bound, we fix $k$ and bound

$K_{n}\geq\sum_{v\in
V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|<k\\}\cup\\{|\mathscr{C}^{\scriptscriptstyle+}_{v}|<k\\}}.$
(5.3)

For each $k<\infty$, the function

$h(G,o)=\frac{1}{|\mathscr{C}_{o}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{o}|<k\\}\cup\\{|\mathscr{C}^{\scriptscriptstyle+}_{o}|<k\\}}$

is a bounded continuous function. Indeed, any $u\in\mathscr{C}_{o}$ is on a
directed cycle starting and ending at $o$. When
$|\mathscr{C}^{\scriptscriptstyle-}_{o}|<k$ or
$|\mathscr{C}^{\scriptscriptstyle+}_{o}|<k$, there cannot be any cycle longer
than $k-1$, so that we can determine $h(G,o)$ on the basis of
$B_{k}^{\scriptscriptstyle(G)}(o)$ (recall Definition 1.4).

We conclude that

$\frac{1}{n}\sum_{v\in
V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|<k\\}\cup\\{|\mathscr{C}^{\scriptscriptstyle+}_{v}|<k\\}}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mathbb{E}_{\mu}\Bigg{[}\frac{1}{|\mathscr{C}_{o}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{o}|<k\\}\cup\\{|\mathscr{C}^{\scriptscriptstyle+}_{o}|<k\\}}\Bigg{]}.$
(5.4)

Since, for $k\rightarrow\infty$,

$\mathbb{E}_{\mu}\Bigg{[}\frac{1}{|\mathscr{C}_{o}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{o}|<k\\}\cup\\{|\mathscr{C}^{\scriptscriptstyle+}_{o}|<k\\}}\Bigg{]}\rightarrow\mathbb{E}_{\mu}\Bigg{[}\frac{1}{|\mathscr{C}_{o}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{o}|<\infty\\}\cup\\{|\mathscr{C}^{\scriptscriptstyle+}_{o}|<\infty\\}}\Bigg{]},$
(5.5)

we obtain that

$\frac{K_{n}}{n}\geq\mathbb{E}_{\mu}\Bigg{[}\frac{1}{|\mathscr{C}_{o}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{o}|<\infty\\}\cup\\{|\mathscr{C}^{\scriptscriptstyle+}_{o}|<\infty\\}}\Bigg{]}+o_{\scriptscriptstyle\mathbb{P}}(1),$
(5.6)

as required.

For the upper bound, we again fix $k$ and now write

$K_{n}=\sum_{v\in
V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|<k\\}\cup\\{|\mathscr{C}^{\scriptscriptstyle+}_{v}|<k\\}}+\sum_{v\in
V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k\\}\cap\\{|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq k\\}}.$ (5.7)

It suffices to prove that the second term in (5.7) is
$o_{k,\scriptscriptstyle\mathbb{P}}(n),$ which is what we will do now. For
this, we make the further split

$\displaystyle\sum_{v\in
V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k\\}\cap\\{|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq k\\}}$ (5.8)
$\displaystyle\qquad=\sum_{v\in
V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}[\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k\\}\cap\\{|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq
k\\}}-\mathbbm{1}_{\\{v\in\mathscr{C}_{\max}\\}}]+\sum_{v\in
V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}\mathbbm{1}_{\\{v\in\mathscr{C}_{\max}\\}}.$

We note that

$\frac{1}{n}\sum_{v\in
V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}\mathbbm{1}_{\\{v\in\mathscr{C}_{\max}\\}}=\frac{1}{n}\sum_{v\in\mathscr{C}_{\max}}\frac{1}{|\mathscr{C}_{\max}|}=\frac{1}{n}\rightarrow
0.$ (5.9)

Further, since
$|\mathscr{C}_{\max}|\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\infty$
by assumption, we have that $|\mathscr{C}_{\max}|\geq k$ whp, so that whp also

$\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k\\}\cap\\{|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq
k\\}}-\mathbbm{1}_{\\{v\in\mathscr{C}_{\max}\\}}\geq 0.$

As a result, using that $|\mathscr{C}_{v}|\geq 1,$ on the high probability
event that $|\mathscr{C}_{\max}|\geq k$,

$\displaystyle\frac{1}{n}\sum_{v\in
V(G_{n})}\frac{1}{|\mathscr{C}_{v}|}[\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k\\}\cap\\{|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq
k\\}}-\mathbbm{1}_{\\{v\in\mathscr{C}_{\max}\\}}]$ (5.10)
$\displaystyle\qquad\leq\frac{1}{n}\sum_{v\in
V(G_{n})}[\mathbbm{1}_{\\{|\mathscr{C}^{\scriptscriptstyle-}_{v}|\geq
k\\}\cap\\{|\mathscr{C}^{\scriptscriptstyle+}_{v}|\geq
k\\}}-\mathbbm{1}_{\\{v\in\mathscr{C}_{\max}\\}}]$
$\displaystyle\qquad=\frac{1}{n}\big{[}Z_{\geq k}-|\mathscr{C}_{\max}|].$

By Theorem 1.1 and forward-backward local convergence in probability of
$G_{n}$,

$\frac{1}{n}\big{[}Z_{\geq
k}-|\mathscr{C}_{\max}|]\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta_{\geq
k}-\zeta,$ (5.11)

which vanishes as $k\rightarrow\infty$. We conclude that also the left-hand
side of (5.10) is $o_{k,\scriptscriptstyle\mathbb{P}}(1)$, which, together
with (5.9), completes the proof. ∎

###  5.2. Isolated vertices in digraphs and locally tree-like digraphs

In this section, we investigate strongly isolated vertices, which are of
interest because each such vertex contributes a unique strongly connected
component. In locally tree-like graphs these are the major contributors when
counting the number of strongly connected components, as we will show in this
section.

######  Definition 5.1 (Strongly isolated vertices).

A vertex $v\in V(G)$ is said to be _strongly isolated_ if
$\mathscr{C}_{v}=\\{v\\}.$ We denote the set of strongly isolated vertices of
$G$ by $V_{1}(G)$, and denote $\alpha_{1}(n)=|V_{1}(G)|$.

We next study $\alpha_{1}(n):$

######  Lemma 5.1 (Upper bound for the proportion of strongly isolated
vertices).

Under the assumptions of Theorem 1.2, and for all $\varepsilon>0$,

$\lim_{n\to\infty}\mathbb{P}\left(\alpha_{1}(n)\leq
1-\zeta+\varepsilon\right)=1,$ (5.12)

where
$\zeta=\mathbb{P}(|\mathscr{C}_{o}^{\scriptscriptstyle-}|=|\mathscr{C}_{o}^{\scriptscriptstyle+}|=\infty)$.

###### Proof.

The number of isolated vertices cannot exceed the number of vertices outside
the giant component, since the vertices in the giant cannot be isolated. This
gives $\alpha_{1}(n)\leq n-|\mathscr{C}_{\max}|$. Dividing by $n$ on both
sides gives the required result. ∎

######  Definition 5.2 (In- and out-neighbourhood of a fixed finite radius).

Let $G$ be a digraph and $v\in V(G)$, then we let
$B_{k}^{\scriptscriptstyle-}(v)$ and $B_{k}^{\scriptscriptstyle+}(v)$ to be
the subgraphs induced by the vertices in the $k$ radius in- and out-
neighbourhood of $v$, respectively, defined as

$\displaystyle B_{k}^{\scriptscriptstyle-}(v)=G\left[\left\\{u\in V(G)\text{
s.t. }d_{G}(u,v)<k\right\\}\right],$ (5.13) $\displaystyle
B_{k}^{\scriptscriptstyle+}(v)=G\left[\left\\{u\in V(G)\text{ s.t.
}d_{G}(v,u)<k\right\\}\right].$ (5.14)

Similarly, we let $\partial B_{k}^{\scriptscriptstyle-}(v)$ and $\partial
B_{k}^{\scriptscriptstyle+}(v)$ to be the boundary of $k$ radius in- and out-
neighbourhoods of $v$, respectively, defined as

$\displaystyle\partial B_{k}^{\scriptscriptstyle-}(v)=\left\\{u\in V(G)\text{
s.t. }d_{G}(u,v)=k\right\\},$ (5.15) $\displaystyle\partial
B_{k}^{\scriptscriptstyle+}(v)=\left\\{u\in V(G)\text{ s.t.
}d_{G}(v,u)=k\right\\}.$ (5.16)

$\blacktriangleleft$

We next turn to locally tree-like digraphs:

######  Lemma 5.2 (Proportion of strongly isolated vertices in locally tree-
like digraphs).

Suppose that $G_{n}$ is a sequence of random digraphs such that $G_{n}$
converges forward-backward locally in probability to $(G,o)\sim\mu$, which is
almost surely a random directed tree. Then, under the assumption of Theorem
1.2,

$\alpha_{1}(n)\overset{\scriptscriptstyle\mathbb{P}}{\longrightarrow}1-\zeta.$
(5.17)

###### Proof of Lemma 5.2.

Fix a finite $k\in\mathbb{N}$. Then

$\displaystyle\begin{split}\alpha_{1}(n)&=\frac{1}{n}\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{|\mathscr{C}_{v}|=1\\}}\\\ &\geq\frac{1}{n}\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{|B_{k}^{\scriptscriptstyle-}(v)\cap
B_{k}^{\scriptscriptstyle+}(v)|=1,|\partial
B_{k}^{\scriptscriptstyle-}(v)||\partial
B_{k}^{\scriptscriptstyle+}(v)|=0\\}}\\\
&\overset{\scriptscriptstyle\mathbb{P}}{\longrightarrow}\mu(|B_{k}^{\scriptscriptstyle-}(o)\cap
B_{k}^{\scriptscriptstyle+}(o)|=1,|\partial
B_{k}^{\scriptscriptstyle-}(o)||\partial
B_{k}^{\scriptscriptstyle+}(o)|=0).\end{split}$ (5.18)

If the local limit is a directed tree, then
$\mu(|B_{k}^{\scriptscriptstyle-}(o)\cap
B_{k}^{\scriptscriptstyle+}(o)|=1)=1$, since otherwise there will be a
directed cycle in the local limit graph. Thus, we can write

$\displaystyle\mu(|B_{k}^{\scriptscriptstyle-}(o)\cap
B_{k}^{\scriptscriptstyle+}(o)|=1,|\partial
B_{k}^{\scriptscriptstyle-}(o)||\partial B_{k}^{\scriptscriptstyle+}(o)|=0)$
(5.19) $\displaystyle\qquad=\mu(|\partial
B_{k}^{\scriptscriptstyle-}(o)||\partial B_{k}^{\scriptscriptstyle+}(o)|=0).$

Also, we know that, as $k\to\infty$,

$\mu(|\partial B_{k}^{\scriptscriptstyle-}(o)||\partial
B_{k}^{\scriptscriptstyle+}(o)|=0)\to\mu\left(\left\\{|\mathscr{C}_{o}^{\scriptscriptstyle-}|<\infty\right\\}\cup\left\\{|\mathscr{C}_{o}^{\scriptscriptstyle+}|<\infty\right\\}\right)=1-\zeta.$
(5.20)

This completes the proof. ∎

###### Proof of Theorem 1.6.

By the definition of $\alpha_{1}(n)$ in Definition 5.1,

$\frac{K_{n}}{n}\geq\alpha_{1}(n),$ (5.21)

Also,

$K_{n}\leq 1+n-|\mathscr{C}_{\max}|.$ (5.22)

From (5.21) and (5.22),

$\alpha_{1}(n)\leq\frac{K_{n}}{n}\leq
1-\frac{|\mathscr{C}_{\max}|}{n}+\frac{1}{n}.$ (5.23)

Lemma 5.2 and Theorem 1.2 then complete the proof. ∎

##  6\. Discussion

###  6.1. Discussion results and literature

The main results in this paper concern the proportion of vertices in the LSCC
and the number of connected components. We prove that these properties are
‘almost local’. Why are these connectivity properties important? Apart from
indicating the connectivity of the graph, they are also used in the
comparisons of centrality measures (see, e.g., [14]). This investigates how
much a graph breaks down in terms of its connectivity, when we remove the most
central nodes. We next list some open problems of our work.

In Theorem 1.5, we prove that (1.9) is a necessary and sufficient condition
for
$|\mathscr{C}_{\max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta=\mu(|\mathscr{C}^{\scriptscriptstyle+}_{o}|=|\mathscr{C}^{\scriptscriptstyle-}_{o}|=\infty)$
to hold. Of course,
$\zeta\geq\zeta^{\prime}\equiv\mu(|\mathscr{C}_{o}|=\infty)$. What is a
necessary and sufficient condition for
$|\mathscr{C}_{\max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta^{\prime}$
to hold? These conditions should really be different, since, for example, for
locally tree-like digraphs, $\zeta^{\prime}=0,$ while
$|\mathscr{C}_{\max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta=\mu(|\mathscr{C}^{\scriptscriptstyle+}_{o}|=|\mathscr{C}^{\scriptscriptstyle-}_{o}|=\infty)>0$
can hold.

Currently, to describe the number of strongly connected components in Theorem
1.5, we rely on the necessary and sufficient condition (1.9) for the
proportion of vertices in the giant being equal to
$\zeta=\mu(|\mathscr{C}^{\scriptscriptstyle+}_{o}|=|\mathscr{C}^{\scriptscriptstyle-}_{o}|=\infty)$.
What is the necessary and sufficient condition for the convergence
$K_{n}/n\overset{\scriptscriptstyle\mathbb{P}}{\to}\alpha$ to hold, and is it
possible that $\alpha$ takes a different form than that on the right-hand side
of (1.16)?

###  6.2. Large weak components

In this section, we discuss weak giants. The definition of a strong component
in a digraph is well accepted. In contrast, the notion of a weak component has
been used differently in the literature, as we discuss next.

##### In- and out-components.

One could consider weak components to be in-and the out-components. For
example, in [4], the authors study the largest in- and out-component sizes for
the directed configuration model. We define the sizes of the largest in- and
out-components $\mathscr{I}_{\max}$ and $\mathscr{O}_{\max}$ to be

$\displaystyle\mathscr{I}_{\max}=\max_{v\in
V(G_{n})}|\mathscr{C}^{\scriptscriptstyle-}_{v}|\qquad\text{and}\qquad\mathscr{O}_{\max}=\max_{v\in
V(G_{n})}|\mathscr{C}^{\scriptscriptstyle+}_{v}|.$ (6.1)

The strong giant having linear size implies that its in- and out-components
also have linear size, but the converse is not necessarily true. We visualize
this in Figure 1.

$\mathscr{C}_{\scriptscriptstyle(1)}$$\mathscr{C}_{\scriptscriptstyle(2)}$…$\mathscr{C}_{\scriptscriptstyle(k-1)}$$\mathscr{C}_{\scriptscriptstyle(k)}$
Figure 1. A linear-sized giant in- or out-component can exist despite the fact
that there is no linear-sized strong giant.

The big question is whether the maximal in- and out-components are ‘almost’
local or not, and if so, under what condition. In particular, a natural
question is to find a condition that guarantees that the proportion of
vertices in $\mathscr{I}_{\max}$ is asymptotically equal to the proportion of
vertices in the out-component of $\mathscr{C}_{\max}$. See Figure 2, where
LSCC stands for the largest strongly connected component. This means that the
condition for the existence of weak giants should be weaker than the
conditions given in Theorem 1.2.

LSCCOutIn Figure 2. The ‘bow-tie’ figure used to describe the connectivity
structure of large directed networks.

For the in- and out-components, we believe it to be possible that
$|\mathscr{C}_{\max}^{+}|/n\overset{\scriptscriptstyle\mathbb{P}}{\to}\alpha\leq\mu(|\mathscr{C}_{o}^{-}|=\infty)$
and vice-versa for the in-component. We state the following open problem:

######  Open Problem 6.1.

Find the necessary and sufficient conditions for

$\displaystyle\frac{|\mathscr{C}_{\max}^{+}|}{n}\overset{\scriptscriptstyle\mathbb{P}}{\to}\alpha^{+}\qquad\text{and}\qquad\frac{|\mathscr{C}_{\max}^{-}|}{n}\overset{\scriptscriptstyle\mathbb{P}}{\to}\alpha^{-}$
(6.2)

to hold.

When
$|\mathscr{C}_{\max}^{+}|/n\overset{\scriptscriptstyle\mathbb{P}}{\to}\alpha^{+}$,
then one can easily deduce that
$\alpha^{+}\leq\mu(|\mathscr{C}_{o}^{-}|=\infty)$. It is not clear when
$\alpha^{+}=\mu(|\mathscr{C}_{o}^{-}|=\infty)$ holds. One difficultly to prove
such a result is that, unlike the strongly connected components, the in- and
out-components do not _partition_ the vertex set.

##### Ignoring the directions of edges.

One can also consider weak components to consist of the set of vertices that
can be reached by recursively following all edges regardless of their
orientations [5, 13]. This corresponds to the connected components in the
underlying undirected graph, i.e., the graph obtained after removing the edge
directions. These types of components find applications in real-world
problems, including epidemiology, data mining, communication networks, world
wide web structure, etc. In this case, the results in [8] can be used to give
a necessary and sufficient condition for the proportion of vertices in the
giant to be the survival probability of the local limit.

##### Weak components as a relation.

The 1972 paper by Graham, Knuth, and Motzkin [12, 7] introduced a rather
different notion of weak components. Formally, it can be defined by the
following $4$ symmetric relations on the vertex set of a digraph:

  1. (1)

For any two vertices $u$ and $v$ in $V(G)$, $u\iff v$ if both vertices are in
the same strongly connected component, i.e.,
$\max\\{d_{G}(u,v),d_{G}(v,u)\\}<\infty$. In other words, there exists a path
from $v$ to $u$ and vice versa.

  2. (2)

For any two vertices $u$ and $v$ in $V(G)$, $u\parallel v$ if
$\min\\{d_{G}(u,v),d_{G}(v,u)\\}=\infty$, i.e., there is no path from $v$ to
$u$ and from $u$ to $v$.

  3. (3)

For any two vertices $u$ and $v$ in $V(G)$, $u\approx v$ if either $u\iff v$
or $u\parallel v$.

  4. (4)

We define $R$ to be the transitive closure of $\approx$. This means that if
there is a chain $(u=v_{0},v_{1},\ldots,v_{k}=v)$ such that $u\approx
v_{1}\approx\cdots v_{k-1}\approx v$, then $uRv$.

The relation $R$ is an equivalence relation and partitions the vertex set into
the weak components. This concept of weak component is not a local quantity as
a small perturbation in the graph can easily dramatically change the
components in the graph. In particular, the addition of _one_ isolated vertex
can change the definition of all these weak components. This suggests that, in
terms of local convergence, this notion is too sensitive to local changes.
Yet, Pacault [15] gives an algorithm for computing weak components.

## References

  * [1] David Aldous and J. Michael Steele, _The objective method: probabilistic combinatorial optimization and local weak convergence_ , Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 1–72. MR 2023650
  * [2] Itai Benjamini and Oded Schramm, _Recurrence of distributional limits of finite planar graphs_ , Electron. J. Probab. 6 (2001), no. 23, 13. MR 1873300
  * [3] Xing Shi Cai and Guillem Perarnau, _The diameter of the directed configuration model_ , Ann. Inst. Henri Poincaré Probab. Stat. 59 (2023), no. 1, 244–270. MR 4533728
  * [4] Colin Cooper and Alan Frieze, _The size of the largest strongly connected component of a random digraph with a given degree sequence_ , Combin. Probab. Comput. 13 (2004), no. 3, 319–337. MR 2056402
  * [5] Matthew Coulson and Guillem Perarnau, _Weak components of the directed configuration model_ , Extended Abstracts EuroComb 2021: European Conference on Combinatorics, Graph Theory and Applications, Springer, 2021, pp. 682–687.
  * [6] Alessandro Garavaglia, Remco van der Hofstad, and Nelly Litvak, _Local weak convergence for PageRank_ , Ann. Appl. Probab. 30 (2020), no. 1, 40–79. MR 4068306
  * [7] Ronald L Graham, Donald E Knuth, and TS Motzkin, _Complements and transitive closures._ , Discret. Math. 2 (1972), no. 1, 17–29.
  * [8] Remco van der Hofstad, _The giant in random graphs is almost local_ , arXiv:2103.11733 [math.PR], 2021.
  * [9] Remco van der Hofstad, _Random graphs and complex networks. Vol. 2_ , Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2024. MR 3617364
  * [10] Pim van der Hoorn and M. Olvera-Cravioto, _Typical distances in the directed configuration model_ , Ann. Appl. Probab. 28 (2018), no. 3, 1739–1792. MR 3809476
  * [11] Femke van Ieperen and Ivan Kryven, _Percolation in simple directed random graphs with a given degree distribution_ , Probability in the Engineering and Informational Sciences (2023), 1–22.
  * [12] Donald E. Knuth, _The art of computer programming_ , Sorting and searching 3 (1999), no. 426-458, 4.
  * [13] Ivan Kryven, _Emergence of the giant weak component in directed random graphs with arbitrary degree distributions_ , Physical Review E 94 (2016), no. 1, 012315.
  * [14] Decebal Constantin Mocanu, Georgios Exarchakos, and Antonio Liotta, _Decentralized dynamic understanding of hidden relations in complex networks_ , Scientific Reports 8 (2018), no. 1, 1571.
  * [15] Jean Francois Pacault, _Computing the weak components of a directed graph_ , SIAM Journal on Computing 3 (1974), no. 1, 56–61.


# One Venue, Two Conferences: The Separation of Chinese and American Citation
Networks

Bingchen Zhao∗
University of Edinburgh
<EMAIL_ADDRESS>Yuling Gu∗
Allen Institute for Artificial Intelligence
<EMAIL_ADDRESS>Jessica Zosa Forde
Brown University
<EMAIL_ADDRESS>Naomi Saphra
New York University
<EMAIL_ADDRESS>
###### Abstract

At NeurIPS, American and Chinese institutions cite papers from each other’s
regions substantially less than they cite endogamously. We build a citation
graph to quantify this divide, compare it to European connectivity, and
discuss the causes and consequences of the separation.

##  1 Introduction

In recent years, the machine learning research landscape has been reshaped by
the growth of Chinese AI research. China now consistently stands as the
second-largest country in terms of total publications at NeurIPS, after the
United States. In 2020, papers from Chinese institutions represented 13.6% of
all NeurIPS publications [6]. The following year, this share increased to
17.5%, representing a relative increase of 28.7% [13].111These numbers can be
regarded as an underestimate of total share, as American multinational
companies have been categorized as American regardless of the office location
of the authors.

In spite of China’s position as a national AI powerhouse, collaborations
between Chinese and American institutions are rarer than those between, say,
American and Western European institutions [11]. Anecdotally, they also form
distinct social groups at machine learning conferences: Chinese researchers
often converse and take meals in separate groups from European and North
American researchers. This divide goes beyond only social interactions; one
prominent non-Chinese professor in an applied area of machine learning drew
attention on Twitter when they advised students to avoid talks by Chinese
authors, arguing that the presentations would be difficult to understand or of
poor quality.222Out of a respect for privacy, we have kept this anecdote
anonymous. While it is true that many non-native anglophones find publicly
speaking in English to be a challenge, avoiding talks by Chinese researchers
may limit a conference attendee’s exposure to new topics and ideas.

In this work, we measure this divide between researchers in China and
researchers in the United States. Using NeurIPS citation data, we analyze the
impact of work from US-based and China-based institutions. We find that
Chinese institutions under-cite work from the US and Europe, and both American
and European institutions under-cite work from China.

##  2 Citation networks

How severe is this segregation between American and Chinese research
communities? In order to measure the effect quantitatively, we collate
citation data with institutions labeled by region. We consider the divisions
between American, European, and Chinese researchers. We find that European and
American institutions are more closely linked through citations, and Chinese
research is less linked to American and European research.

###  2.1 Methods

We compiled a citation graph by joining the citation data of the NeurIPS
papers available from
SemanticScholar333https://www.semanticscholar.org/product/api with
institutional information about authors from
AMiner444https://www.aminer.cn/oag-2-1. We first collected all paper titles
from NeurIPS 2012 to 2021 from the NeurIPS website. We map the paper titles to
their Semantic Scholar paper IDs using the Semantic Scholar Academic Graph
(S2AG) API [15]. We manually searched for the unmatched papers, finding all
but one in the Semantic Scholar database. For each of these papers, we then
used the S2AG API to identify the authors, as well as authors of papers in its
references.

We then used AMiner to identify institutional information for each author. The
9460 NeurIPS papers have 135,941 authors in total, of which we found
institutions for 83,515 authors (61%). There are 4038 papers that have no
authors on AMiner, so they are removed from the data. We then automatically
marked institutes that included the name of a country, along with common
cities and regions in China. We supplemented these automatic annotations with
existing 555https://github.com/nd7141/icml2020/blob/master/university2.csv
regional matchings and manually added 364 additional rules for regional
matching. Finally, we removed major multinational corporate labs (e.g.,
Google, Meta, Microsoft, Tencent, Alibaba, or Huawei), as they typically do
not include information about the local office of the authors. Out of the
remaining 5422 papers, we removed papers that weren’t in one of the specified
regions (China, US, Europe), or that included collaborators in multiple
regions, leaving 1792 papers remaining. We then computed the average number
and proportion of citations between papers from each region (Figure 1).

###  2.2 Results

Based on these numbers, we see the extent to which American and Chinese papers
fail to cite each other. While American papers make up 60% of the dataset,
they make up only 34% of Chinese citations. American citations of Chinese
papers show a more dramatic effect: while Chinese papers make up 34% of the
dataset, they are only 9% of American citations. The effect is clear when we
compare these numbers to American citations of European papers: even though
our dataset of NeurIPS papers has six times as many Chinese papers as European
papers, American institutions cite Chinese papers less often than European
papers. (Note that the cited non-NeurIPS papers can be older, and thus are
less likely to be Chinese than the citing papers.)

We observe that each region tends to self-cite more frequently than they are
otherwise cited: 21% for China, 41% for the USA, and 14% for Europe. However,
the separation between American and Chinese research communities is more
pronounced than one might expect from typical regional preference. The
American and European research communities share similar citation behavior,
with few citations to Chinese papers, whereas Chinese institutions cite
American and European papers less often than either other region does.

Figure 1: Papers from Europe and the US cite one another more often than they
cite papers from China, and papers from China are least likely to cite
institutions in Europe and the US.

###  2.3 Limitations

The strength of our claims is subject to the influence of a number of factors
we have not accounted for in this work.

First, while we consider the work from any university situated in the United
States to be American, US-based labs may still have close links to China,
which may lead us to underestimate the division between AI research in the US
and China. For example, there exist labs in the US that are made up largely or
entirely of Chinese international students. Similarly, Chinese international
students who return to their home country may bring international connections
to their alma mater and other institutions. We have not measured the degree to
which such graduates change their citation patterns to focus on domestic
papers, or whether they continue to widely cite American work. Additionally,
our filter of multinational corporate labs may be incomplete. If these
industry authors include companies with offices in both America and China,
they may affect the reliability of our conclusions.

There is another limitation that affects the confidence of our conclusions:
the number of papers that have been excluded on the basis of authors not
appearing in AMiner, a Chinese company. This is likely to result in there
being more Chinese papers in the dataset than if we had full information about
every paper. Overall, we discarded 43% of papers due to a lack of author
information, and this excluded set is likely to be a biased sample.

##  3 Consequences

While American and Chinese researchers publish in the same venues, they
represent two parallel communities, each producing work with limited impact on
the other. To some degree this divide can be attributed to an interest in
different topics, as cultural norms inform research priorities. For example,
multi-object tracking is an active area of research in China, with large scale
benchmarks such as Wang et al. [16], which provides annotations of individual
humans in each video. In North America, however, criticisms regarding of the
misuse of biometric data [1] have led researchers to avoid related tasks and
datasets. Similarly, the US tends to be heavily represented at fairness
conferences such as FACCT, while representation from China remains limited
[2].

However, even abstract topics or architectures that are popular in China may
not catch on in other regions. PCANet [3], an image classification
architecture from a Singaporean research lab, has 1200 citations which are
largely from Chinese or East Asian institutions. Deep Forests [20], which were
developed at Nanjing University, garnered over 600 citations that are mostly
Chinese.

It is not only topics of research that are limited by a lack of exchange
between regions. In recent years, the North American and European AI community
has begun to engage in conversations and publishing research on the ethical
considerations of AI. In accordance with these considerations, AI conferences
have adopted systems for reviewers to flag ethical concerns and ask authors to
write ethics statements or fill out checklists [1, 10]. Engagement with
researchers from China on these topics, however, remains limited. An example
of this disconnect is the Provisional Draft of the NeurIPS Code of Ethics [1].
At the time of initial publication, the authors’ affiliations were with US
universities, US-multinationals, and a university in Australia. None of the
authors were based in Asia. This absence is despite the fact that observers
have noted many similarities in ethics statements from Chinese based AI
institutions [12, 9].

Yet despite these similarities in ethics statements from US and Chinese
researchers, specific disagreements in research practice still exist. For
example, Duke University stopped providing the Duke-MTMC dataset [8] for
studying object tracking across multiple cameras, because the researchers did
not obtain consent from the students they collected images from [14]. However,
similar datasets like Market-1501 [18] from Tsinghua University are still
being actively used [5, 4]. Furthermore, researchers in China have continued
to use the Duke dataset even after its removal [17, 7, 19]. We can’t know
whether American researchers would have persuaded the authors with their
arguments about the ethical hazards of such datasets, because they failed to
engage the Chinese authors in these conversations.

The separation between these two communities has real impact on the individual
researchers, the machine learning community as a whole, and potentially the
societies affected by AI research. It is long past time that the AI community
had a conversation about how to overcome this barrier.

## References

  * [1] S. Bengio, A. Beygelzimer, K. Crawford, J. Fromer, I. Gabriel, A. Levendowski, , I. D. Raji, and M. Ranzato.  Provisional draft of the neurips code of ethics, 2022.
  * [2] D. Card.  Report from facct 2022, Jul 2022.
  * [3] T.-H. Chan, K. Jia, S. Gao, J. Lu, Z. Zeng, and Y. Ma.  Pcanet: A simple deep learning baseline for image classification?  IEEE Transactions on Image Processing, 24:5017–5032, 2015.
  * [4] D. Fu, D. Chen, H. Yang, J. Bao, L. Yuan, L. Zhang, H. Li, F. Wen, and D. Chen.  Large-scale pre-training for person re-identification with noisy labels.  In The IEEE / CVF Computer Vision and Pattern Recognition Conference (CVPR), 2022.
  * [5] S. He, H. Luo, P. Wang, F. Wang, H. Li, and W. Jiang.  Transreid: Transformer-based object re-identification.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 15013–15022, October 2021.
  * [6] S. Ivanov.  NeurIPS 2020. Comprehensive analysis of authors, organizations, and countries., Oct. 2020.
  * [7] M. Li, X. Zhu, and S. Gong.  Unsupervised tracklet person re-identification.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019\.
  * [8] E. Ristani, F. Solera, R. Zou, R. Cucchiara, and C. Tomasi.  Performance measures and a data set for multi-target, multi-camera tracking.  In European Conference on Computer Vision workshop on Benchmarking Multi-Target Tracking, 2016.
  * [9] H. Roberts, J. Cowls, J. Morley, M. Taddeo, V. Wang, and L. Floridi.  The chinese approach to artificial intelligence: an analysis of policy, ethics, and regulation.  AI & SOCIETY, 36(1):59–77, Mar 2021.
  * [10] A. Rogers, T. Baldwin, and K. Leins.  ‘just what do you think you’re doing, dave?’ a checklist for responsible data use in NLP.  In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 4821–4833, Punta Cana, Dominican Republic, Nov. 2021. Association for Computational Linguistics.
  * [11] M. Rungta, J. Singh, S. M. Mohammad, and D. Yang.  Geographic Citation Gaps in NLP Research, Oct. 2022.  arXiv:2210.14424 [cs].
  * [12] M. Sheehan.  Beijing’s approach to trustworthy ai isn’t so dissimilar from the world’s, Aug 2021.
  * [13] SYNCED.  NeurIPS 2021 Announces Its 6 Outstanding Paper Awards, 2 Datasets and Benchmarks Track Best Paper Awards, and the Test of Time Award | Synced, 2021.
  * [14] C. Tomasi.  Letter: Video analysis research at Duke, 2019.
  * [15] A. D. Wade.  The semantic scholar academic graph (s2ag).  In Companion Proceedings of the Web Conference 2022, WWW ’22, page 739, New York, NY, USA, 2022. Association for Computing Machinery.
  * [16] X. Wang, X. Zhang, Y. Zhu, Y. Guo, X. Yuan, L. Xiang, Z. Wang, G. Ding, D. Brady, Q. Dai, et al.  Panda: A gigapixel-level human-centric video dataset.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3268–3278, 2020.
  * [17] Y. Wu, Y. Lin, X. Dong, Y. Yan, W. Ouyang, and Y. Yang.  Exploit the unknown gradually: One-shot video-based person re-identification by stepwise learning.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [18] L. Zheng, L. Shen, L. Tian, S. Wang, J. Wang, and Q. Tian.  Scalable person re-identification: A benchmark.  In Computer Vision, IEEE International Conference on, 2015.
  * [19] Z. Zheng, L. Zheng, and Y. Yang.  Unlabeled samples generated by gan improve the person re-identification baseline in vitro.  In Proceedings of the IEEE International Conference on Computer Vision, 2017.
  * [20] Z.-H. Zhou and J. Feng.  Deep forest: Towards an alternative to deep neural networks.  ArXiv, abs/1702.08835, 2017.