Connectivity threshold for superpositions

of Bernoulli random graphs. II

Mindaugas Bloznelis, Dominykas Marma, Rimantas Vaicekauskas

Institute of Computer Science, Vilnius University

Didlaukio 47, LT-08303 Vilnius, Lithuania

###### Abstract

Let $G_{1},\dots,G_{m}$ be independent Bernoulli random subgraphs of the
complete graph ${\cal K}_{n}$ having variable sizes
$X_{1},\dots,X_{m}\in\\{0,1,2,\dots\\}$ and densities
$Q_{1},\dots,Q_{m}\in[0,1]$. Letting $n,m\to+\infty$ we establish the
connectivity threshold for the union $\cup_{i=1}^{m}G_{i}$ defined on the
vertex set of ${\cal K}_{n}$. Assuming that
$(X_{1},Q_{1}),(X_{2},Q_{2}),\dots,(X_{m},Q_{m})$ are independent identically
distributed bivariate random variables and $\ln
n-\frac{m}{n}{\bf{E}}\bigl{(}X_{1}(1-(1-Q_{1})^{|X_{1}-1|}\bigr{)}\to c$ we
show that ${\bf{P}}\\{\cup_{i=1}^{m}G_{i}$ is connected$\\}\to e^{-e^{c}}$.
The result extends to the case of non-identically distributed random variables
$(X_{1},Q_{1}),\dots,(X_{m},Q_{m})$ as well.

##  1 Introduction

Let $G_{1},\dots,G_{m}$ be independent Bernoulli random subgraphs of the
complete graph ${\cal K}_{n}$ having (random) sizes $X_{1},\dots,X_{m}$ and
densities $Q_{1},\dots,Q_{m}$. More precisely, given a sequence of independent
bivariate random vectors $(X_{1},Q_{1}),\dots,(X_{m},Q_{m})$, each
$G_{k}=({\cal V}_{k},{\cal E}_{k})$ is obtained by selecting a subset of
vertices ${\cal V}_{k}$ of ${\cal K}_{n}$ of size $|{\cal V}_{k}|=X_{k}$ and
retaining edges between selected vertices independently at random with
probability $Q_{k}$. In particular, each $G_{k}$ is a random graph on $X_{k}$
vertices, where every pair of vertices is linked by an edge independently at
random with probability $Q_{k}$. The union (superposition)
$G_{1}\cup\cdots\cup G_{m}$ represents a network of (possibly) overlapping
communities $G_{1},\dots,G_{m}$. It was called community affiliation graph by
Yang and Leskovec [10, 11] and has received considerable attention in the
literature. We note that Yang and Leskovec [10, 11] defined community
memberships (i.e. the sets ${\cal V}_{1},\dots,{\cal V}_{m}$) by design. In
this paper we study the community affiliation graph $G=\bigl{(}{\cal
V},\cup_{k=1}^{m}{\cal E}_{k}\bigr{)}$ in the case where the vertex sets
${\cal V}_{1}$, $\dots$, ${\cal V}_{m}$ of the communities $G_{1},\dots,G_{m}$
are drawn independently at random from the vertex set ${\cal V}=[n]$ of ${\cal
K}_{n}$. We mention that in the range of parameters $m=m(n)=\Theta(n)$ the
random graph $G$ admits a power law (asymptotic) degree distribution and non-
vanishing global clustering coefficient [3]. The phase transition in the size
of the largest component has been shown in [3]. Here we consider the
parametric range $m=\Theta(n\ln n)$ and address the property of full
connectivity.

The paper is organized as follows. In the remaining part of this section we
rigorously define the random graph model, present our results and give a brief
overview of related previous work. Proofs are postponed to the next section.

###  1.1 Random community affiliation graph

Given $n$ and $m$, let $(X_{n,1},Q_{n,1}),\dots,(X_{n,m},Q_{n,m})$ be
independent bivariate random variables taking values in
$\\{0,1,\dots,n\\}\times[0,1]$. For each $i\in[m]$, the $i$-th community
$G_{n,i}=({\cal V}_{n,i},{\cal E}_{n,i})$ is defined as follows. We firstly
sample $(X_{n,i},Q_{n,i})$. Then, given $(X_{n,i},Q_{n,i})$, we select the
vertex set ${\cal V}_{n,i}\subset[n]$ of size $|{\cal V}_{n,i}|=X_{n,i}$
uniformly at random and link every pair of elements of ${\cal V}_{n,i}$
independently at random with probability $Q_{n,i}$. We study the union graph
$G_{[n,m]}=({\cal V},{\cal E})$ with the vertex set ${\cal V}=[n]$ and the
edge set ${\cal E}=\cup_{i\in[m]}{\cal E}_{n,i}$. We say that $G_{[n,m]}$ is
defined by the sequence $(X_{n,1},Q_{n,1}),\dots,(X_{n,m},Q_{n,m})$. In
Theorems 1 and 2 below we assume that $m=m(n)\to+\infty$ as $n\to+\infty$ and
study a sequence of random graphs $G_{[n,m(n)]}$, $n=1,2,\dots$.

Our first result, Theorem 1 establishes the connectivity threshold for
$G_{[n,m]}$ in the case where the contributing random graphs
$G_{n,1},\dots,G_{n,m}$ are identically distributed. Let
$(X,Q),(X_{1},Q_{1}),(X_{2},Q_{2}),\dots$ be a sequence of independent and
identically distributed bivariate random variables. For each $n=1,2,\dots$ and
$i=1,\dots,m$ we put $X_{n,i}=\min\\{X_{i},n\\}$.

Introduce the function

$h(x,q)=1-(1-q)^{(x-1)_{+}},$

defined for $(x,q)\in[0;+\infty)\times[0;1]$. Here we denote
$(x)_{+}=\max\\{x,0\\}$ and assign value $1$ to the expression $0^{0}$. By
${\mathbb{I}}_{\cal A}$ we denote the indicator function of the condition
(event) ${\cal A}$. We denote

$\alpha={\bf{E}}(Q{\mathbb{I}}_{\\{X\geq
2\\}}),\qquad\varkappa={\bf{E}}(Xh(X,Q)),\qquad\lambda_{m,n}=\ln
n-\varkappa\frac{m}{n}.$

######  Theorem 1.

Let $c$ be a real number. Let $n\to+\infty$. Assume that $m=m(n)\to+\infty$.
Assume that ${\bf{E}}\left(Xh(X,Q)\ln(X+1)\right)<\infty$ and
${\bf{E}}(Q{\mathbb{I}}_{\\{X\geq 2\\}})>0$. Then

$\lim_{n\to+\infty}{\bf{P}}\\{G_{[n,m]}{\rm{\ is\ connected\
}}\\}=\begin{cases}1,\qquad\ {\rm{for}}\quad\lambda_{m,n}\to-\infty;\\\
e^{-e^{c}},\quad{\rm{for}}\quad\lambda_{m,n}\to c;\\\ 0,\qquad\
{\rm{for}}\quad\lambda_{m,n}\to+\infty.\end{cases}$ (1)

We observe that inequality $h(x,q)\geq q$, which holds for $x\geq 2$,
$q\in[0,1]$ implies

$\varkappa\geq{\bf{E}}(XQ{\mathbb{I}}_{\\{X\geq
2\\}})\geq{\bf{E}}(Q{\mathbb{I}}_{\\{X\geq 2\\}}).$

Hence, the condition ${\bf{E}}(Q{\mathbb{I}}_{\\{X\geq 2\\}})>0$ of Theorem 1
implies $\varkappa>0$. We mention that the integrability condition
${\bf{E}}\left(Xh(X,Q)\ln(X+1)\right)<\infty$ can not be relaxed, see [1].

Our next result, Theorem 2 addresses the case where the community sizes and
strengths $(X_{n,1},Q_{n,1}),\dots,(X_{n,m},Q_{n,m})$ are not necessarily
identically distributed. In particular, some or all of the members of the
sequence can be non random bivariate vectors. Before formulating the result we
introduce some notation. Let $i_{*}$ be a random number uniformly distributed
in $[m]$. We assume that $i_{*}$ is independent of the sequence
$\\{(X_{n,i},Q_{n,i})$, $i\in[m]\\}$. The bivariate random variable
$(X_{n,i_{*}},Q_{n,i_{*}})$ has probability distribution,

${\bf{P}}\bigr{\\{}X_{n,i_{*}}=x,Q_{n,i_{*}}\in[0,t]\bigl{\\}}=\frac{1}{m}\sum_{i\in[m]}{\bf{P}}\\{X_{n,i}=x,Q_{n,i}\in[0,t]\\}.$

We denote this probability distribution $P_{n,m}$. We will assume that
$P_{n,m}$ converges weakly to a probability distribution, say, $P$ on
$\\{0,1,2,\dots\\}\times[0,1]$. With a little abuse of notation we denote by
$(X,Q)$ a bivariate random variable with the distribution $P$. Denote

$\kappa_{n}={\bf{E}}\bigl{(}X_{n,i_{*}}h(X_{n,i_{*}},Q_{n,i_{*}})\bigr{)}=\frac{1}{m}\sum_{i\in[m]}{\bf{E}}\bigl{(}X_{n,i}h(X_{n,i},Q_{n,i})\bigr{)}$

and

$\lambda^{*}_{n,m}=\ln n-\frac{m}{n}\kappa_{n}.$

######  Theorem 2.

Let $m,n\to+\infty$. Assume that $(X_{n,i_{*}},Q_{n,i_{*}})$ converges in
distribution to some bivariate random random variable $(X,Q)$ such that
${\bf{E}}\bigl{(}Q{\mathbb{I}}_{\\{X\geq 2\\}}\bigr{)}>0$ and

${\bf{E}}\bigl{(}Xh(X,Q)\ln(1+X)\bigr{)}<\infty.$ (2)

Assume, in addition, that

${\bf{E}}\bigl{(}X_{n,i_{*}}h(X_{n,i_{*}},Q_{n,i_{*}})\ln(1+X_{n,i_{*}})\bigr{)}\to{\bf{E}}\bigl{(}Xh(X,Q)\ln(1+X)\bigr{)}.$
(3)

Then

$\lim_{n\to+\infty}{\bf{P}}\\{G_{[n,m]}{\rm{\ is\ connected\
}}\\}=\begin{cases}1,\qquad\ {\rm{for}}\quad\lambda^{*}_{m,n}\to-\infty;\\\
e^{-e^{c}},\quad{\rm{for}}\quad\lambda^{*}_{m,n}\to c;\\\ 0,\qquad\
{\rm{for}}\quad\lambda^{*}_{m,n}\to+\infty.\end{cases}$ (4)

###  1.2 Related previous work

After the seminal work of Erdős and Rényi [5] the connectivity thresholds for
various random graph models has attracted considerable attention in the
literature and still remains an area of active research, see [6], [8], [9] and
references therein.

An important property of the random graph model considered here is that in the
(sparse) parametric regime $m=\Theta(n)$ it admits an asymptotic power-law
degree distribution with a tunable power-law exponent and non-vanishing global
clustering coefficient, [3]. It doesn’t look surprising that the connectivity
thershold (1), (4) occurs at the range $m=\Theta(n\ln n)$ (recall that the
number of edges of the Erdős-Rényi graph at the connectivity threshold has the
same order of magnitude). What is perhaps more interesting is that the only
characteristic that defines the threshold is the mixed moment $\varkappa$
(respectively $\kappa_{n}$). For a comparison, the connectivity threshold of
another class of inhomogeneous random graphs, where edges between vertices,
say $u,v$, are inserted independently with probability, say $p_{n}(u,v)$, is
defined by $\operatorname*{ess\,inf}$ of the properly scaled limit of $p_{n}$
as $n\to+\infty$, see [4].

The present work complements the earlier study [1], where the zero - one law
for the connectivity property of the community affiliation graph has been
established under the minimal moment conditions on the probability
distribution of $(X,Q)$. Other previous papers concerned with the connectivity
threshold of the community affiliation graph have focused on the particular
case where the contributing subgraphs (communities) $G_{n,i}$ were complete
graphs (cliques). The connectivity threshold (1) has been reported in [7],
where it was assumed that $Q\equiv 1$ and $\exists M>0$ such that
${\bf{P}}\\{X\leq M\\}=1$. We note that the approach adopted in [7] is
different from ours. In the recent paper [2] the boundedness condition
${\bf{P}}\\{X\leq M\\}=1$ of [7] has been relaxed and the zero - one law for
the connectivity property has been shown assuming the second moment condition
${\bf{E}}X^{2}<\infty$. The present paper gives a definite answer to the
connectivity threshold problem for the community affiliation graph.

##  2 Proofs

In the proof we often use shorthand notation $G_{i}=G_{n,i}$ and ${\cal
V}_{i}={\cal V}_{n,i}$, ${\cal E}_{i}={\cal E}_{n,i}$, $1\leq i\leq m$.

###  2.1 Proof of Theorem 1

###### Proof of Theorem 1.

In the case where $\lambda_{m,n}\to\pm\infty$ the zero - one law of (1) is
shown in Proposition 1 of [1]. Here we show (1) in the case where
$\lambda_{m,n}\to c$.

We note that $G$ is disconnected whenever it has a (connected) component of
size $k$ for some $1\leq k\leq n/2$. Let $Y_{k}$ denote the number of
connected components of size $k$ and ${\cal A}_{i}=\left\\{\sum_{i\leq k\leq
n/2}Y_{k}\geq 1\right\\}$ denote the event that $G$ has a component of size
$k$ for some $k\geq i$. The probability that $G$ is disconnected equals

${\bf{P}}\\{{\cal A}_{1}\\}={\bf{P}}\\{{\cal A}_{2}\cup\\{Y_{1}\geq
1\\}\\}={\bf{P}}\\{Y_{1}\geq 1\\}+{\bf{P}}\\{{\cal
A}_{2}\setminus\\{Y_{1}=1\\}\\}.$

We show in Lemma 3 below that ${\bf{P}}\\{{\cal A}_{2}\\}=o(1)$. In Lemma 4 we
show that the random variable $Y_{1}$ ($=$ the number of isolated vertices)
converges in distribution to the Poisson distribution with mean value $e^{c}$
(distribution ${\cal P}(e^{c})$). In this way we obtain the asymptotic
relation

$\displaystyle 1-{\bf{P}}\\{G{\text{\ is connected}}\\}={\bf{P}}\\{{\cal
A}_{1}\\}$ $\displaystyle={\bf{P}}\\{Y_{1}\geq 1\\}+o(1)$
$\displaystyle=1-{\bf{P}}\\{Y_{1}=0\\}+o(1)$
$\displaystyle=1-e^{-e^{c}}+o(1).$

Hence ${\bf{P}}\\{G{\text{\ is connected}}\\}=e^{-e^{c}}+o(1)$. ∎

Before the formulation and proof of Lemmas 3 and 4 we collect some notation
and auxiliary results. Given integer $x\geq 2$ and real number $q\in[0,1]$,
let $V_{x}\subset{\cal V}$ be a random subset of size $|V_{x}|=x$. Let
$G_{x}=(V_{x},{\cal E}_{x})$ be Bernoulli random graph with the vertex set
$V_{x}$ and with edge probability $q$. Let $q_{k}(x,q)$ denote the probability
that none of the edges of $G_{x}$ connect subsets $[k]$ and $[n]\setminus[k]$,

$q_{k}(x,q)={\bf{P}}\bigl{\\{}\forall\\{u,v\\}\in{\cal
E}_{x}\quad{\text{either}}\quad u,v\in[k]\quad{\text{or}}\quad
u,v\in[n]\setminus[k]\bigr{\\}}.$

We put $q_{k}(x,q)=1$ for $x=0,1$. We will use the following result of [1].

######  Lemma 1.

For $1\leq k\leq n/2$, $2\leq x\leq n$ and $0\leq q\leq 1$ we have

$\displaystyle q_{k}(x,q)$ $\displaystyle\leq 1-2\frac{k(n-k)}{n(n-1)}q,$ (5)
$\displaystyle q_{k}(x,q)$ $\displaystyle\leq
1-\left(\frac{k}{n}x-R_{1}-R_{2}\right)h(x,q),$ (6)

where $R_{1}=\frac{k^{2}}{(n-k)^{2}}$ and
$R_{2}=R_{2}(k,x)=e^{-\frac{k}{n}x}-1+\frac{k}{n}x$.

Let ${\hat{q}}_{k}$ denote the probability that $G_{1}$ has no edge with one
endpoint in $[k]$ and another endpoint in $[n]\setminus[k]$. We denote for
short ${\tilde{X}}=\min\\{n,X\\}$ and ${\tilde{X}}_{i}=\min\\{X_{i},n\\}$. We
denote

${\tilde{\varkappa}}={\bf{E}}\bigl{(}{\tilde{X}}h({\tilde{X}},Q)\bigr{)},\quad{\tilde{\lambda}}_{m,n}=\ln
n-{\tilde{\varkappa}}\frac{m}{n}.$

The following lemma is a simple consequence of Lemma 1.

######  Lemma 2.

Let $c$ be a real number. Assume that ${\bf{E}}(Xh(X,Q)\ln(X+1))<\infty$,
${\bf{E}}(Q{\mathbb{I}}_{\\{X\geq 2\\}})>0$. Assume that
${\tilde{\lambda}}_{m,n}\to c$ as $n\to+\infty$. Denote
$\delta_{n}={\tilde{\lambda}}_{m,n}+\frac{2}{{\tilde{\varkappa}}}$ and
$\delta=2c+\frac{3}{\varkappa}$. For any $0<\beta<1$ there exists
$n_{\beta}>0$ depending on $\beta$ and on the probability distribution of
$(X,Q)$ such that for $n>n_{\beta}$ we have

${\hat{q}}_{k}^{m}\leq e^{-k\ln n+k\delta_{n}},\qquad{\hat{q}}_{k}^{m-k}\leq
e^{-k\ln n+k\delta_{n}+\frac{k^{2}}{n}\ln n},\qquad{\text{for}}\qquad 1\leq
k\leq n^{\beta}.$ (7)

We note that ${\tilde{\lambda}}_{m,n}\to c$ and
${\tilde{\varkappa}}\to\varkappa$ implies $\delta_{n}\leq\delta$ for
sufficiently large $n$.

###### Proof of Lemma 2.

To show (7) we combine inequality $1+x\leq e^{x}$ with the inequality

${\hat{q}}_{k}\leq 1-\frac{k}{n}{\tilde{\varkappa}}+\frac{k}{n}\frac{2}{\ln
n},$ (8)

which holds for sufficiently large $n$. Inequality (8) is a simple consequence
of Lemma 1, see also formula (27) of [1]. ∎

######  Lemma 3.

Let $c$ be a real number. Let $n\to+\infty$. Assume that $m=m(n)\to\infty$.
Assume that ${\bf{E}}(Xh(X,Q)\ln(X+1))<\infty$ and
${\bf{E}}(Q{\mathbb{I}}_{\\{X\geq 2\\}})>0$. Assume that
${\tilde{\lambda}}_{m,n}\to c$. Then

${\bf{P}}\\{G_{[n,m]}\rm{\ has\ a\ component\ on}\ k\ \rm{vertices\ for\
some}\ 2\leq k\leq n/2\\}=o(1).$ (9)

We remark that condition ${\tilde{\lambda}}_{m,n}\to c$ can be replaced by
$\lambda_{m,n}\to c$.

###### Proof of Lemma 3.

In the proof we use the notation introduced in the proof of Theorem 1. Before
the proof we introduce some more notation and collect auxiliary results. We
denote $\beta=\max\\{1-\frac{\alpha}{2\varkappa},\frac{1}{2}\\}$. For a subset
$U\subset{\cal V}$ we denote by ${\cal B}_{U}$ the event that $U$ induces a
connected component of $G_{[n,m]}$. Below we use the simple identity

$Y_{k}=\sum_{U\subset V,|U|=k}{\mathbb{I}}_{{\cal B}_{U}}.$ (10)

We denote by ${\cal D}_{U}$ the event that $G_{[n,m]}$ has no edges connecting
vertex sets $U$ and ${\cal V}\setminus U$. Note that ${\bf{P}}\\{{\cal
B}_{U}\\}\leq{\bf{P}}\\{{\cal D}_{U}\\}$.

We observe that the integrability condition ${\bf{E}}(Xh(X,Q)\ln(1+X))<\infty$
implies that there exists an increasing function $\phi(t)\uparrow+\infty$ as
$t\to+\infty$ (depending on the distribution of $(X,Q)$) such that

${\bf{E}}(X\phi(X)h(X,Q)\ln(1+X))<\infty.$ (11)

Moreover, one can choose $\phi(t)$ such that the function $t\to
t/(\phi(t)\ln(1+t))$ was increasing for $t=1,2,\dots$ and $\phi(1)=1$.

Furthermore we observe that $\zeta:={\bf{E}}(X\phi(X)Q\ln(1+X))<\infty$.
Indeed, the inequality $q\leq h(x,q)$, which holds for $x\geq 2$, implies

${\bf{E}}(X\phi(X)Q\ln(1+X))\leq{\bf{P}}\\{X=1\\}\ln
2+{\bf{E}}(X\phi(X){\mathbb{I}}_{\\{X\geq 2\\}}h(X,Q)\ln(1+X))<\infty$ (12)

(here we use the fact that $X$ is an integer valued random variable). The fact
that $t\to t/(\phi(t)\ln(1+t))$ is increasing for $t\geq 1$ implies
$t/(\phi(t)\ln(1+t))\leq n/(\phi(n)\ln(1+n))$, for $t=1,2,\dots,n$. Using this
inequality we estimate for $a=1,2,\dots$,

$\displaystyle{\tilde{X}}^{a+1}$
$\displaystyle=\frac{{\tilde{X}}}{\phi({\tilde{X}})\ln(1+\tilde{X})}{\tilde{X}}^{a}\phi({\tilde{X}})\ln(1+{\tilde{X}})$
$\displaystyle\leq\frac{n}{\phi(n)\ln(1+n)}{\tilde{X}}^{a}\phi({\tilde{X}})\ln(1+\tilde{X})$
$\displaystyle\leq\frac{n^{a}}{\phi(n)\ln(1+n)}{\tilde{X}}\phi({\tilde{X}})\ln(1+\tilde{X}).$

The latter inequality implies the bound

${\bf{E}}({\tilde{X}}^{a+1}Q^{a})\leq\frac{n^{a}}{\phi(n)\ln(1+n)}\zeta,\qquad
a=1,2,\dots,$ (13)

which we are going to use in the proof of (9).

Now we are ready to prove Lemma 3. Let us show that
${\tilde{\lambda}}_{n,m}\to c\Leftrightarrow\lambda_{n,m}\to c$. Note that
each of these relations yields $m/n=O(\ln n)$. Furthermore, we have
$\lambda_{m,n}-{\tilde{\lambda}}_{m,n}=(\varkappa-{\tilde{\varkappa}})m/n$ and

$\displaystyle 0\leq\varkappa-{\tilde{\varkappa}}$
$\displaystyle\leq{\bf{E}}\left(Xh(X,Q){\mathbb{I}}_{\\{X>n\\}}\right)$ (14)
$\displaystyle\leq\frac{1}{\ln(1+n)}{\bf{E}}\left(Xh(X,Q){\mathbb{I}}_{\\{X>n\\}}\ln(1+X)\right)$
$\displaystyle=o\left(\frac{1}{\ln n}\right).$

We conclude that each of the relations ${\tilde{\lambda}}_{n,m}\to c$ and
$\lambda_{n,m}\to c$ implies $\lambda_{m,n}-{\tilde{\lambda}}_{m,n}=o(1)$.
Hence ${\tilde{\lambda}}_{n,m}\to c\Leftrightarrow\lambda_{n,m}\to c$.

Let us show (9). By the union bound and (10), we have

${\bf{P}}\\{{\cal A}_{2}\\}\leq\sum_{2\leq k\leq n/2}{\bf{P}}\\{Y_{k}\geq
1\\}\leq\sum_{2\leq k\leq n/2}\ \sum_{U\subset{\cal V},|U|=k}{\bf{P}}\\{{\cal
B}_{U}\\}=\sum_{2\leq k\leq n/2}\binom{n}{k}{\bf{P}}\\{{\cal B}_{[k]}\\}.$

In the last step we used the fact that ${\bf{P}}\\{{\cal
B}_{U}\\}={\bf{P}}\\{{\cal B}_{[k]}\\}$ for $|U|=k$. Next, using the
inequality ${\bf{P}}\\{{\cal B}_{[k]}\\}\leq{\bf{P}}\\{{\cal D}_{[k]}\\}$ we
upper bound ${\bf{P}}\\{{\cal A}_{2}\\}\leq S_{0}+S_{1}+S_{2}$, where

$S_{0}=\sum_{2\leq k\leq\varphi_{n}}\binom{n}{k}{\bf{P}}\\{{\cal
B}_{[k]}\\},\qquad S_{1}=\sum_{\varphi_{n}<k\leq
n^{\beta}}\binom{n}{k}{\bf{P}}\\{{\cal D}_{[k]}\\},\qquad
S_{2}=\sum_{n^{\beta}\leq k\leq n/2}\binom{n}{k}{\bf{P}}\\{{\cal D}_{[k]}\\}.$

Here $\beta=\max\left\\{1-\frac{\alpha}{2{\varkappa}},\frac{1}{2}\right\\}$.
The sequence $\varphi_{n}\to+\infty$ as $n\to+\infty$ will be specified
latter. To prove (9) we show that $S_{i}=o(1)$ for $i=0,1,2$.

Proof of $S_{0}=o(1)$. Let us evaluate the probabilities ${\bf{P}}\\{{\cal
B}_{[k]}\\}$, $k\geq 2$. Let $T=(V_{T},{\cal E}_{T})$ be a tree with the
vertex set $V_{T}=[k]\subset{\cal V}$. Fix an integer $1\leq r\leq k-1$. Let
${\tilde{\cal E}}_{T}=({\cal E}_{T}^{(1)},\dots,{\cal E}_{T}^{(r)})$ be an
ordered partition of the set ${\cal E}_{T}$ (every set ${\cal E}_{T}^{(i)}$ is
nonempty, ${\cal E}_{T}^{(i)}\cap{\cal E}_{T}^{(j)}=\emptyset$ for $i\not=j$,
and $\cup_{i=1}^{r}{\cal E}_{T}^{(i)}={\cal E}_{T}$). Let
${\tilde{t}}=(t_{1},\dots,t_{r})\in[m]^{r}$ be a vector with integer valued
coordinates satisfying $t_{1}<t_{2}<\cdots<t_{r}$. Given a pair $({\tilde{\cal
E}}_{T},{\tilde{t}})$, let ${\cal T}({\tilde{\cal E}}_{T},{\tilde{t}})$ denote
the event that ${\cal E}_{T}^{(i)}\subset{\cal E}_{t_{i}}$ for each $1\leq
i\leq r$. The event means that the edges of $T$ are covered by the edges of
$G_{t_{1}},\dots G_{t_{r}}$ so that for every $i$ the edge set ${\cal
E}_{T}^{(i)}$ belongs to the edge set ${\cal E}_{t_{i}}$ of $G_{t_{i}}$. Let
$H_{\tilde{t}}=[m]\setminus\\{t_{1},\dots,t_{r}\\}$ and let ${\cal
I}(V_{T},H_{\tilde{t}})$ be the event that none of the graphs $G_{i}$, $i\in
H_{\tilde{t}}$ has an edge connecting some $v\in V_{T}$ and $w\in{\cal
V}\setminus V_{T}$.

Let ${\mathbb{T}}_{k}$ denote the set of trees on the vertex set $[k]$. We
have, by the union bound and independence of $G_{1},\dots,G_{m}$, that

${\bf{P}}\\{{\cal
B}_{[k]}\\}\leq\sum_{T\in{\mathbb{T}}_{k}}\sum_{({\tilde{\cal
E}}_{T},{\tilde{t}})}{\bf{P}}\\{{\cal T}({\tilde{\cal
E}}_{T},{\tilde{t}})\\}{\bf{P}}\\{{\cal I}(V_{T},H_{\tilde{t}})\\}.$ (15)

Here the second sum runs over all possible pairs $({\tilde{\cal
E}}_{T},{\tilde{t}})$. Invoking the bound ${\bf{P}}\\{{\cal
I}(V_{T},H_{{\tilde{t}}})\\}\leq e^{-k\ln n+k\delta+1}$, see the second
inequality of Lemma 2, which holds for sufficiently large $n$ uniformly over
${\tilde{t}}=(t_{1},\dots,t_{r})$ with $r\in[1,k]$ satisfying $k\leq\ln n$, we
obtain

${\bf{P}}\\{{\cal B}_{[k]}\\}\leq e^{-k\ln
n+k\delta+1}\sum_{T\in{\mathbb{T}}_{k}}S_{T},\qquad S_{T}:=\sum_{({\tilde{\cal
E}}_{T},{\tilde{t}})}{\bf{P}}\\{{\cal T}({\tilde{\cal
E}}_{T},{\tilde{t}})\\}.$ (16)

We show below that

$S_{T}\leq\frac{1}{\phi(n)}\sum_{r=1}^{k-1}\left(\frac{2}{\varkappa}\right)^{r}\zeta^{r}e^{r}r^{k-1-r}.$
(17)

Invoking this inequality in (16) and using Cayley’s formula
$|{\mathbb{T}}_{k}|=k^{k-2}$ we obtain

${\bf{P}}\\{{\cal B}_{[k]}\\}\leq e^{-k\ln
n+k\delta+1}\frac{R_{k}}{\phi(n)},\qquad
R_{k}:=k^{k-2}\sum_{r=1}^{k-1}\left(\frac{2}{\varkappa}\right)^{r}\zeta^{r}e^{r}r^{k-1-r}.$

Furthermore, using the simple bound
$\binom{n}{k}\leq\frac{n^{k}}{k!}=\frac{e^{k\ln n}}{k!}$ we estimate

$S_{0}\leq\frac{1}{\phi(n)}\sum_{k=2}^{\varphi_{n}}e^{k\delta+1}\frac{R_{k}}{k!}.$

Finally, choosing a nondecreasing (integer valued) sequence
$\varphi_{n}\to+\infty$ as $n\to+\infty$ such that $\varphi_{n}\leq\ln n$ and
$\sum_{k=2}^{\varphi_{n}}e^{k\delta+1}\frac{R_{k}}{k!}=o(\phi(n))$ we obtain
$S_{0}=o(1)$.

Proof of (17). Given a tree $T=([k],{\cal E}_{T})$ and partition ${\tilde{\cal
E}}_{T}=({\cal E}_{T}^{(1)},\dots,{\cal E}_{T}^{(r)})$, let $V_{T}^{(i)}$ be
the set of vertices incident to the edges from ${\cal E}_{T}^{(i)}$. We denote
$e_{i}=|{\cal E}_{T}^{(i)}|$ and $v_{i}=|V_{T}^{(i)}|$. For any labeling
${\tilde{t}}=(t_{1},\dots,t_{r})$ that assigns labels $t_{1},\dots,t_{r}$ to
the sets ${\cal E}_{T}^{(1)},\dots,{\cal E}_{T}^{(r)}$ we have, by the
independence of $G_{1},\dots,G_{m}$,

${\bf{P}}\\{{\cal T}({\tilde{\cal
E}}_{T},{\tilde{t}})\\}=\prod_{i=1}^{r}{\bf{E}}\left(\frac{({\tilde{X}}_{t_{i}})_{v_{i}}}{(n)_{v_{i}}}Q_{t_{i}}^{e_{i}}\right).$

We note that the fraction $\frac{({\tilde{X}}_{t_{i}})_{v_{i}}}{(n)_{v_{i}}}$
is a decreasing function of $v_{i}$ and it is maximized by
$\frac{({\tilde{X}}_{t_{i}})_{e_{i}+1}}{(n)_{e_{i}+1}}$ since we always have
$v_{i}\geq e_{i}+1$. Indeed, given $|{\cal E}_{T}^{(i)}|=e_{i}$ the smallest
possible set of vertices $V_{T}^{(i)}$ corresponds to the configuration of
edges of ${\cal E}_{T}^{(i)}$ that creates a subtree $(V_{T}^{(i)},{\cal
E}_{T}^{(i)})\subset T$. Hence $v_{i}\geq e_{i}+1$. It follows that

${\bf{P}}\\{{\cal T}({\tilde{\cal
E}}_{T},{\tilde{t}})\\}\leq\prod_{i=1}^{r}{\bf{E}}\left(\frac{({\tilde{X}}_{t_{i}})_{e_{i}+1}}{(n)_{e_{i}+1}}Q_{t_{i}}^{e_{i}}\right)\leq\left(\frac{\zeta}{n\phi(n)\ln(1+n)}\right)^{r}.$
(18)

In the last step we used (13).

Let us evaluate the sum $S_{T}$. For $1\leq r\leq k-1$ and a vector
$(e_{1},\dots,e_{r})$ with integer valued coordinates satisfying
$e_{1}+\cdots+e_{r}=k-1$ and $e_{i}\geq 1$ $\forall i$, there are
$\frac{(k-1)!}{e_{1}!\cdots e_{r}!}$ ordered partitions ${\tilde{\cal
E}}_{T}=({\cal E}_{T}^{(1)},\dots,{\cal E}_{T}^{(r)})$ of ${\cal E}_{T}$ in
$r$ non empty parts of sizes $|{\cal E}_{T}^{(1)}|=e_{1},\dots,|{\cal
E}_{T}^{(r)}|=e_{r}$. Therefore we have

$\displaystyle S_{T}$
$\displaystyle\leq\sum_{r=1}^{k-1}\binom{m}{r}\sum^{\prime}_{e_{1}+\dots+e_{r}=k-1}\frac{(k-1)!}{e_{1}!\cdots
e_{r}!}\ \left(\frac{\zeta}{n\phi(n)\ln(1+n)}\right)^{r}$
$\displaystyle\leq\sum_{r=1}^{k-1}\binom{m}{r}\left(\frac{\zeta}{n\phi(n)\ln(1+n)}\right)^{r}r^{k-1}.$

Here the sum $\sum^{\prime}_{e_{1}+\dots+e_{r}=k-1}$ runs over the set of
vectors $(e_{1},\dots,e_{r})$ having integer valued coordinates $e_{i}\geq 1$
satisfying $e_{1}+\cdots+e_{r}=k-1$.

Invoking inequalities $\binom{m}{r}\leq\left(\frac{me}{r}\right)^{r}$ and
$\frac{m}{n\ln(1+n)}\leq\frac{2}{\varkappa}$ (the last inequality holds for
sufficiently large $n$ and $m$) we arrive to (17)

$S_{T}\leq\frac{1}{\phi(n)}\sum_{r=1}^{k-1}\left(\frac{m}{n\ln(1+n)}\right)^{r}\zeta^{r}e^{r}r^{k-1-r}\leq\frac{1}{\phi(n)}\sum_{r=1}^{k-1}\left(\frac{2}{\varkappa}\right)^{r}\zeta^{r}e^{r}r^{k-1-r}.$

Proof of $S_{1}=o(1)$. The first inequality of Lemma 4 implies
${\bf{P}}\\{{\cal D}_{[k]}\\}\leq e^{-k\ln n+k\delta}$. Invoking the
inequality $\binom{n}{k}\leq\frac{n^{k}}{k!}$ we obtain

$S_{1}\leq\sum_{\varphi_{n}<k\leq
n^{\beta}}\frac{e^{k\delta}}{k!}\leq\sum_{k>\varphi_{n}}\frac{e^{k\delta}}{k!}.$

For $n\to+\infty$ we have $S_{1}=o(1)$ because $\varphi_{n}\to+\infty$ and the
series $\sum_{k\geq 1}\frac{e^{k\delta}}{k!}$ converges.

Proof of $S_{2}=o(1)$. The proof is much the same as that of the corresponding
bound in the proof of Proposition 1 of [1]. In particular, we use the
inequality $\binom{n}{k}\leq e^{2k+(1-\beta)k\ln n}$, which holds for
$n^{\beta}\leq k\leq n/2$, and the inequality

${\hat{q}}_{k}\leq 1-\alpha\frac{k}{n},\qquad 1\leq k\leq n/2.$

Both inequalities are shown in the proof of Proposition 1 of [1]. Combining
these inequalities and $1+x\leq e^{x}$ we estimate the product

$\binom{n}{k}{\bf{P}}\\{{\cal D}_{k}\\}=\binom{n}{k}{\hat{q}}_{k}^{m}\leq
e^{2k+(1-\beta)k\ln n-\alpha
k\frac{m}{n}}=e^{k\left(2+\alpha\frac{{\tilde{\lambda}}_{m,n}}{{\tilde{\varkappa}}}\right)-k\left(\frac{\alpha}{\tilde{\varkappa}}+\beta-1\right)\ln
n}.$ (19)

In the last step we used $\frac{m}{n}=\frac{1}{\tilde{\varkappa}}(\ln
n-{\tilde{\lambda}}_{m,n})$. For $\lambda_{m,n}\to c$ and
$\varkappa-{\tilde{\varkappa}}=o\left(\frac{1}{\ln n}\right)$, see (14), the
quantity on the right of (19) becomes
$e^{-k\left(\frac{\alpha}{\varkappa}+\beta-1+o(1)\right)\ln n}$. Since our
choice of $\beta$ yields
$\frac{\alpha}{\varkappa}+\beta-1\geq\frac{\alpha}{2\varkappa}$, we have
$S_{2}\leq\sum_{k\geq
n^{\beta}}e^{-k\left(\frac{\alpha}{2\varkappa}+o(1)\right)\ln n}=o(1)$.

∎

######  Lemma 4.

Let $c$ be a real number. Let $\Lambda$ be a random variable having the
Poisson distribution with mean value $e^{c}$. Assume that conditions of Lemma
3 hold. Then the number of vertices of degree $0$ in $G_{[n,m]}$ converges in
distribution to $\Lambda$.

###### Proof of Lemma 4.

Let $Y_{0}$ denote the number of vertices $v_{i}$ of $G_{[n,m]}$ having degree
$d(v_{i})=0$. We apply the method of moments to show that $Y_{0}$ converges in
distribution to $\Lambda$. To this aim we establish the convergence of the
factorial moments as $n\to+\infty$

${\bf{E}}(Y_{0})_{r}\to{\bf{E}}(\Lambda)_{r},\qquad{\text{for}}\qquad
r=1,2,\dots.$ (20)

Note that ${\bf{E}}(\Lambda)_{r}=e^{rc}$. Let us evaluate
${\bf{E}}(Y_{0})_{r}$. In the proof we use the identity

$\binom{Y_{0}}{r}=\sum_{\\{v_{i_{1}},\dots,v_{i_{r}}\\}\subset{\cal
V}}{\mathbb{I}}_{\\{d(v_{i_{1}})=0\\}}\cdots{\mathbb{I}}_{\\{d(v_{i_{r}})=0\\}},$

where both sides count the (same) number of subsets of size $r$ of vertices
having degree $0$. Taking the expected values we obtain, by symmetry,

$\displaystyle{\bf{E}}(Y_{0})_{r}$
$\displaystyle=r!{\bf{E}}\left(\sum_{\\{v_{i_{1}},\dots,v_{i_{r}}\\}\subset{\cal
V}}{\mathbb{I}}_{\\{d(v_{i_{1}})=0\\}}\cdots{\mathbb{I}}_{\\{d(v_{i_{r}})=0\\}}\right)$
$\displaystyle=r!\binom{n}{r}{\bf{P}}\\{d(v_{1})=0,\dots,d(v_{r})=0\\}.$ (21)

Furthermore, by the independence of $G_{1},\dots,G_{m}$, we have

${\bf{P}}\\{d(v_{1})=0,\dots,d(v_{r})=0\\}=P_{r}^{m},\qquad{\text{where}}\qquad
P_{r}:={\bf{P}}\\{d_{1}(v_{1})=0,\dots,d_{1}(v_{r})=0\\}.$

Here $d_{1}(v)$ denotes the degree of $v$ in $G_{1}=({\cal V}_{1},{\cal
E}_{1})$ and we put $d_{1}(v)=0$ for $v\notin{\cal V}_{1}$.

Next we approximate $P_{r}=1-{\bf{P}}\\{\cup_{i=1}^{r}\\{d_{1}(v_{i})>0\\}\\}$
using inclusion-exclusion inequalities

$S_{1}-S_{2}\leq 1-P_{r}\leq S_{1},$ (22)

where

$\displaystyle S_{1}$
$\displaystyle=\sum_{i=1}^{r}{\bf{P}}\\{d_{1}(v_{i})>0\\}=r{\bf{P}}\\{d_{1}(v_{1})>0\\},$
$\displaystyle S_{2}$ $\displaystyle=\sum_{1\leq i<j\leq
r}{\bf{P}}\\{d_{1}(v_{i})>0,\,d_{1}(v_{j})>0\\}=\binom{r}{2}{\bf{P}}\\{d_{1}(v_{1})>0,\,d_{1}(v_{2})>0\\}.$

A straightforward calculation shows that

${\bf{P}}\\{d_{1}(v_{1})>0\\}={\bf{E}}\left(\frac{{\tilde{X}}_{1}}{n}\bigl{(}1-(1-Q_{i})^{({\tilde{X}}_{1}-1)_{+}}\bigr{)}\right)=\frac{{\tilde{\varkappa}}}{n}.$
(23)

Here $\frac{{\tilde{X}}_{1}}{n}$ accounts for the probability of the event
$v_{1}\in{\cal V}_{1}$ and $(1-(1-Q_{i})^{({\tilde{X}}_{1}-1)_{+}}$ accounts
for the probability that given vertex of $G_{1}$ is not isolated in $G_{1}$.
Similarly, we have

${\bf{P}}\\{d_{1}(v_{1})>0\cap
d_{1}(v_{2})>0\\}={\bf{E}}\left(\frac{({\tilde{X}}_{1})_{2}}{(n)_{2}}h_{1}({\tilde{X}}_{1},Q_{1})\right),$

where
$h_{1}({\tilde{X}}_{1},Q_{1})=Q_{1}+(1-Q_{1})\bigl{(}1-(1-Q_{1})^{({\tilde{X}}_{1}-2)_{+}}\bigr{)}^{2}$
accounts for the pobability that given a pair of vertices of $G_{1}$ none of
them is isolated in $G_{1}$. $\frac{({\tilde{X}}_{1})_{2}}{(n)_{2}}$ accounts
for the probability that $\\{v_{1},v_{2}\\}\subset{\cal V}_{1}$. Invoking the
inequality $h_{1}(x,q)\leq h(x,q)$, which holds for $x\geq 2$,

$\displaystyle h_{1}(x,q)$
$\displaystyle=q+(1-q)\Bigl{(}1-2(1-q)^{(x-2)_{+}}+(1-q)^{2(x-2)_{+}}\Bigr{)}$
$\displaystyle=1-2(1-q)^{1+(x-2)_{+}}+(1-q)^{1+2(x-2)_{+}}$
$\displaystyle=1-(1-q)^{1+(x-2)_{+}}-\Bigl{(}(1-q)^{1+(x-2)_{+}}-(1-q)^{1+2(x-2)_{+}}\Bigr{)}$
$\displaystyle\leq 1-(1-q)^{1+(x-2)_{+}}=1-(1-q)^{(x-1)_{+}}=h(x,q),$

(we only need $x\geq 2$ in the second last identity) we obtain

${\bf{P}}\\{d_{1}(v_{1})>0\cap
d_{1}(v_{2})>0\\}\leq{\bf{E}}\left(\frac{({\tilde{X}}_{1})_{2}}{(n)_{2}}h({\tilde{X}}_{1},Q_{1})\right)=:\Delta.$
(24)

We show below that $\Delta=o\left(\frac{1}{n\ln n}\right)$. This bound implies
$S_{2}=o\left(\frac{r^{2}}{n\ln n}\right)$ and, together with (22) and (23),
it yields the approximation

$P_{r}=1-{\tilde{\varkappa}}\frac{r}{n}+o\left(\frac{r^{2}}{n\ln n}\right).$

Finally, using $(n)_{r}=(1+o(1))e^{r\ln n}$ and
$1-x=e^{\ln(1-x)}=e^{-x+O(x^{2})}$ as $x\to 0$ we obtain

${\bf{E}}(Y_{0})_{r}=(n)_{r}P_{r}^{m}=(1+o(1))e^{r\ln
n}e^{-r{\tilde{\varkappa}}\frac{m}{n}+o(1)}=(1+o(1))e^{r{\tilde{\lambda}}_{m,n}+o(1)}.$

Now (20) follows by our assumption ${\tilde{\lambda}}_{m,n}\to c$.

It remains to show that $\Delta=o\left(\frac{1}{n\ln n}\right)$. To this aim
we show that
${\bf{E}}({\tilde{X}}_{1}^{2}h({\tilde{X}}_{1},Q_{1}))=o\left(\frac{n}{\ln
n}\right)$. We split

${\bf{E}}({\tilde{X}}_{1}^{2}h({\tilde{X}}_{1},Q_{1}))={\bf{E}}(X_{1}^{2}h(X_{1},Q_{1}){\mathbb{I}}_{\\{X_{1}\leq
n\\}})+n^{2}{\bf{E}}(h(n,Q_{1}){\mathbb{I}}_{\\{X_{1}>n\\}})=:\Delta_{1}+n^{2}\Delta_{2}$

and treat $\Delta_{1}$ and $\Delta_{2}$ separately. By the fact that $t\to
t/(\phi(t)\ln(1+t))$ is increasing,

$\displaystyle\Delta_{1}$
$\displaystyle={\bf{E}}\left(\frac{X_{1}}{\phi(X_{1})\ln(1+X_{1})}X_{1}\phi(X_{1})\ln(1+X_{1}){\mathbb{I}}_{\\{X_{1}\leq
n\\}}\right)$
$\displaystyle\leq\frac{n}{\phi(n)\ln(1+n)}{\bf{E}}(X_{1}\phi(X_{1})\ln(1+X_{1}){\mathbb{I}}_{\\{X_{1}\leq
n\\}})$ $\displaystyle\leq\frac{\gamma}{\phi(n)}\frac{n}{\ln(1+n)}.$

Here $\gamma:={\bf{E}}(X_{1}\phi(X_{1})\ln(1+X_{1}))<\infty$. Now
$\phi(n)\to+\infty$ implies $\Delta_{1}=o\left(\frac{n}{\ln n}\right)$.
Furthermore, by the fact that $t\to t\ln(1+t)$ is increasing and $t\to h(t,q)$
is nondecreasing, we have

$\displaystyle\Delta_{2}\leq{\bf{E}}\left(\frac{X_{1}\ln(1+X_{1})}{n\ln(1+n)}h(X_{1},Q_{1}){\mathbb{I}}_{\\{X_{1}>n\\}}\right)=o\left(\frac{1}{n\ln
n}\right).$

In the last step we used the fact that $\gamma<\infty$ implies
${\bf{E}}\left(X_{1}\ln(1+X_{1})h(X_{1},Q_{1}){\mathbb{I}}_{\\{X_{1}>n\\}}\right)=o(1)$
as $n\to+\infty$. We conclude that $n^{2}\Delta_{2}=o\left(\frac{n}{\ln
n}\right)$. ∎

###  2.2 Proof of Theorem 2

Before the proof we introduce some notation. Let ${\hat{q}}_{k}^{[n,i]}$
denote the probability that $G_{n,i}$ has no edge with one endpoint in $[k]$
and another endpoint in $[n]\setminus[k]$. We denote

$\displaystyle\kappa_{n,i}={\bf{E}}\bigl{(}X_{n,i}h(X_{n,i},Q_{n,i})\bigr{)},\qquad\alpha_{n,i}={\bf{E}}\bigl{(}Q_{n,i}{\mathbb{I}}_{\\{X_{n,i}\geq
2\\}}\bigr{)},$
$\displaystyle\alpha_{n}={\bf{E}}\bigl{(}Q_{n,i_{*}}{\mathbb{I}}_{\\{X_{n,i_{*}}\geq
2\\}}\bigr{)},\qquad\qquad\ \,\alpha={\bf{E}}\bigl{(}Q{\mathbb{I}}_{\\{X\geq
2\\}}\bigr{)}$

and observe that

$\sum_{i=1}^{m}\alpha_{n,i}=m\alpha_{n},\qquad\sum_{i=1}^{m}\kappa_{n,i}=m\kappa_{n}.$

Furthermore, we observe that the weak convergence $P_{n,m}\to P$ together with
the convergence of moments (3) implies

$\alpha_{n}\to\alpha\ \bigl{(}={\bf{E}}(Q{\mathbb{I}}_{\\{X\geq
2\\}})\bigr{)},\qquad\kappa_{n}\to\varkappa\
\bigl{(}={\bf{E}}(Xh(X,Q))\bigr{)}\qquad{\text{as}}\qquad n\to+\infty.$ (25)

Moreover, the sequence of random variables
$\\{X_{n,i_{*}}h(X_{n,i_{*}},Q_{n,i_{*}})\ln(1+X_{n,i_{*}}),\,n\geq 1\\}$ is
uniformly integrable. That is, we have

$\lim_{t\to+\infty}\sup_{n}{\bf{E}}\left(X_{n,i_{*}}h(X_{n,i_{*}},Q_{n,i_{*}})\ln(1+X_{n,i_{*}}){\mathbb{I}}_{\\{X_{n,i_{*}}\geq
t\\}}\right)=0.$

Using the uniform integrability property above we can construct a positive
increasing function $\phi(x)$ such that $\lim_{x\to+\infty}\phi(x)=+\infty$
and the sequence of random variables
$\\{X_{n,i_{*}}h(X_{n,i_{*}},Q_{n,i_{*}})\phi(X_{n,i_{*}})\ln(1+X_{n,i_{*}}),\,n\geq
1\\}$ is uniformly integrable, see [1]. We denote

$\displaystyle\varphi(t)=\sup_{n}{\bf{E}}\left(X_{n,i_{*}}h(X_{n,i*},Q_{n,i_{*}})\phi(X_{n,i_{*}})\ln(1+X_{n,i_{*}}){\mathbb{I}}_{\\{X_{n,i_{*}}\geq
t\\}}\right).$

The uniform integrability implies $\varphi(t)\to 0$ as $t\to+\infty$.
Moreover, one can choose $\phi(x)$ such that the function $x\to
x/(\phi(x)\ln(1+x))$ was increasing for $x=1,2,\dots$, see [1]. Furthermore,
the same argument as in (12) shows that

$\zeta_{*}:=\sup_{n}{\bf{E}}\left(X_{n,i_{*}}Q_{n,i_{*}}\phi(X_{n,i_{*}})\ln(1+X_{n,i_{*}})\right)<\infty.$

In the proof below we use the bounds shown in [1]

$\displaystyle{\bf{E}}\bigl{(}X_{n,i_{*}}^{2}h(X_{n,i_{*}},Q_{n,i_{*}})\bigr{)}=o\left(\frac{n}{\ln
n}\right),$ (26) $\displaystyle\max_{1\leq i\leq
n}\kappa^{2}_{n,i}\leq\sum_{i\in[m]}\kappa^{2}_{n,i}\leq
m{\bf{E}}(X^{2}_{n,i_{*}}h(X_{n,i_{*}},Q_{n,i_{*}}))=o\left(\frac{mn}{\ln
n}\right).$ (27)

We note that for $m=O(n\ln n)$ the quantity on the right of (27) is
$o(n^{2})$.

###### Proof of Theorem 2.

In the case where $\lambda^{*}_{m,n}\to\pm\infty$ the zero - one law of (4) is
shown in Theorem 1 of [1]. It remains to show (4) in the case where
$\lambda^{*}_{m,n}\to c$. In this case we proceed similarly as in the proof of
Theorem 1. The only difference is that now we use Lemmas 5 and 6 (shown below)
instead of Lemmas 3 and 4. ∎

######  Lemma 5.

Let $c$ be a real number. Let $n,m\to+\infty$. Assume that conditions of
Theorem 2 hold. Assume that $\lambda^{*}_{n,m}\to c$. Then

${\bf{P}}\\{G_{[n,m]}\rm{\ has\ a\ component\ on}\ k\ \rm{vertices\ for\
some}\ 2\leq k\leq n/2\\}=o(1).$ (28)

###### Proof of Lemma 5.

The proof is similar to that of Lemma 3 and we use notation introduced there.
Several minor modifications needed are explained in detail.

Let $\beta=\max\\{1-\frac{\alpha}{2\varkappa},\frac{1}{2}\\}$. We upper bound
the probability ${\bf{P}}\\{{\cal A}_{2}\\}$ by the sum ${\bf{P}}\\{{\cal
A}_{2}\\}\leq S_{0}+S_{1}+S_{2}$, where $S_{0},S_{1},S_{2}$ are the same as in
the proof of Lemma 3, and show that $S_{j}=o(1)$ for $j=0,1,2$. The sequence
$\varphi_{n}\to+\infty$ as $n\to+\infty$ entering the expressions of $S_{0}$,
$S_{1}$ above will be specified later.

Before the proof we collect some useful facts. We note that our assumption
$\lambda^{*}_{n,m}\to c$ together with (25) implies
$m=(\varkappa^{-1}+o(1))n\ln n$. In particular, we have $m=O(n\ln n)$.

Next, given $U\subset{\cal V}=[n]$ of size $|U|\leq n^{\beta}$ and
$H\subset[m]$, we evaluate the probability of the event ${\cal I}(U,H)$ that
none of the graphs $G_{n,i}$, $i\in H$ has an edge connecting some $v\in U$
and $w\in{\cal V}\setminus U$. Using inequality

${\hat{q}}^{[n,i]}_{k}\leq
1-\frac{k}{n}\kappa_{n,i}+R_{1}+{\bf{E}}\left(R_{2}(k,X_{n,i})h(X_{n,i},Q_{n,i})\right),$

which follows from (6), we obtain for $U=[k]$ and any $H\subset[m]$ of size
$h=|H|$ that

${\bf{P}}\\{{\cal I}([k],H)\\}=\prod_{i\in H}{\hat{q}}_{k}^{[n,i]}\leq
e^{-\frac{k}{n}S_{1}(H)+hR_{1}+S_{2}(H)}.$ (29)

Here we denote

$S_{1}(H)=\sum_{i\in H}\kappa_{n,i},\qquad S_{2}(H)=\sum_{i\in
H}{\bf{E}}\left(R_{2}(k,X_{n,i})h(X_{n,i},Q_{n,i})\right).$

Let us evaluate the second and third term in the argument of the exponent in
(29). We have

$S_{2}(H)\leq
S_{2}([m])=m{\bf{E}}\left(R_{2}(k,X_{n,i_{*}})h(X_{n,i_{*}},Q_{n,i_{*}})\right)\leq
2k\frac{m}{n\ln n}.$

In the last step we used the bound shown in formula (36) of [1]

${\bf{E}}\left(R_{2}(k,X_{n,i_{*}})h(X_{n,i_{*}},Q_{n,i_{*}})\right)\leq\frac{k}{n}\frac{2}{\ln
n},$

which holds uniformly in $1\leq k\leq n^{\beta}$ for all sufficiently large
$n$ (say $n>n_{\beta}$, where $n_{\beta}$ depends on $\beta$ and the
probability distribution of the array of random variables $\\{X_{n,i},1\leq
i\leq m(n),\,n=1,2,\dots\\}$, see [1]). Furthermore, for $m=O(n\ln n)$ and
$1\leq k\leq n^{\beta}$ we have

$hR_{1}\leq
mR_{1}=m\frac{k^{2}}{(n-k)^{2}}=\frac{mk^{2}}{n^{2}(1-o(1))}=O\left(k^{2}\frac{\ln
n}{n}\right)=O\left(k\frac{\ln n}{n^{1-\beta}}\right).$

Invoking in (29) the bounds for $S_{2}(H)$ and $hR_{1}$ and using
$m=(\varkappa^{-1}+o(1))n\ln n$ we obtain

${\bf{P}}\\{{\cal I}([k],H)\\}\leq e^{-\frac{k}{n}S_{1}(H)+2k\frac{m}{n\ln
n}+o(k)}=e^{-\frac{k}{n}S_{1}(H)+k\left(\frac{2}{\varkappa}+o(1)\right)}.$
(30)

Proof of $S_{0}=o(1)$. We first note that for $m=O(n\ln n)$ inequalities (27)
imply

$K_{n}:=\max_{i\in[m]}\kappa_{n,i}=o(n).$ (31)

Hence, there exists an integer sequence $\tau_{n}\to+\infty$ such that
$\tau_{n}^{2}K_{n}\leq n$. Consequently, for any $H\subset[m]$ of size
$|H|\geq m-\tau_{n}$ we have

$S_{1}(H)\geq S_{1}([m])-\tau_{n}K_{n}\geq
S_{1}([m])-\frac{n}{\tau_{n}}=m\kappa_{n}-\frac{n}{\tau_{n}}$

and, by (30),

${\bf{P}}\\{{\cal I}([k],H)\\}\leq
e^{-k\frac{m}{n}\kappa_{n}+k\left(\frac{2}{\varkappa}+o(1)\right)}=e^{-k\ln
n+k\left(\frac{2}{\varkappa}+c+o(1)\right)}.$ (32)

We choose $\varphi_{n}$ such that $\varphi_{n}\leq\tau_{n}$ and upper bound
$S_{0}=\sum_{2\leq k\leq\varphi_{n}}\binom{n}{k}{\bf{P}}\\{{\cal B}_{[k]}\\}$
similarly as in the proof of Lemma 3, see (15), (16) above. In view of (32)
inequality (16) now reads as follows

${\bf{P}}\\{{\cal B}_{[k]}\\}\leq e^{-k\ln
n+k\left(\frac{2}{\varkappa}+c+o(1)\right)}\sum_{T\in{\mathbb{T}}_{k}}S_{T},\qquad
S_{T}=\sum_{({\tilde{\cal E}},{\tilde{t}})}{\bf{P}}\\{{\cal T}({\tilde{\cal
E}},{\tilde{t}})\\}.$ (33)

We recall that ${\mathbb{T}}_{k}$ stands for the set of all spanning trees
with the vertex set $[k]$, ${\tilde{\cal E}}_{T}=({\tilde{\cal
E}}_{T}^{(1)},\dots,{\tilde{\cal E}}_{T}^{(r)})$ denotes an ordered partition
of the edge set of a tree $T$, and the event ${\cal T}({\tilde{\cal
E}},{\tilde{t}})$ is defined in the proof of Lemma 3 above. We show below that

$S_{T}\leq\frac{1}{\phi(n)}\sum_{r=1}^{k-1}\left(\frac{2\zeta_{*}}{\varkappa}\right)^{r}r^{k-1}.$
(34)

Invoking this inequality in (33) and using Cayley’s formula
$|{\mathbb{T}}_{k}|=k^{k-2}$ we obtain

${\bf{P}}\\{{\cal B}_{[k]}\\}\leq e^{-k\ln
n+k\left(\frac{2}{\varkappa}+c+o(1)\right)}\frac{R_{k}}{\phi(n)},\qquad
R_{k}:=k^{k-2}\sum_{r=1}^{k-1}\left(\frac{2\zeta_{*}}{\varkappa}\right)^{r}r^{k-1}.$

Hence

$S_{0}\leq\frac{1}{\phi(n)}\sum_{k=2}^{\varphi_{n}}e^{k\left(\frac{2}{\varkappa}+c+o(1)\right)}\frac{R_{k}}{k!}.$

Finally, since $\phi(n)\to+\infty$ as $n\to+\infty$, we can choose
$\varphi_{n}\to+\infty$ growing slowly enough such that the quantity on the
right was $o(1)$. We remark that condition $\varphi_{n}\leq\ln n$ used in the
proof of Lemma 3 is now replaced now by the condition
$\varphi_{n}\leq\tau_{n}$.

It remains to prove (34). Given an ordered partition ${\tilde{\cal
E}}_{T}=({\tilde{\cal E}}_{T}^{(1)},\dots,{\tilde{\cal E}}_{T}^{(r)})$ we
denote by $|{\tilde{\cal E}}_{T}|$ the number of parts (in this case
$|{\tilde{\cal E}}_{T}|=r$). For ${\tilde{t}}=(t_{i_{1}},\dots,t_{i_{r}})$ we
denote by $|{\tilde{t}}|$ the number of coordinates (in this case
$|{\tilde{t}}|=r$). We have

$\displaystyle S_{T}=\sum_{({\tilde{\cal E}}_{T},{\tilde{t}})}{\bf{P}}\\{{\cal
T}({\tilde{\cal E}}_{T},{\tilde{t}})\\}=\sum_{r=1}^{k-1}\
\frac{1}{r!}\sum_{{\tilde{\cal E}}_{T}:\,|{\tilde{\cal
E}}_{T}|=r}S({\tilde{\cal E}}_{T}),\qquad S({\tilde{\cal
E}}_{T}):=\sum_{{\tilde{t}}:\,|{\tilde{t}}|=|{\tilde{\cal
E}}_{T}|}{\bf{P}}\\{{\cal T}({\tilde{\cal E}}_{T},{\tilde{t}})\\}.$

The last sum runs over the set of vectors ${\tilde{t}}=(t_{1},\dots t_{r})$
having distinct coordinates $t_{1},\dots,t_{r}\in[m]$. Proceeding as in the
proof of Lemma 3 we show for ${\tilde{\cal E}}_{T}=({\tilde{\cal
E}}_{T}^{(1)},\dots,{\tilde{\cal E}}_{T}^{(r)})$ with $|{\tilde{\cal
E}}_{T}^{(1)}|=e_{1},\dots,|{\tilde{\cal E}}_{T}^{(r)}|=e_{r}$ that

${\bf{P}}\\{{\cal T}({\tilde{\cal
E}}_{T},{\tilde{t}})\\}\leq\prod_{i=1}^{r}{\bf{E}}\left(\frac{(X_{n,t_{i}})_{e_{i}+1}}{(n)_{e_{i}+1}}Q_{n,t_{i}}^{e_{i}}\right).$

Consequently, the sum $S({\tilde{\cal E}}_{T})$ is upper bounded by the sum

$S_{*}({\tilde{\cal
E}}_{T}):=\sum_{t_{1}=1}^{m}\cdots\sum_{t_{r}=1}^{m}\prod_{i=1}^{r}{\bf{E}}\left(\frac{(X_{n,t_{i}})_{e_{i}+1}}{(n)_{e_{i}+1}}Q_{n,t_{i}}^{e_{i}}\right)=m^{r}\prod_{i=1}^{r}{\bf{E}}\left(\frac{(X_{n,i_{*}})_{e_{i}+1}}{(n)_{e_{i}+1}}Q_{n,i_{*}}^{e_{i}}\right).$

Invoking the bound (which is shown similarly as (13) above)

${\bf{E}}\left(X_{n,i_{*}}^{a+1}Q_{n,i_{*}}^{a}\right)\leq\frac{n^{a}}{\phi(n)\ln(1+n)}\zeta_{*},\quad
a=1,2,\dots,$

we obtain

$S_{*}({\tilde{\cal E}}_{T})\leq
m^{r}\left(\frac{\zeta_{*}}{n\phi(n)\ln(1+n)}\right)^{r}.$

Next, using the fact that there are $\frac{(k-1)!}{e_{1}!\cdots e_{r}!}$
distinct ordered partitions ${\tilde{\cal E}}_{T}=({\tilde{\cal
E}}_{T}^{(1)},\dots,{\tilde{\cal E}}_{T}^{(r)})$ with $|{\tilde{\cal
E}}_{T}^{(1)}|=e_{1},\dots,|{\tilde{\cal E}}_{T}^{(r)}|=e_{r}$, we upper bound

$\displaystyle S_{T}$
$\displaystyle\leq\sum_{r=1}^{k-1}\sum^{\prime}_{e_{1}+\cdots+e_{r}=k-1}\frac{(k-1)!}{e_{1}!\cdots
e_{r}!}m^{r}\left(\frac{\zeta_{*}}{n\phi(n)\ln(1+n)}\right)^{r}$
$\displaystyle\leq\sum_{r=1}^{k-1}m^{r}\left(\frac{\zeta_{*}}{n\phi(n)\ln(1+n)}\right)^{r}r^{k-1}.$

Here the sum $\sum^{\prime}_{e_{1}+\dots+e_{r}=k-1}$ runs over the set of
vectors $(e_{1},\dots,e_{r})$ having integer valued coordinates $e_{i}\geq 1$
satisfying $e_{1}+\cdots+e_{r}=k-1$. Invoking the inequality
$\frac{m}{n\ln(1+n)}\leq\frac{2}{\varkappa}$ (which holds for large $n$) we
obtain (34).

Proof of $S_{1}=o(1)$. We observe that the event ${\cal D}_{k}$ defined in the
proof of Lemma 3 and the event ${\cal I}([k],[m])$ are the same. Hence, by
(30), (32),

${\bf{P}}\\{{\cal D}_{k}\\}={\bf{P}}\\{{\cal I}([k],[m])\\}\leq
e^{-k\frac{m}{n}\kappa_{n}+k\left(\frac{2}{\varkappa}+o(1)\right)}\leq
e^{-k\ln n+k\left(\frac{2}{\varkappa}+c+o(1)\right)}.$

We conclude that

$S_{1}=\sum_{\varphi_{n}\leq k\leq n^{\beta}}\binom{n}{k}{\bf{P}}\\{{\cal
D}_{k}\\}\leq\sum_{k\geq\varphi_{n}}\frac{e^{k\left(\frac{2}{\varkappa}+c+o(1)\right)}}{k!}=o(1)\qquad{\text{as}}\qquad
n\to+\infty$

because the series $\sum\frac{e^{k\left(\frac{2}{\varkappa}+c+1\right)}}{k!}$
converges and $\varphi_{n}\to+\infty$.

Proof of $S_{2}=o(1)$. From (5) we have for $k\leq n/2$

$\displaystyle{\hat{q}}^{[n,i]}_{k}$ $\displaystyle={\bf{P}}\\{X_{n,i}\leq
1\\}+{\bf{E}}\left(q_{k}(X_{n,i},Q_{n,i}){\mathbb{I}}_{\\{X_{n,i}\geq
2\\}}\right)$ $\displaystyle\leq 1-2\alpha_{n,i}\frac{k(n-k)}{n(n-1)}\leq
1-\alpha_{n,i}\frac{k}{n}.$

Consequently,

${\bf{P}}\\{{\cal D}_{k}\\}=\prod_{i\in[m]}{\hat{q}}^{[n,i]}_{k}\leq
e^{-\frac{k}{n}\sum_{i\in[m]}\alpha_{n,i}}=e^{-k\frac{m}{n}\alpha_{n}}.$

Next, proceeding as in (19) above, we estimate using $\frac{m}{n}=\frac{\ln
n}{\varkappa}(1+o(1))$ and $\alpha_{n}=\alpha(1+o(1))$

$\binom{n}{k}{\bf{P}}\\{{\cal D}_{k}\\}\leq e^{2k+(1-\beta)k\ln
n-\alpha_{n}k\frac{m}{n}}=e^{-k\left(\frac{\alpha}{\varkappa}+\beta-1+o(1)\right)\ln
n}\leq e^{-k\left(\frac{\alpha}{2\varkappa}+o(1)\right)\ln n}.$

In the last step we used $\beta\geq 1-\frac{\alpha}{2\varkappa}$. Finally, we
have $S_{2}\leq\sum_{k\geq
n^{\beta}}e^{-k\left(\frac{\alpha}{2\varkappa}+o(1)\right)\ln n}=o(1)$ as
$n\to+\infty$. ∎

######  Lemma 6.

Let $c$ be a real number. let $n,m\to+\infty$. Assume that conditions of
Theorem 2 hold. Assume that $\lambda^{*}_{n,m}\to c$. Then the number of
vertices of degree $0$ in $G_{[n,m]}$ converges in distribution to the Poisson
distribution with the mean $e^{c}$.

###### Proof of Lemma 6.

The proof is similar to that of Lemma 4. The only (minor) difference is in the
evaluation of the probability $p:={\bf{P}}\\{d(v_{1})=0,\dots,d(v_{r})=0\\}$
of (21).

Let us evaluate the probability $p$. For $k=1,\dots,m$ let $d_{k}(v)$ denote
the degree of $v$ in $G_{n,k}=({\cal V}_{n,k},{\cal E}_{n,k})$ and we put
$d_{k}(v)=0$ for $v\notin{\cal V}_{n,k}$. We denote
$P_{r,k}={\bf{P}}\\{d_{k}(v_{1})=0,\dots,d_{k}(v_{r})=0\\}$.

By the independence of $G_{n,1},\dots,G_{n,m}$, we have
$p=\prod_{k\in[m]}P_{r,k}$. Furthermore, we have, by the inclusion-exclusion
principle (cf. (22)),

$S_{1,k}-S_{2,k}\leq 1-P_{r,k}\leq S_{1,k},$ (35)

where the sums $S_{1,k}$ and $S_{2,k}$ are defined as in the proof of Lemma 4,
but with $d_{1}(v_{i}),d_{1}(v_{j})$ replaced by $d_{k}(v_{i}),d_{k}(v_{j})$.
Proceeding as in the proof of (23), (24) we evaluate
$S_{1,k}=\kappa_{n,k}\frac{r}{n}$ and estimate

$S_{2,k}\leq\frac{r^{2}}{2n^{2}}\Delta_{n,k},\qquad\Delta_{n,k}:={\bf{E}}\left((X_{n,k})_{2}h(X_{n,k},Q_{n,k})\right).$

Now (35) yields the approximation

$\displaystyle
P_{r,k}=1-\frac{r}{n}\kappa_{n,k}+\theta_{n,k}\frac{r^{2}}{2n^{2}}\Delta_{n,k}=:1-a_{k}+b_{k},$
(36)

where $|\theta_{n,k}|\leq 1$. We note that

$\max_{k\in[m]}\Delta_{n,k}\leq\sum_{k\in[m]}\Delta_{n,k}=m{\bf{E}}\left((X_{n,i_{*}})_{2}h(X_{n,i_{*}},Q_{n,i_{*}})\right)=o(n^{2}),$
(37)

where the last bound follows from (26). Hence $b_{k}=o(1)$ uniformly in $k$ as
$n\to+\infty$. Similarly, (31) implies that $a_{k}=o(1)$ uniformly in $k$ as
$n\to+\infty$.

Next, using $1+t=e^{\ln(1+t)}$ and inequality $t-t^{2}\leq\ln(1+t)\leq t$
valid for $|t|\leq 0.5$ we write $P_{r,k}$ in the form

$\displaystyle
P_{r,k}=e^{\ln(1-a_{k}+b_{k})}=e^{-a_{k}+b_{k}+R},\qquad{\text{where}}\qquad
R\leq(-a_{k}+b_{k})^{2}\leq 2a_{k}^{2}+2b_{k}^{2}.$

Furthermore, denoting $R_{r,k}:=b_{k}+R$ we obtain

$P_{r,k}=e^{-a_{k}+R_{r,k}}=e^{-\frac{r}{n}\kappa_{n,k}+R_{r,k}},$

where $R_{r,k}$ satisfies

$|R_{r,k}|\leq\frac{r^{2}}{2n^{2}}\Delta_{n,k}+2\left(\frac{r}{n}\kappa_{n,k}\right)^{2}+2\left(\frac{r^{2}}{2n^{2}}\Delta_{n,k}\right)^{2}.$

Let us analyse the remainder term $R_{r,k}$. By (37), we have for large $n$
that $\max_{k\in[m]}\frac{r^{2}}{n^{2}}\Delta_{n,k}<~{}1$. Hence

$|R_{r,k}|\leq\frac{r^{2}}{n^{2}}\Delta_{n,k}+2\left(\frac{r}{n}\kappa_{n,k}\right)^{2}.$

Consequently

$\left|\sum_{k\in[m]}R_{r,k}\right|\leq\frac{r^{2}}{n^{2}}\sum_{k\in[m]}\Delta_{n,k}+2\frac{r^{2}}{n^{2}}\sum_{k\in[m]}\kappa^{2}_{n,k}=o(1).$

In the last step we used (27) and the bound
$\sum_{k\in[m]}\Delta_{n,k}=o(n^{2})$ of (37).

Finally, we evaluate the probability

$p=\prod_{k\in[m]}P_{r,k}=e^{-\frac{r}{n}\sum_{k\in[m]}\kappa_{n,k}+\sum_{k\in[m]}R_{r,k}}=e^{-r\frac{m}{n}\kappa_{n}+o(1)}.$

The respective factorial moment

${\bf{E}}(Y_{0})_{r}=(n)_{r}p=(1+o(1))e^{r\ln
n-r\frac{m}{n}\kappa_{n}+o(1)}=(1+o(1))e^{r\lambda^{*}_{m,n}+o(1)}$

converges to $e^{rc}$ since $\lambda^{*}_{m,n}\to c$ as $n\to+\infty$. ∎

## References

  * [1] Ardickas, D., Bloznelis, M. (2023): Connectivity threshold for superpositions of Bernoulli random graphs. arxiv:2306.08113v2.
  * [2] Bergman, E., Leskelä, L. (2022): Connectivity of random hypergraphs with a given hyperedge size distribution. arXiv:2207.04799.
  * [3] Bloznelis, M., Leskelä, L. (2023): Clustering and percolation on superpositions of Bernoulli random graphs. Random Structures $\&$ Algorithms, https://doi.org/10.1002/rsa.21140.
  * [4] Devroye, L., Fraiman, N. (2014): Connectivity of inhomogeneous random graphs. Random Structures Algorithms 45, 408–420.
  * [5] Erdős, P., Rényi, A. (1959): On random graphs. I. Publ. Math. Debrecen 6, 290–297.
  * [6] Frieze, A., Karoński, M. (2015): Introduction to Random Graphs. Cambridge University Press.
  * [7] Godehardt, E., Jaworski, J., Rybarczyk, K. (2007): Random intersection graphs and classification, in Advances in Data Analysis, R. Decker and H. J. Lenz, eds., Berlin, Heidelberg, Springer Berlin Heidelberg, pp. 67–74.
  * [8] Janson, S., Łuczak, T., Ruciński, A. (2000): Random Graphs, Wiley, New York.
  * [9] van der Hofstad, R. (2017): Random graphs and complex networks. Vol. 1. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge.
  * [10] Yang, J., Leskovec, J. (2012): Community-affiliation graph model for overlapping network community detection. In 2012 IEEE 12th International Conference on Data Mining, pages 1170–1175. IEEE.
  * [11] Yang, J., Leskovec, J. (2014): Structure and overlaps of ground-truth communities in networks. ACM Trans. Intell. Syst. Technol.  5(2), 1–35.