# Dynamic random intersection graph:
Dynamic local convergence and giant structure

Marta Milewska  Centrum Wiskunde & Informatica (CWI), P.O. Box 94079, 1090 GB
Amsterdam, The Netherlands  Remco van der Hofstad  Department of Mathematics
and Computer Science, Eindhoven University of Technology, 5600 MB Eindhoven,
The Netherlands  Bert Zwart  Centrum Wiskunde & Informatica (CWI), P.O. Box
94079, 1090 GB Amsterdam, The Netherlands  Department of Mathematics and
Computer Science, Eindhoven University of Technology, 5600 MB Eindhoven, The
Netherlands

###### Abstract

Random intersection graphs containing an underlying community structure are a
popular choice for modelling real-world networks. Given the group memberships,
the classical random intersection graph is obtained by connecting individuals
when they share at least one group.
We extend this approach and make the communities _dynamic_ by letting them
alternate between an active and inactive phase. We analyse the new model,
delivering results on degree distribution, local convergence, giant component,
and maximum group size, paying particular attention to the dynamic description
of these properties. We also describe the connection between our model and the
bipartite configuration model, which is of independent interest.

Keywords: Random intersection graphs, Bipartite generalised random graph,
dynamic local weak convergence, dynamic giant process;

##  1 Introduction and main results

###  1.1 Introduction

Networks are present in many areas of everyday life. We distinguish for
instance social networks, such as acquaintance networks, technological
networks, such as the Worldwide Web, or biological networks such as neural
networks (see [27] for an extensive overview). Networks can be investigated in
terms of many aspects, one of them being the existence and shape of local
communities.

Local communities are smaller structures that have, on average, more
connections than the network as a whole. They are crucial components of many
real-life networks, such as social networks or the Internet, and they
naturally give rise to high clustering (see [40, Chapters 7 and 11]) - one of
the most fiercely investigated network’s properties, that many systems seem to
share.

There are many reasons why communities appear in networks. It might be because
of a set of common features shared by a certain amount of individuals (for
example the same nationality) or some underlying geometry (for example living
in the same city). In our model, we intuitively associate communities with
social groups that people can belong to, such as families, groups of friends,
commuters on the same bus, etc. However, the model can also be relevant to
other types of networks with similar structures.

Due to their complexity, real-world networks are often modelled with the help
of random graphs. There are many ways of implementing a community structure
such as described above. A classic choice is the random intersection graph
(RIG), first introduced in [45]. The distinctive feature of intersection graph
models is a double layer. We first establish a bipartite graph, with vertices
on one side and communities on the other. After drawing edges between the two
groups, we obtain a resulting graph by connecting two vertices if and only if
they both belong to the same community. This procedure is called the one-node
projection. Throughout the years, multiple suggestions on how to generate such
bipartite graphs with group memberships appeared [13]. This includes pre-
assigning the number of group memberships to every vertex and then connecting
them to groups in a uniform manner (uniform RIG [8, 43] or generalized RIG [9,
10, 11, 14, 28], generating group membership via the bipartite configuration
model, i.e., assigning half-edges to individuals and groups and then
connecting them uniformly at random [22, 32, 33, 41], or performing
independent percolation on the complete bipartite graph (binomial RIG [26, 37,
45] or inhomogeneous RIG [12, 23]).

Our approach shares some similarities with the mentioned inhomogeneous RIG
since we also assign weight $w_{i}$ to every vertex $i$ and the probability
that vertex $i$ belongs to a certain community depends on this weight.
However, we add a novel dynamic factor by letting all communities go through
active and inactive phases. We argue that such a modification is relevant for
real-world networks since many of our regular social contacts are temporary.
For instance, we usually do not spend all our days with our colleagues, and we
only meet our closest friends a few times a week for a couple of hours. Other
examples of temporary social interactions are concerts or rides with public
transport. Note that our model is also a natural generalization of static
graphs with communities, as the scenario in which all of the groups are
present all the time is a special case.

The dynamics we implement in our model significantly differ from the well-
investigated dynamic of graphs whose size evolves in time, such as
preferential attachment models [5, 30, 44, 48]. The size of our graph is
_static_ , but the connections between individuals and communities (and hence,
in the resulting graph the connections between individuals themselves) keep
evolving. This makes the model more similar to the graphs with dynamic bond
percolation [29, 46] or evolving configuration models [3, 4].

Contribution of the paper. In this paper, we investigate degree distribution,
local convergence, and behavior of the giant connected component. A main
innovation of our work is the methodology required to give a dynamic
description of a bipartite generalized random graph. We investigate its
dynamic local convergence and in particular, we introduce the concept of a
dynamic giant component from the perspective of a uniformly chosen vertex,
looking at it as a process in time. We then show in which way it is related to
the dynamic local limit. To our best knowledge, the concept of dynamic local
limit has only been discussed in the recent paper [24] where the authors adopt
a different approach and treat a different model. We also develop an auxiliary
result on the equivalence between our model and the bipartite configuration
model described in [33], that can be of independent interest (see Appendix).
This result can be thought of as a bipartite/community version of the
equivalence between the configuration model and generalized random graph (see
[30, Theorem 7.18] and also Section 2 in this paper).

Outline of the paper. We introduce our model and all necessary assumptions in
Section 1.2. We state our main results in Section 1.3 and provide a discussion
in Section 1.4. We describe the overview of the proofs and state some
secondary results in Section 2. In Section 3 we prove the main results
presented in Section 1.3. For the conceptually straightforward proofs of the
remaining results, we refer the reader to the Appendix.

###  1.2 Model and notation

In this section, we intuitively and formally introduce the model and list some
necessary assumptions that will hold throughout the paper.

Bipartite structure. As mentioned in the introduction, there are two layers to
our model: the underlying bipartite generalized random graph that we will call
$\mathrm{BGRG}_{n}(\bm{w})$, and the resulting dynamic random intersection
graph that we will call $\mathrm{DRIG}_{n}(\bm{w})$. Let $[n]_{k}$ denote the
set of subsets of size $k$ of $[n]=\\{1,...,n\\}$. $\mathrm{BGRG}_{n}(\bm{w})$
consists of the set of vertices $[n]$ on the one hand and the set of groups
$\cup_{k\geq 2}[n]_{k}$ \- a union of all $k$-element subsets of $[n]$ \- with
$k\geq 2,k\in\mathbf{N}$ on the other. We intuitively think of them as left-
and right-vertices respectively. To differentiate degrees in the underlying
and the resulting graph, we write $d^{(l)}_{i}$ for the degree of vertex
$i\in[n]$ in $\mathrm{BGRG}_{n}(\bm{w})$ and $d^{(r)}_{a}$ for the degree of a
group $a\in\cup_{k\geq 2}[n]_{k}$ in $\mathrm{BGRG}_{n}(\bm{w})$. The
connections are then formed by making the left-vertices connect to active
right-vertices (groups).

In the following, we explain in detail how these connections are formed and
with what probabilities, and what it means for a group $a\in\cup_{k\geq
2}[n]_{k}$ to be active. The left-degrees here denote the (potential) number
of groups that vertices belong to and the right-degrees are the number of
left-vertices connected to a particular right-vertex, i.e., the group sizes.
Hence,

$\displaystyle d^{(l)}_{i}=\sum_{k=2}^{\infty}\sum_{a\in[n]_{k}:a\ni
i}\mathds{1}_{\\{a\hskip 2.84544pt\text{is ON}\\}},$ (1.1)

and, with $|a|$ denoting the size of group $a\in\cup_{k\geq 2}[n]_{k}$,

$\displaystyle d^{(r)}_{a}=|a|\cdot\mathds{1}_{\text{\\{$a$ is \rm{ON}\\}}}.$
(1.2)

Group memberships. We quantify the number of all active groups as

$\displaystyle\sum_{k=2}^{\infty}\sum_{a\in[n]_{k}}\mathds{1}_{\text{\\{$a$ is
\rm{ON}\\}}},$ (1.3)

and the number of all active groups a vertex $i\in[n]$ is a part of as

$\displaystyle\sum_{k=2}^{\infty}\sum_{a\in[n]_{k},a\ni
i}\mathds{1}_{\text{\\{$a$ is \rm{ON}\\}}}.$ (1.4)

As one can see, we conceptually deviate from the popular strategy of fixing
upfront a $p_{ia}$ \- a probability that a vertex $i$ is connected to a group
$a$. Instead, we say that every combination of $k$ vertices, with $k\in[2,n]$,
might potentially form a group and we define the probability that such a group
is active, depending on the choice of vertices in question.

Group dynamics. Every group $a\in\cup_{k\geq 2}[n]_{k}$ will alternate between
an ON and OFF state. Each group $a\in[n]_{k}$ behaves like a continuous-time
Markov process with two states, which we refer to as ON and OFF. The holding
times, i.e., the time that a group spends in each of them, are exponentially
distributed with rates

$\displaystyle\lambda^{a}_{\text{\rm{ON}}}=1\hskip 28.45274pt\text{and}\hskip
28.45274pt\lambda^{a}_{\text{\rm{OFF}}}=\frac{f(|a|)\prod_{i\in
a}w_{i}}{\ell_{n}^{|a|-1}},$ (1.5)

respectively, where $\bm{w}=(w_{i})_{i\in[n]}$ are the vertex weights,
$\ell_{n}=\sum_{i\in[n]}w_{i}$ and $|a|$ denotes the size of a group
$a\in[n]_{k}$. Naturally, $f(|a|)$ is a function of a group’s size and can be
chosen in a flexible way. Hence, the stationary distribution
$\pi=[\pi_{\text{\rm{ON}}},\pi_{\text{\rm{OFF}}}]$ of these Markov chains is
given by

$\displaystyle\pi^{a}_{\text{\rm{ON}}}=\frac{\lambda^{a}_{\text{\rm{OFF}}}}{\lambda^{a}_{\text{\rm{ON}}}+\lambda^{a}_{\text{\rm{OFF}}}}=\frac{f(|a|)\prod_{i\in
a}w_{i}}{\ell_{n}^{|a|-1}+f(|a|)\prod_{i\in a}w_{i}}\hskip
14.22636pt\text{and}\hskip
14.22636pt\pi^{a}_{\text{\rm{OFF}}}=\frac{\lambda^{a}_{\text{\rm{ON}}}}{\lambda^{a}_{\text{\rm{ON}}}+\lambda^{a}_{\text{\rm{OFF}}}}=\frac{\ell_{n}^{|a|-1}}{\ell_{n}^{|a|-1}+f(|a|)\prod_{i\in
a}w_{i}}.$ (1.6)

Assumptions on weights. We first define what the empirical distribution of the
weights is.

######  Definition 1.1 (Empirical vertex weights distribution).

We define the empirical distribution function of the vertex weights as

$\displaystyle F_{n}(x)=\frac{1}{n}\sum_{i\in[n]}\mathds{1}_{\\{w_{i}\leq
x\\}},\hskip 5.69046pt\text{for}\hskip 5.69046ptx\geq 0.$ (1.7)

$F_{n}$ can be interpreted as the distribution of the weight of a uniformly
chosen vertex. We denote the weight of such a uniformly chosen vertex $o_{n}$
in $[n]$ by $W_{n}=w_{o_{n}}$. We impose the following conditions on the
vertex weights:

######  Condition 1.2 (Regularity condition for vertex weight).

There exists a distribution function $F$ such that, as $n\to\infty$, the
following conditions hold:

  1. (a)

Weak convergence of vertex weight:

$\displaystyle W_{n}\stackrel{{\scriptstyle d}}{{\longrightarrow}}W,$ (1.8)

where $W_{n}$ and $W$ have distribution functions $F_{n}$ and $F$,
respectively. Equivalently, for any $x$ for which $x\mapsto F(x)$ is
continuous,

$\displaystyle\lim_{n\to\infty}F_{n}(x)=F(x).$ (1.9)

  2. (b)

Convergence of average vertex weight:

$\displaystyle\lim_{n\to\infty}\mathbf{E}[W_{n}]=\mathbf{E}[W],$ (1.10)

where $W_{n}$ and $W$ have distribution functions $F_{n}$ and $F$,
respectively. Further, we assume that $\mathbf{E}[W]>0$.

  3. (c)

Convergence of second moment of vertex weight:

$\displaystyle\lim_{n\to\infty}\mathbf{E}[W_{n}^{2}]=\mathbf{E}[W^{2}],$
(1.11)

######  Remark 1.3.

For the time being, we assume Condition 1.2(c), however, the results treated
in this paper are also true without it, which is very convenient for
applications. We explain how Condition 1.2(c) can be lifted in Remark B.11.

Assumptions on the function of a group’s size. We take $f(|a|)=|a|!p_{|a|}$,
where $(p_{k})_{k\geq 2}$ is the probability mass function of the group sizes.
A particularly important case is a power-law group-size distribution where
$p_{k}$ is close to $k^{-(\alpha+1)}$. We denote

$\displaystyle\mu=\sum_{k=2}^{\infty}kp_{k},$ (1.12)

and assume $\mu<\infty$. We also assume that the second moment of the group-
size distribution is finite, so that $\alpha>2$, i.e.,

$\displaystyle\mu_{(2)}=\sum_{k=2}^{\infty}k^{2}p_{k}<\infty.$ (1.13)

As explained below, these assumptions are necessary for the graph to be
sparse, that is, the average degree remains uniformly bounded.

Dynamic intersection graph. The resulting dynamic random intersection graph
$\mathrm{DRIG}_{n}(\bm{w})$ consists of the set of vertices
$[n]=\\{1,...,n\\}$. It is formed from $\mathrm{BGRG}_{n}(\bm{w})$ by drawing
an edge between two vertices $i,j\in[n]$ at time $s$ if they are in at least
one active group together at time $s$. Hence, $\mathrm{DRIG}_{n}(\bm{w})$ is a
projection of $\mathrm{BGRG}_{n}(\bm{w})$, the random multi-graph given by the
edge multiplicities $\big{(}X(i,j)\big{)}_{i,j\in[n]}$ such that

$\displaystyle
X(i,j)=\sum_{k=2}^{\infty}\sum_{a\in[n]_{k}}\mathds{1}_{\\{\text{$i$ in
$a$}\\}\cap\\{\text{$j$ in $a$}\\}}\mathds{1}_{\\{\text{$a$ is \rm{ON}}\\}}.$
(1.14)

Let $d_{i}(s)$ denote the degree of a vertex $i\in[n]$ at time $s$ in
$\mathrm{DRIG}_{n}(\bm{w})$. Then

$\displaystyle d_{i}(s)=\sum_{k=2}^{\infty}\sum_{a\in[n]_{k}:a\ni
i}(|a|-1)\mathds{1}_{\\{a\hskip 2.84544pt\text{is ON at time $s$}\\}}.$ (1.15)

Stationary vs dynamic. Due to the Markovian nature of our groups,
$\mathrm{BGRG}_{n}(\bm{w})$ and $\mathrm{DRIG}_{n}(\bm{w})$ can be examined in
two scenarios: in the long run, under the stationary distribution, and
dynamically, for every time $s\in[0,t]$ with $t$ fixed, incorporating constant
switching of the groups between the ON and OFF states. To make it clear which
situation we are referring to, we will name the graphs resulting from the
stationary distribution $\mathrm{BGRG}_{n}(\bm{w})$ and
$\mathrm{DRIG}_{n}(\bm{w})$ and the dynamic graphs by
$\big{(}\mathrm{BGRG}_{n}^{s}(\bm{w})\big{)}_{s\geq 0}$ and
$\big{(}\mathrm{DRIG}_{n}^{s}(\bm{w})\big{)}_{s\geq 0}$.

Uniformly chosen vertices. Throughout the paper we often discuss results with
respect to a uniformly chosen vertex. We denote a uniformly chosen vertex in
the bipartite graph by $V^{b}_{n}$ and in the intersection graph by $o_{n}$.
Note that this notation does not specify whether we refer to the stationary,
dynamic, or union graphs. If such an indication is needed, then we will make
it clear by stating an appropriate name of the graph, according to the
notation introduced in the previous paragraph. We also denote the degree of a
uniformly chosen vertex in $\mathrm{BGRG}_{n}(\bm{w})$ by $D^{(l)}_{n}$ and
the degree of a uniformly chosen group by $D^{(r)}_{n}$. We denote the degree
of a uniformly chosen vertex in $\mathrm{DRIG}_{n}(\bm{w})$ by $D_{n}$.

###  1.3 Main results

In this section, we state our main results. We first investigate the behavior
of our model in stationarity. We start with the description of local
convergence, i.e., the convergence of the neighborhood counts. We explain this
notion in more detail later in Section 2.2.1. We continue with the description
of the giant component. Next, we proceed to analyse the dynamic situation. We
state our results on dynamic local convergence and dynamic giant membership
process. We close by discussing the dynamics of the largest group that is ON.

####  1.3.1 Stationarity

It turns out that under the stationary distribution and given appropriate
conditions, our underlying graph - $\mathrm{BGRG}_{n}(\bm{w})$ \- is
equivalent to the bipartite configuration model, $\mathrm{BCM}_{n}(\bm{d})$,
introduced in [33] and investigated further in [32]. Hence, it is possible to
transfer the results on the local convergence and the giant component from
[33] and [32] to our model. The link between the two models and the transfer
of results are explained in detail in further sections. We now state its most
important consequences: the results on the static local limit and giant
component.

Static local limit. Similarly, as in $\mathrm{BCM}_{n}(\bm{d})$, the
neighborhood of a uniformly chosen vertex in $\mathrm{BGRG}_{n}(\bm{w})$
resembles a mixture of two branching processes, each of them corresponding to
offspring distributions of left- and right-vertices of the root. Then, the
neighborhood of a uniformly chosen vertex in $\mathrm{DRIG}_{n}(\bm{w})$
resembles a community projection (see 1.14) of this mixture. We summarise
these statements in the following theorem, the limiting objects themselves are
later explained in detail in Section 2.2.2:

######  Theorem 1.4 (Local convergence of $\mathrm{BGRG}_{n}(\bm{w})$ and
$\mathrm{DRIG}_{n}(\bm{w})$).

Consider $\mathrm{BGRG}_{n}(\bm{w})$ under Condition 1.2. As $n\to\infty$,
$(\mathrm{BGRG}_{n}(\bm{w}),V^{b}_{n})$ converges locally in probability to
$(\mathrm{BP}_{\gamma},0)$, where $(\mathrm{BP}_{\gamma},0)$ is a mixture of
two branching processes.
Consequently for $\mathrm{DRIG}_{n}(\bm{w})$ under Condition 1.2, as
$n\to\infty$, $(\mathrm{DRIG}^{\pi}_{n}(\bm{w}),o_{n})$ converges locally in
probability to $(\mathrm{CP},o)$, where (CP, o) is a random rooted graph.

We prove Theorem 1.4 in Appendix B.4.

Static giant component. Denote the giant component in
$\mathrm{DRIG}_{n}(\bm{w})$ by $\mathscr{C}_{1}$. The random variables
$\tilde{D}^{(l)}$ and $\tilde{D}^{(r)}$ are strongly connected to the
offspring distributions present in the local limit of the underlying
$\mathrm{BGRG}_{n}(\bm{w})$ and are explained in detail in Section 2.2.2.
Denote $M_{n}=\\#\\{a\in[n]_{k}:\text{$a$ is \rm{ON}}\\}$ and
$A_{k}=\\#\\{a\in[n]_{k}:\text{$a$ is \rm{ON}}\\}$. The following theorem
gives a precise condition for the existence of the giant component in
$\mathrm{DRIG}_{n}(\bm{w})$.

######  Theorem 1.5 (Giant component in $\mathrm{DRIG}_{n}(\bm{w})$).

Consider $\mathrm{DRIG}_{n}(\bm{w})$. There exists $\eta_{l}\in[0,1]$, the
smallest solution of the fixed point equation

$\displaystyle\eta_{l}=G_{\tilde{D}^{(r)}}(G_{\tilde{D}^{(l)}}(\eta_{l})),$
(1.16)

and $\xi_{l}=1-G_{D^{(l)}}(\eta_{l})\in[0,1]$ such that

$\displaystyle\frac{|\mathscr{C}_{1}|}{n}\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\xi_{l}.$
(1.17)

Furthermore, $\xi_{l}>0$ exactly when

$\displaystyle\mathbf{E}[\tilde{D}^{(l)}]\mathbf{E}[\tilde{D}^{(r)}]=\frac{\mathbf{E}[W^{2}](\mu_{(2)}-\mu)}{\mathbf{E}[W]}>1.$
(1.18)

We call the above the _supercritical case_. In this case, $\mathscr{C}_{1}$ is
unique.

We prove Theorem 1.5 in Appendix B.5.

####  1.3.2 Dynamic local convergence

We start with the description of the local limit of our graph in the dynamic
scenario. This concept is rather new in the study of the local convergence of
graphs and to our best knowledge it has not been thoroughly investigated yet
(see the discussion later on).

The concept behind dynamic local convergence explained. To examine the dynamic
behavior, we first look collectively at everything that happens during the
time interval $[0,t]$, for $t$ fixed, and then develop a method to withdraw
information on the state of the graph for every $s\in[0,t]$. This yields one
of our main results - the convergence of the dynamic intersection graph seen
as a stochastic process in time:

######  Theorem 1.6 (Dynamic local limit of $\mathrm{DRIG}_{n}^{s}(\bm{w})$).

Under Condition 1.2, the dynamic intersection graph process
$\big{(}\big{(}\mathrm{DRIG}^{s}_{n}(\bm{w}),o_{n}\big{)}\big{)}_{s\in[0,t]}$
converges in a local weak sense to
$\big{(}(\mathrm{CP}^{s},o)\big{)}_{s\in[0,t]}$, where, for every $s\in[0,t]$,
$\big{(}(\mathrm{CP}^{s},o)\big{)}_{s\in[0,t]}$ is a stochastic process of
random rooted marked graphs.

We prove Theorem 1.6 in Section 3.7.

The limiting object. Due to the one-node projection needed to obtain
$\mathrm{DRIG}_{n}^{s}(\bm{w})$, the limiting object is also rather involved
and we fully explain what it is later (see Section 2). Now we only provide an
informal description. The limit $(\mathrm{CP}^{s},o)$ depends heavily on the
limit of the marked bipartite union graph $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$,
which is a mixture of two marked branching processes: one corresponding to the
offspring distribution of the left partition and the other one to the
offspring distribution of the right partition. The marks
$\big{(}\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}}\big{)}_{a}$ encoding
activity times of the edges (details in Section 2.3.4) are preserved in the
limiting object as the limiting marks
$\big{(}t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}}\big{)}_{a}$. Because of the way the
intersection graph is constructed, the limit
$(\mathrm{CP}^{[0,t]},\big{(}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})\big{)},o)$ of
the marked union intersection graph $\mathrm{DRIG}_{n}^{[0,t]}(\bm{w})$ is
then a community projection of the limit of the marked bipartite union graph,
again preserving the edge marks. From there the limit of
$\mathrm{DRIG}_{n}^{s}(\bm{w})$ can be constructed for every $s\in[0,t]$ from
$(\mathrm{CP}^{[0,t]},\big{(}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})\big{)},o)$,
taking only the groups for which $s\in[t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}}]$.

Dynamic degree. As mentioned earlier, if we know what happens to the graph
during the time period $[0,t]$, we can extract the information on the degree
of $i\in[n]$ for every $s\in[0,t]$.

Degree in $\mathrm{DRIG}_{n}^{s}(\bm{w})$. For every $i\in[n]$,

$\displaystyle d_{i}(s)=\sum_{a\in\cup_{k\geq 2}[n]_{k}:a\ni i,\text{$a$ ON in
$[0,t]$}}(|a|-1)\mathds{1}_{\big{\\{}s\in[\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}}]\big{\\}}}.$
(1.19)

Denote the number of groups of size $k$ containing a vertex $i$ at time
$s\in[0,t]$ by $C_{k}^{s}(i)$. Since the degree distribution is a functional
of the local limit we deduce the following convergence of the degree process:

######  Corollary 1.7.

As $n\to\infty$,

$\displaystyle\big{(}D^{s}_{n}\big{)}_{s\in[0,t]}\stackrel{{\scriptstyle\text{d}}}{{\longrightarrow}}\bigg{(}\sum_{k=2}^{\infty}(k-1)C_{k}^{s}(o_{n})\bigg{)}_{s\in[0,t]}.$
(1.20)

####  1.3.3 Dynamic giant component

Denote the giant component in
$\big{(}\mathrm{DRIG}_{n}^{s}(\bm{w})\big{)}_{s\geq 0}$ at time $s$ by
$\mathscr{C}^{s}_{1}$ and the connected component of the root $o$ at time $s$
in the limiting structure $(\mathrm{CP}^{s},o)_{s\geq 0}$ (see Theorem 1.6) by
$\mathscr{C}^{s}(o)$. We examine the behavior of the process
$J_{n}(s)=\mathds{1}_{\big{\\{}o_{n}\in\mathscr{C}^{s}_{1}\big{\\}}}$. From
the behavior of the static giant (see Theorem 1.5), for all $s$,

$\displaystyle
J_{n}(s)\stackrel{{\scriptstyle\text{d}}}{{\longrightarrow}}\mathds{1}_{\big{\\{}|\mathscr{C}^{s}(o)|=\infty\big{\\}}}.$
(1.21)

However, we want to investigate the behavior of $J_{n}(s)$ as a stochastic
process in time. It turns out that this question can be linked to local
neighborhoods in our graph and answered thanks to local convergence:

######  Theorem 1.8 (Dynamic giant component).

As $n\to\infty$,

$\displaystyle\Big{(}\mathds{1}_{\big{\\{}o_{n}\in\mathscr{C}^{s}_{1}\big{\\}}}\Big{)}_{s\in[0,t]}\stackrel{{\scriptstyle\text{d}}}{{\longrightarrow}}\Big{(}\mathds{1}_{\big{\\{}|\mathscr{C}^{s}(o)|=\infty\big{\\}}}\Big{)}_{s\in[0,t]}$
(1.22)

in the Skorokhod $J_{1}$ topology.

We provide the proof of Theorem 1.8 in Section 3.8.

####  1.3.4 Maximal group size

Define

$\displaystyle K_{\max}^{\\{0\\}}=\max_{a\in\cup_{k\geq 2}[n]_{k}:\text{$a$ is
\rm{ON} at time $0$}}|a|,$ (1.23)

and $K^{(0,t]}_{\max}$ is the maximum group size in the set of groups that
switch ON in the time interval $(0,t]$, respectively. We define

$\displaystyle
K^{[0,t]}_{\max}=\max\\{K^{\\{0\\}}_{\max},K^{(0,t]}_{\max}\\},$ (1.24)

with $K^{\\{0\\}}_{\max}$ and $K^{(0,t]}_{\max}$ independent, as a consequence
of the fact that different groups arrive independently. We further define
$K^{(s,t]}_{\max}$ for every $s\in[0,t)$ as the maximum group size in the set
of groups that switched ON in time interval $(s,t]$. Hence, for every
$s\in[0,t)$,

$\displaystyle K^{(0,t]}_{\max}=\max\\{K^{(0,s]}_{\max},K^{(s,t]}_{\max}\\},$
(1.25)

and $K^{(0,s]}_{\max},K^{(s,t]}_{\max}$ are independent. Now define
$\big{(}\kappa^{(0,t]}_{\max}\big{)}_{t\geq 0}$ such that, for every $t\geq
0$,

$\displaystyle\mathbf{P}(\kappa^{(0,t]}_{\max}\leq
k)=e^{-tk^{-\alpha}\mathbf{E}[W]},$ (1.26)

and the evolution of the whole process is such that for every partition
$\\{0,s_{1},s_{2},...,s_{t-1},s_{t}\\}$ of the time interval $[0,s_{t}]$ it
holds

$\displaystyle\kappa^{(0,s_{t}]}_{\max}=\max\\{\kappa^{(0,s_{1}]}_{\max},\kappa^{(s_{1},s_{2}]}_{\max},...,\kappa^{(s_{t-1},s_{t}]}_{\max}\\},$
(1.27)

where, for non-overlapping time intervals $(s_{1},t_{1}]$ and $(s_{2},t_{2}]$,
$\kappa_{\max}^{(s_{1},t_{1}]}$, $\kappa_{\max}^{(s_{2},t_{2}]}$ are
independent. We show that the largest group size converges in distribution as
a stochastic process to a limiting process
$\big{(}\kappa^{(0,t]}_{\max}\big{)}_{t\geq 0}$ inheriting a similar
structure:

######  Theorem 1.9 (Maximum group size).

If the group-size distribution is a power law, i.e., $\sum_{l\geq
k}p_{l}\propto k^{-\alpha}$, with $\alpha>3$, then, as $n\to\infty$,

$\displaystyle\bigg{(}\frac{K^{[0,t]}_{\max}}{n^{1/\alpha}}\bigg{)}_{t\geq
0}\stackrel{{\scriptstyle\text{d}}}{{\longrightarrow}}\bigg{(}\kappa^{(0,t]}_{\max}\bigg{)}_{t\geq
0},$ (1.28)

in the Skorokhod $J_{1}$ topology.

We prove Theorem 1.9 in Section 3.9.

######  Remark 1.10.

Note that in the case of the maximal group present in the union graph, we do
not run into the same problem of creating connections that do not exist as was
the case with degrees of vertices. Hence, the largest group ever active in the
union graph is at the same time the largest group ever active in the dynamic
graph.

######  Remark 1.11.

Note that one could also investigate a slightly different dynamic process,
namely $\big{(}n^{-1/\alpha}K^{s}_{\max}\big{)}_{s\in[0,t]}$, where
$K^{s}_{\max}$ is the maximal group that is ON at time $s$. We conjecture that
a proof of convergence of such a process should be closely related to the
proof of Theorem 1.9 that we present in the next section. However, the
dynamics of $\big{(}n^{-1/\alpha}K^{s}_{\max}\big{)}_{s\in[0,t]}$ are
significantly more involved: when the so far largest group switches OFF, then
the largest ON group becomes the previously second largest one. Hence, to
analyse such a process it would be necessary to keep track of the large ON
groups as a process of infinite length.

###  1.4 Discussion

In this section, we comment on the advantages and limitations of our model and
results and present open problems.

Dynamic factor. An undeniably interesting feature of our model is the
introduction of temporary connections between vertices. Intuitively, it makes
sense that a dynamic model should describe real-world networks more
accurately. It would undoubtedly be interesting to investigate the
truthfulness of this statement by comparing our model with other popular
models through simulations. The dynamic we introduce is also interesting
purely from the perspective of random graph theory. The framework for the
dynamic local limit we provide is an alternative to the one in [24]. However,
the limit itself is a rather complex construction and its interpretation is
not very straightforward.

Other work on bipartite graphs with group structure. To derive results on the
static $\mathrm{BGRG}_{n}(\bm{w})$, which later on lead to results on
$\mathrm{DRIG}_{n}(\bm{w})$, we heavily rely on [32] and [33]. The authors of
these papers derive statements on local convergence and giant component in the
bipartite configuration model with communities, which can be transferred to
our model by showing an appropriate relation between the bipartite
configuration model conditioned on simplicity and the bipartite generalized
random graph conditioned on its degree sequence. We provide more details in
Section 2.

Other work on dynamic local convergence. To our best knowledge, the only paper
that treats dynamic local convergence is a recent pre-print by Dort and Jacob
[24]. The approach of the authors is different from ours: we are taking a
classic approach by treating the dynamic graph as a stochastic process on the
space of rooted graphs with a traditional local metric, whereas they define a
metric that incorporates time. Contrary to [24], we also consider the dynamic
giant component.

Group sizes. One of the beneficial features of our model is the existence of
big groups (see Theorem 1.9). Such groups are an important factor in real-
world social networks, which are highly clustered. We set the model in a way
that allows for flexibility in the choice of the group-size distribution, as
one can consider various $(p_{k})_{k\geq 2}$, not necessarily heavy-tailed
ones. We are aware that many of our proof techniques require $p_{k}$ to have a
finite second moment, which might not seem ideal. However, the finite second
moment is needed to obtain a sparse graph, i.e., a graph with a bounded
average degree.

Choice of parameters and alternative interpretation. The model is quite
flexible in the choice of parameters, as we do not determine the weight
variables or the group-size distribution and only keep some general
assumptions about them. However, the model does not allow for the one-to-one
transfer of degree distribution from real-world data, as opposed to the
bipartite configuration model with communities (from [33]). Moreover, at first
glance, choosing the stationary distribution as in (1.6) might seem un-
intuitive. However, there is a nice intuitive description of this model. Our
model is very closely connected to a Poisson process dynamic: take a
situation, where we form a new group according to a Poisson process with
intensity $\ell_{n}$. When a group is formed, we choose its size $k\geq 2$
according to some size distribution $p_{k}$. Lastly, from all the groups of
the chosen size, we pick the one to appear proportionally to products of
weights, i.e., with probability

$\displaystyle\frac{\prod_{i\in a}w_{i}}{\sum_{b\in[n]_{k}}\prod_{j\in
b}w_{j}},$

for all $a\in[n]_{k}$. It can be shown that our model and the model we just
described yield the same degree sequences and hence, produce very similar
graphs. However, our model conditioned on its degree sequence has the
advantage of being uniform over all bipartite graphs with such degree
sequence, which proves to be a very useful feature.

Equivalence with the bipartite configuration model. An interesting byproduct
of our paper is a relationship between the underlying bipartite structure in
our model and the bipartite configuration model. More mathematical details
regarding this equivalence are stated in the next section and in the Appendix.
This raises the question of whether the dynamic versions of these models are
also equivalent.

Relationship to $\mathrm{GRG}$. Note that by taking $p_{2}=1$ we can obtain
the classic generalized random graph $\mathrm{GRG}_{n}(\bm{w})$ from our
model. Hence, our results also apply to the generalized random graph.

##  2 Overview of the proofs

In this section, we provide the ideas behind the proofs of our main results.
We include shorter and straightforward proofs. We also state the auxiliary
results that we think might be of independent interest.

###  2.1 Bipartite generalized random graphs and configuration models are
equivalent

Two of the most popular approaches to modelling real-world networks are the
generalized random graph and the configuration model. The generalized random
graph denoted $\mathrm{GRG}$, was introduced in 2006 by Britton, Deijfen and
Martin-Löf (see [18]). In this model, each vertex $i\in[n]$ is given a weight
$w_{i}$ and the probability that there is an edge between vertex $i$ and
vertex $j$ is equal to

$\displaystyle p_{ij}=\frac{w_{i}w_{j}}{\ell_{n}+w_{i}w_{j}},$

with $\ell_{n}=\sum_{i\in[n]}w_{i}$, just like in our model. Naturally,
assigning edge probabilities according to weights can also be done in a
different way. For a more general version see [16], for related models see the
Chung-Lu model (for instance [19]) or the Norros-Reitu model [42]. For an
overview of results on the classic generalized random graph see [30, Chapter
6].

In contrast, in the configuration model (CM), the degrees of the vertices are
fixed upfront. The concept of the configuration model originates in the early
works of Bollobás (see [15]). Since then, various configuration models have
been proposed but in its most standard formulation, the configuration model
refers to a uniform pairing of half-edges, which can be represented in a form
of a graph by assigning an appropriately determined number of half-edges to
every node and then connecting them uniformly to form edges. A graph obtained
in this way is uniform over the space of all graphs with a given degree
sequence [40]. Such a model was popularised and intensively studied by Molloy
and Reed (see [38], [39]). For an overview of results for the classic
configuration model see [30, Chapter 7]. Again, there are many modifications
of the classic configuration model such as the configuration model with
households [47].

Despite their differences, it turns out that under certain conditions the
generalized random graph and the configuration model are equivalent (see [30,
Theorem 7.18]). Also note that the static $\mathrm{BGRG}_{n}(\bm{w})$
introduced by us can be perceived as a bipartite, multi-dimensional version of
the generalized random graph (hence the name $\mathrm{BGRG}_{n}(\bm{w})$),
where also certain communities are present. It turns out that this model is
accordingly equivalent to a bipartite configuration model with communities
$\mathrm{BCM}_{n}(\bm{d})$, introduced and studied in [33] and [32], under the
same conditions that guarantee equivalence of the classic generalized random
graph and the configuration model. More precisely, it turns out that, under
such conditions, both $\mathrm{BGRG}_{n}(\bm{w})$ and
$\mathrm{BCM}_{n}(\bm{d})$ from [33] are uniform random graphs, and hence have
the same distribution.

This relationship is one of the most important building blocks in the proof of
our results. Thanks to it, we can transfer results proved in [32, 33] to our
graph. As these auxiliary statements can be of independent interest, we
present them below:

######  Theorem 2.1 ($\mathrm{BGRG}_{n}(\bm{w})$ conditioned on degree
sequence is uniform).

$\mathrm{BGRG}_{n}(\bm{w})$ conditioned on
$\\{d^{(l)}_{i}(X)=d^{(l)}_{i}\hskip 2.84544pt\forall
i\in[n],d^{(r)}_{a}(X)=d^{(r)}_{a}\hskip 2.84544pt\forall a\in\cup_{k\geq
2}[n]_{k}\\}$, is uniform over all bipartite graphs with degree sequence
$(\bm{d}^{(l)},\bm{d}^{(r)})=\big{(}(d^{(l)}_{i})_{i\in[n]},(d^{(r)}_{a})_{a\in\cup_{k\geq
2}[n]_{k}}\big{)}$.

An equivalent result follows for the $\mathrm{BCM}_{n}(\bm{d})$ conditioned on
simplicity:

######  Theorem 2.2 ($\mathrm{BCM}_{n}(\bm{d})$ conditioned on being simple is
uniform).

For any degree sequence
$\bm{d}=(\bm{d}^{(l)},\bm{d}^{(r)})=\big{(}(d^{(l)}_{i})_{i\in[n]},(d^{(r)}_{a})_{a\in\cup_{k\geq
2}[n]_{k}}\big{)}$, and conditionally on the event {$\mathrm{BCM}_{n}(\bm{d})$
is a simple graph}, $\mathrm{BCM}_{n}(\bm{d})$ is a uniform bipartite graph
with degree sequence $d$.

As a natural consequence, $\mathrm{BGRG}_{n}(\bm{w})$ conditioned on its
degree and $\mathrm{BCM}_{n}(\bm{d})$ conditioned on simplicity have the same
distribution. We properly state this result in the following theorem, however,
we first note that under some extra assumptions, an even stronger connection
between the two graphs can be shown. As this connection plays a crucial role
in many of our proofs, we include it in the theorem. The mentioned assumptions
are as follows:

######  Condition 2.3 (Regularity conditions).

The random variables $D^{(l)}_{n}$ and $D^{(r)}_{n}$ have distribution
function $F^{(l)}_{n}$ and $F^{(r)}_{n}$ respectively, given by

$\displaystyle
F^{(l)}_{n}(x)=\frac{1}{n}\sum_{i\in[n]}\mathds{1}_{\\{d^{(l)}_{i}\leq
x\\}}\hskip 14.22636pt\text{and}\hskip
14.22636ptF^{(r)}_{n}(x)=\frac{1}{n}\sum_{a\in[n]_{k}}\mathds{1}_{\\{d^{(r)}_{a}\leq
x\\}}.$ (2.1)

We impose the following assumptions on these distribution functions:

  1. a)

There exist random variables $D^{(l)}$, $D^{(r)}$ such that, as $n\to\infty$
and for every $l\geq 0$, $k\geq 2$,

$\displaystyle\mathbf{P}(D^{(l)}_{n}=l\mid
G_{n})\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\mathbf{P}(D^{(l)}=l)\hskip
5.69046pt\text{and}\hskip 5.69046pt\mathbf{P}(D^{(r)}_{n}=k\mid
G_{n})\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\mathbf{P}(D^{(r)}=k),$
(2.2)

where $(\cdot\mid G_{n})$ denotes conditioning with respect to a realisation
of a random graph. Moreover, $\mathbf{E}[D^{(l)}]<\infty$,
$\mathbf{E}[D^{(r)}]<\infty$ and, as $n\to\infty$,

$\displaystyle\mathbf{E}[D^{(l)}_{n}\mid
G_{n}]\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\mathbf{E}[D^{(l)}]\hskip
5.69046pt\text{and}\hskip 5.69046pt\mathbf{E}[D^{(r)}_{n}\mid
G_{n}]\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\mathbf{E}[D^{(r)}].$
(2.3)

Additionally, we put a constraint on the second moment of degree random
variables:

  2. b)

$\mathbf{E}\big{[}\big{(}D^{(l)}\big{)}^{2}\big{]},\mathbf{E}\big{[}\big{(}D^{(r)}\big{)}^{2}\big{]}<\infty$
and, as $n\to\infty$,

$\displaystyle\mathbf{E}\big{[}\big{(}D^{(l)}_{n}\big{)}^{2}\mid
G_{n}\big{]}\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\mathbf{E}\big{[}\big{(}D^{(l)}\big{)}^{2}\big{]}\hskip
5.69046pt\text{and}\hskip
5.69046pt\mathbf{E}\big{[}\big{(}D^{(r)}_{n}\big{)}^{2}\mid
G_{n}\big{]}\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\mathbf{E}\big{[}\big{(}D^{(r)}\big{)}^{2}\big{]}.$
(2.4)

With all the above in mind, the following result relates
$\mathrm{BGRG}_{n}(\bm{w})$ and $\mathrm{BCM}_{n}(\bm{d})$:

######  Theorem 2.4 (Relation between $\mathrm{BGRG}_{n}(\bm{w})$ and
$\mathrm{BCM}_{n}(\bm{d})$).

Let $d^{(l)}_{i}$ be the degree of left-vertex $i$ in
$\mathrm{BGRG}_{n}(\bm{w})$, $d^{(r)}_{a}$ the degree of a group $a$ in
$\mathrm{BGRG}_{n}(\bm{w})$, and
$D=(\bm{d}^{(l)},\bm{d}^{(r)})=\big{(}(d^{(l)}_{i})_{i\in[n]},(d^{(r)}_{a})_{a\in[m]}\big{)}$.
Then,

$\displaystyle\mathbf{P}(\mathrm{BGRG}_{n}(\bm{w})=G\mid\bm{D}=\bm{d})=\mathbf{P}(\mathrm{BCM}_{n}(\bm{d})=G\mid\mathrm{BCM}_{n}(\bm{d})\hskip
2.84544pt\text{simple}).$ (2.5)

Let $\mathcal{E}_{n}$ be a subset of multi-graphs such that
$\mathbf{P}(\mathrm{BCM}_{n}(\bm{d})\in\mathcal{E}_{n})\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}1$
when $D$ satisfies Condition 2.3. Assume that the degree sequence $D$ of
$\mathrm{BGRG}_{n}(\bm{w})$ satisfies Condition 2.3. Then also
$\mathbf{P}(\mathrm{BGRG}_{n}(\bm{w})\in\mathcal{E}_{n})\longrightarrow 1$.

The above theorem is a bipartite equivalent of the relationship between the
classic generalised random graph $\mathrm{GRG}_{n}(\bm{w})$ and the
configuration model $\mathrm{CM}_{n}(\bm{d})$ (see for instance [30, Theorem
7.18]). Hence, the idea behind the proof is also similar. We first show that
$\mathrm{BGRG}_{n}(\bm{w})$ conditioned on the degree sequence is uniform.
After that, we establish that $\mathrm{BCM}_{n}(\bm{d})$ conditioned on
simplicity is also uniform. Finally, we use both statements to prove the
desired result. The proofs of the auxiliary steps as well as of the final
Theorem 2.4 can be found in Appendix A.

###  2.2 Static local limit and giant component

In this section, we investigate the local convergence of our graph under the
stationary distribution. We introduce and describe in more detail the limiting
local objects of the underlying $\mathrm{BGRG}_{n}(\bm{w})$ and of the
resulting $\mathrm{DRIG}_{n}(\bm{w})$. Further on, we examine the proportion
of vertices that are in the giant connected component. We state a phase
transition in the size of the largest component in terms of the model
parameters and give the explicit criterion under which a unique giant
component exists.

####  2.2.1 Brief overview of local convergence

Before stating our results we briefly define local convergence in probability
and local marked convergence in probability. Local convergence was introduced
in [6] and a few years later, independently, in [1]. It describes the
resemblance of the neighborhood of a vertex chosen uniformly at random to a
certain limiting graph. To formalise this resemblance we introduce the notion
of neighborhood and isomorphism on graphs:

######  Definition 2.5 (Rooted graph, rooted isomorphism and
$r$-neighborhood).

  1. (i)

We call a pair $(G,o)$ a rooted graph if $G$ is a locally finite, connected
graph and $o$ is a distinguished vertex of $G$. We denote the space of rooted
graphs by $\mathcal{G}_{\star}$.

  2. (ii)

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

  3. (iii)

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

The notion of graph isomorphism enables defining a metric on the space of
rooted graphs:

######  Definition 2.6.

(Metric on rooted graphs) Let $(G_{1},o_{1})$ and $(G_{2},o_{2})$ be two
rooted connected graphs, and write $B_{r}(G_{i},o_{i})$ for the neighborhood
of vertex $o_{i}\in V(G_{i})$. Let

$\displaystyle R^{\star}=\sup\\{r:B_{r}(G_{1},o_{1})\simeq
B_{r}(G_{2},o_{2})\\},$ (2.6)

and define

$\displaystyle\text{d}_{\mathcal{G}_{\star}}\big{(}(G_{1},o_{1}),(G_{2},o_{2})\big{)}=\frac{1}{R^{\star}+1}.$
(2.7)

The space $\mathcal{G}_{\star}$ of rooted graphs under the metric
$\text{d}_{\mathcal{G}_{\star}}$ is separable and thus Polish (for proof see
[31, Appendix A]), which will later prove very useful in the case of dynamic
local convergence. We now define local convergence:

######  Definition 2.7.

(Local convergence in probability) Let
$G_{n}=(\mathcal{V}_{n},\mathcal{E}_{n})$ with size
$|\mathcal{V}_{n}|\stackrel{{\scriptstyle\mathbf{P}}}{{\to}}\infty$ be a
sequence of random graphs, and let $o_{n}\mid G_{n}\sim
Unif[\mathcal{V}(G_{n})]$. Let $(G,o)$ denote a random element (with arbitrary
distribution) of the set of rooted graphs, which we call a random rooted
graph. We say that $(G_{n},o_{n})$ converges locally in probability to
$(G,o)$, if for any fixed rooted graph $(H_{\star},o^{\prime})$ and
$r\in\mathbf{N}$,

$\displaystyle\mathbf{P}(B_{r}(G_{n},o_{n})\simeq(H_{\star},o^{\prime})\mid
G_{n}):=$
$\displaystyle\frac{1}{|G_{n}|}\sum_{i\in\mathcal{V}(G_{n})}\mathds{1}_{\\{B_{r}(G_{n},i)\simeq(H_{\star},o^{\prime})\\}}$
(2.8)
$\displaystyle\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\hskip
2.84544pt$ $\displaystyle\mathbf{P}(B_{r}(G,o)\simeq(H_{\star},o^{\prime})).$

We say that $(G,o)$ is the local limit in probability of $(G_{n})_{n\geq 1}$.

Thus, intuitively, local convergence is defined as the convergence of the
proportion of vertices whose neighborhoods have some specified structure. For
further reading about local convergence, see for instance [31, Chapter 2-5]
and the references therein for examples of local limits of various graph
models. Since we will actually need a more general setting of marked graphs
and their convergence, we now briefly present some of the theory behind it.

Marked graphs and marked local convergence. Marks allow us to include
additional information about vertices and/or edges such as directions,
colours, and so on. In particular, we use marks to indicate the belonging of a
vertex to a certain partition (of left- or right-vertices) in the underlying
$\mathrm{BGRG}_{n}(\bm{w})$ and to denote the on and off times of edges in the
dynamic graphs, based on the group activity.

######  Definition 2.8 (Marked graphs).

Let $\mathcal{G}$ denote the set of all locally finite (multi)graphs on a
countable (finite or countably infinite) vertex set. A marked (multi)graph is
a (multi)graph $G=(V(G),E(G))$, $G\in\mathcal{G}$, together with a set
$\mathcal{M}(G)$ of marks taking values in a complete separable metric space
$\Xi$, called the mark space. $\mathcal{M}$ maps from $V(G)$ and $E(G)$ to
$\Xi$. Images in $\Xi$ are called marks. Each edge is given two marks, one
associated with (‘at’) each of its endpoints, in particular, for $v\in V(G)$,
$\Xi(v)\in\mathcal{M}$, and for $e\in E(G)$, $\Xi(e)\in\mathcal{M}^{2}$.
Moreover, $\mathcal{M}$ contains the special symbol $\varnothing$ which is to
be interpreted as “no mark”. We denote the set of graphs with marks from the
mark set $\mathcal{M}$ by $\mathcal{G}(\mathcal{M})$.

We generalize Definitions 2.5 and 2.6 to the setting of marked rooted graphs:

######  Definition 2.9 (Rooted marked graph and $r$-neighborhood.).

  1. (i)

We choose a vertex $o$ in a marked graph $(G,\mathcal{M}(G))$ to be
distinguished as the root. We denote the rooted marked graph by
$(G,\mathcal{M}(G),o)$.
We also denote the set of rooted marked graphs by
$\mathcal{G}_{\star}(\mathcal{M})$. We call a random element of
$\mathcal{G}_{\star}(\mathcal{M})$ (with an arbitrary joint distribution) a
random rooted marked graph.

  2. (ii)

The (closed) ball $B_{r}(G,\mathcal{M}(G),o)$ can be defined analogously to
the unmarked graph ball (Definition 2.5 (iii)), by restricting the mark
function to the subgraph as well.

######  Definition 2.10 (Metric on marked rooted graphs).

Let $\text{d}_{\Xi}$ be a metric on the space of marks $\Xi$. Let

$\displaystyle R^{\star}=\sup\\{$ $\displaystyle r:B_{r}(G_{1},o_{1})\simeq
B_{r}(G_{2},o_{2}),\hskip 5.69046pt\text{and there exists $\phi$ such that}$
(2.9) $\displaystyle\text{d}_{\Xi}((m_{1}(i),m_{2}(\phi(i)))\leq 1/r\hskip
4.26773pt\forall i\in V(B_{r}(G_{1},o_{1})),$
$\displaystyle\text{d}_{\Xi}(m_{1}(i,j),m_{2}(\phi(i,j)))\leq 1/r\hskip
4.26773pt\forall\\{i,j\\}\in E(B_{r}(G_{1},o_{1}))\\},$

with $\phi:V(B_{r}(G_{1},o_{1}))\longrightarrow V(B_{r}(G_{2},o_{2}))$ running
over all isomorphisms between $B_{r}(G_{1},o_{1})$ and $B_{r}(G_{2},o_{2})$,
that map $o_{1}$ to $o_{2}$. Then define

$\displaystyle\text{d}_{\mathcal{G}_{\star}}\big{(}(G_{1},\mathcal{M}(G_{1}),o_{1}),(G_{2},\mathcal{M}(G_{2}),o_{2})\big{)}=\frac{1}{R^{\star}+1}.$
(2.10)

This turns $\mathcal{G}_{\star}(\mathcal{M})$ into a Polish space, i.e., a
complete, separable metric space.

Definition 2.10 puts a metric structure on marked rooted graphs. With this
metric topology in hand, we can simply adapt all convergence statements to
this setting. Hence, we generalize Definition 2.8 as follows:

######  Definition 2.11 (Local convergence in probability of marked graphs
with continuous marks).

Let $(G_{n},\mathcal{M}(G_{n}))_{n\in\mathbf{N}}$,
$(G_{n},\mathcal{M}(G_{n}))\in\mathcal{G}_{\star}(\mathcal{M})$ be a sequence
of (finite) random marked graphs such that
$|G_{n}|\stackrel{{\scriptstyle\mathbf{P}}}{{\to}}\infty$ and let $o_{n}\sim
Unif[\mathcal{V}(G_{n})]$. Let
$\mathbf{P}\big{(}\cdot\mid(G_{n},\mathcal{M}(G_{n}))\big{)}$ denote
conditional probability with respect to the marked graph ($o_{n}$ is the free
variable). We say that $(G_{n},\mathcal{M}(G_{n}),o_{n})_{n\in\mathbf{N}}$
converges locally in probability to a (possibly) random element
$(G,\mathcal{M}(G),o)\in\mathcal{G}_{\star}(\mathcal{M})$ if for any fixed
rooted graph $(H_{\star},\mathcal{M}(H_{\star}),o^{\prime})$ and
$r\in\mathbf{N}$, as $n\to\infty$,

$\displaystyle\mathbf{P}$
$\displaystyle\bigg{(}\text{d}_{\mathcal{G}_{\star}}\bigg{(}(G_{n},\mathcal{M}(G_{n}),o_{n}),(H_{\star},\mathcal{M}(H_{\star}),o^{\prime})\bigg{)}\leq\frac{1}{r+1}\mid(G_{n},\mathcal{M}(G_{n}))\bigg{)}$
(2.11) $\displaystyle:=$
$\displaystyle\frac{1}{|G_{n}|}\sum_{i\in\mathcal{V}(G_{n})}\mathds{1}_{\big{\\{}\text{d}_{\mathcal{G}_{\star}}\big{(}(G_{n},\mathcal{M}(G_{n}),i),(H_{\star},\mathcal{M}(H_{\star}),o^{\prime})\big{)}\leq\frac{1}{r+1}\big{\\}}}\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\hskip
2.84544pt\mathbf{P}\bigg{(}\text{d}_{\mathcal{G}_{\star}}\bigg{(}(G,\mathcal{M}(G),o),(H_{\star},\mathcal{M}(H_{\star}),o^{\prime})\bigg{)}\leq\frac{1}{r+1}\bigg{)}.$

We say that $(G,\mathcal{M}(G),o)$ is the local limit in probability of
$(G_{n},\mathcal{M}(G_{n}))_{n\geq 1}$.

####  2.2.2 Static local convergence of the dynamic random intersection graph

To prove static local convergence of $\mathrm{DRIG}_{n}(\bm{w})$ we first look
at static local convergence of $\mathrm{BGRG}_{n}(\bm{w})$. The authors of
[33] and [32] derive results on the local convergence and the giant component
of $\mathrm{BCM}_{n}(\bm{d})$ under the assumption that
$\mathrm{BCM}_{n}(\bm{d})$ fulfils Condition 2.3(i). From the previous section
we know that under Condition 2.3(i)-(ii), results applying to
$\mathrm{BCM}_{n}(\bm{d})$ also apply to $\mathrm{BGRG}_{n}(\bm{w})$. Hence,
it suffices to show that our model under stationarity and assuming Condition
1.2 fulfils Condition 2.3(i) and argue that Condition 2.3(ii) is in fact not
necessary to obtain local convergence and the giant component in
$\mathrm{BGRG}_{n}(\bm{w})$.
Due to the one-node projection present in [33] and in our model, the
statements about the resulting intersection graphs, i.e, of $\mathrm{RIGC}$
and $\mathrm{DRIG}_{n}(\bm{w})$, automatically follow from results shown for
$\mathrm{BCM}_{n}(\bm{d})$ and $\mathrm{BGRG}_{n}(\bm{w})$ respectively. Since
verification of the regularity conditions is quite elementary and the
remaining results follow directly from [33] and [32], the proofs of all static
results can be found in Appendix B. Here we only describe the limiting object
and state the theorems.

The static limiting object $(\mathrm{BP}_{\gamma},0)$. We start by introducing
$(\mathrm{BP}_{\gamma},0)$, the local limit in probability of
$\mathrm{BGRG}_{n}(\bm{w})$. Naturally, as we are dealing with two types of
vertices - the left and the right ones - a typical neighborhood in this graph
will be different depending on the type of the root. However, it is not
possible to determine whether a uniformly chosen root was a left- or a right-
vertex just on the basis of its neighborhood. Hence, we introduce marks to
keep track of different types of vertices. Let $\mathcal{M}_{b}=\\{l,r\\}$ be
the set of marks. We mark left-vertices as $l$ and right-vertices as $r$.
Formally,

$\displaystyle\mathcal{E}^{b}_{n}=\begin{cases}l\hskip
5.69046pt\text{if}\hskip 5.69046pti\in[n],\\\ r\hskip 5.69046pt\text{if}\hskip
5.69046pta\in[n]_{k\geq 2}.\end{cases}$ (2.12)

Now we introduce the limiting object
$(\mathrm{BP}_{\gamma},\mathcal{E}_{\gamma},0)$, equipped with the mark
function $\mathcal{E}^{b}_{n}$, while $(\mathrm{BP}_{\gamma},0)$ is then
obtained by ignoring the mark function. Define a mixing variable ${\gamma}$ as

$\displaystyle\mathbf{P}({\gamma}=l)=\frac{1}{1+\frac{M_{n}}{n}}\hskip
8.5359pt\text{and}\hskip
8.5359pt\mathbf{P}({\gamma}=r)=\frac{\frac{M_{n}}{n}}{1+\frac{M_{n}}{n}}.$
(2.13)

Then, $(\mathrm{BP}_{\gamma},\mathcal{E}_{\gamma},0)$ is a mixture of two
marked ordered BP-trees, $(\mathrm{BP}_{l},\mathcal{E}_{l},0)$ and
$(\mathrm{BP}_{r},\mathcal{E}_{r},0)$:

$\displaystyle(\mathrm{BP}_{\gamma},\mathcal{E}_{\gamma},0)\stackrel{{\scriptstyle
d}}{{=}}\mathds{1}_{\\{\gamma=l\\}}(\mathrm{BP}_{l},\mathcal{E}_{l},0)+\mathds{1}_{\\{\gamma=r\\}}(\mathrm{BP}_{r},\mathcal{E}_{r},0),$
(2.14)

where $(\mathrm{BP}_{l},\mathcal{E}_{l},0)$ describes the neighborhood of a
left-vertex and $(\mathrm{BP}_{r},\mathcal{E}_{r},0)$ of a right one. Hence,

$\displaystyle(\mathrm{BGRG}_{n}(\bm{w}),\mathcal{E}_{l},V_{n}^{(l)})\stackrel{{\scriptstyle\mathbf{P}}}{{\to}}(\mathrm{BP}_{l},\mathcal{E}_{l},0)\hskip
8.5359pt\text{and}\hskip
8.5359pt(\mathrm{BGRG}_{n}(\bm{w}),\mathcal{E}_{r},V_{n}^{(r)})\stackrel{{\scriptstyle\mathbf{P}}}{{\to}}(\mathrm{BP}_{r},\mathcal{E}_{r},0),$
(2.15)

where $V_{n}^{(l)}$ and $V_{n}^{(r)}$ denote vertices chosen uniformly from
the set of all left- and right-vertices respectively. The mixing variable
$\gamma$ can thus be re-interpreted as the random mark of the root.

Before we proceed, we need to introduce the size-biased version of a random
variable:

######  Definition 2.12.

For an $\mathbb{N}$-valued random variable $X$ with $\mathbf{E}[X]<\infty$, we
define its size-biased distribution $X^{\star}$ and the shift variable
$\tilde{X}$ by their probability mass functions, for all $k\in\mathbb{N}$,

$\displaystyle\mathbf{P}(X^{\star}=k)=\frac{k\mathbf{P}(X=k)}{\mathbf{E}[X]}\hskip
28.45274pt\text{and}\hskip
28.45274pt\mathbf{P}(\tilde{X}=k)=\mathbf{P}(X^{\star}-1=k).$ (2.16)

Now we can continue with the description of the random ordered marked tree
$(\mathrm{BP}_{l},\mathcal{E}_{l},0)$ itself. We consider a discrete-time
branching process where the offspring of any two individuals are independent.
We then give the individuals in even and odd generations marks $l$ and $r$,
respectively. Generation 0 contains the root alone and the root’s offspring
distribution is $D^{(l)}$ (the limit of the degree of a uniformly chosen left-
vertex, see Condition 2.3). In consecutive generations, the offspring
distribution of individuals marked with $l$ will be $\tilde{D}^{(l)}$ and of
individuals marked with $r$ will be $\tilde{D}^{(r)}$.
$(\mathrm{BP}_{r},\mathcal{E}_{r},0)$ is defined analogously with reversed
roles of $l$ and $r$.

Static local limit of $\mathrm{DRIG}_{n}(\bm{w})$. Having specified the local
limit of the underlying $\mathrm{BGRG}_{n}(\bm{w})$, we proceed to the limit
of the resulting graph $\mathrm{DRIG}_{n}(\bm{w})$.

The static limiting object $(\mathrm{CP},o)$. The limit that we denote by
$(\mathrm{CP},o)$ is a random rooted graph and the “community projection” (see
(1.14)) of $(\mathrm{BP}_{\gamma},\mathcal{E}_{\gamma},0)$ in the same way
that $\mathrm{DRIG}_{n}(\bm{w})$ is the “community projection” of the
underlying $\mathrm{BGRG}_{n}(\bm{w})$: it extracts only vertices marked as
$l$ and builds links between these which were previously connected to the same
vertex with mark $r$. Let us accentuate that even though the final limit is
not a tree, it relies on the tree-like structure of the underlying
$\mathrm{BGRG}_{n}(\bm{w})$. This constructs the local limit $(\mathrm{CP},o)$
of $\mathrm{DRIG}_{n}(\bm{w})$.

####  2.2.3 Degree distribution

The average degree in $\mathrm{DRIG}_{n}(\bm{w})$ is asymptotically a sum of
rescaled Poisson variables whose rates depend on the limiting weight variable
$W$ (see Condition 1.2):

######  Corollary 2.13 (Convergence of degree of a random vertex in
$\mathrm{DRIG}_{n}(\bm{w})$).

Let $\bm{w}$ satisfy Condition 1.2. Then,

$\displaystyle D_{n}\stackrel{{\scriptstyle d}}{{\longrightarrow}}\sum_{l\geq
2}(l-1)X_{l},$ (2.17)

where $X_{l}$ is a mixed-Poisson variable with mixing distribution $lp_{l}W$.

Corollary 2.13 is a direct consequence of the static local convergence and we
can actually prove a stronger result about the degree distribution in the
static graph. Define

$\displaystyle
Q_{k}^{(n)}=\frac{1}{n}\sum_{i\in[n]}\mathds{1}_{\\{d_{i}=k\\}}.$ (2.18)

Then, the following theorem shows that $\big{(}Q_{k}^{(n)}\big{)}_{k\geq 0}$
converges in total variation distance:

######  Theorem 2.14 (Degree sequence in $\mathrm{DRIG}_{n}(\bm{w})$).

For every $\varepsilon>0$,

$\displaystyle\mathbf{P}\Big{(}\sum_{k=0}^{\infty}|Q^{(n)}_{k}-q_{k}|>\varepsilon\Big{)}\longrightarrow
0,$ (2.19)

where $q_{k}=\mathbf{P}\big{(}\sum_{l\geq 2}(l-1)X_{l}=k\big{)}$ with
$\big{(}X_{l}\big{)}_{l\geq 2}$ \- independent mixed-Poisson variables with
mixing distribution $lp_{l}W$, i.e., such that

$\displaystyle\mathbf{P}(X_{l}=k)=\mathbf{E}\Big{[}e^{-lp_{l}W}\frac{(lp_{l}W)^{k}}{k!}\Big{]}.$
(2.20)

Theorem 2.14 is proven in Appendix B.3.

We next investigate the sparsity of our model by investigating the average
degree:

######  Theorem 2.15 (Convergence of average degree in
$\mathrm{DRIG}_{n}(\bm{w})$).

As $n\to\infty$,

$\displaystyle\mathbf{E}[D_{n}\mid
G_{n}]\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}(\mu_{(2)}-\mu)\mathbf{E}[W].$
(2.21)

The proof of this result (see Appendix B.3) shows why Conditions 1.12 and 1.13
are necessary for the sparsity of our model.

####  2.2.4 Static giant component

Since real-world networks tend to be highly connected and a large fraction of
individuals very often lies in a single connected component, it is useful to
study the behavior of this component. We denote the cluster or connected
component of a vertex $i\in[n]$ in the graph $G=([n],E)$ by $\mathscr{C}(i)$.
We denote the graph distance in $G$, i.e., the minimal number of edges in a
path linking $i$ and $j$, by $\text{dist}_{G}(i,j)$. We define

######  Definition 2.16 (Giant connected component).

$\displaystyle\mathscr{C}(i)=\\{j\in[n]:\text{dist}_{G}(i,j)<\infty\\}.$
(2.22)

Let $\mathscr{C}_{1}$ denote the largest connected component, i.e., let
$\mathscr{C}_{1}$ satisfy

$\displaystyle|\mathscr{C}_{1}|=\max_{i\in[n]}|\mathscr{C}(i)|,$ (2.23)

where $|\mathscr{C}(i)|$ denotes the number of vertices in $\mathscr{C}(i)$
and we break ties arbitrarily.

Of course, it can happen that there are two or more maximal clusters in a
graph. For that reason, the uniqueness of the giant is often investigated.
Another popular question is the existence of a component containing a linear
proportion of vertices - the so-called giant component problem. It was first
studied by Erdős and Rényi ([25]) and has since been investigated on multiple
other models (for instance the Chung-Lu model [20, 21], or configuration model
[17, 35, 38, 39]).

Due to the structure of intersection graphs, the giant component exists when
it exists in the underlying bipartite graphs. Hence, the results on the giant
component in $\mathrm{DRIG}_{n}(\bm{w})$ follow from the results on the giant
component in $\mathrm{BGRG}_{n}(\bm{w})$. Similarly, as in the case of local
convergence, thanks to the link between our model under stationarity and the
$\mathrm{BCM}_{n}(\bm{d})$ and the fact that regularity conditions we impose
on the weights variables imply regularity conditions of degrees in
$\mathrm{BGRG}_{n}(\bm{w})$, we are allowed to transfer the statements on the
giant component for $\mathrm{BCM}_{n}(\bm{d})$ and $\mathrm{RIGC}$, proven in
[32]. We again state the results and prove them in more detail in Appendix
B.5).

Static giant component in the $\mathrm{BGRG}_{n}(\bm{w})$. We start with the
bipartite graph. Denote the giant component in $\mathrm{BGRG}_{n}(\bm{w})$ by
$\mathscr{C}_{1,b}$. Its giant is studied in the next theorem:

######  Theorem 2.17 (Giant component in $\mathrm{BGRG}_{n}(\bm{w})$).

Under the supercriticality condition
$\mathbf{E}[\tilde{D}^{(l)}]\mathbf{E}[\tilde{D}^{(r)}]>1$, as $n\to\infty$,

$\displaystyle\frac{|\mathscr{C}_{1,b}\cap\mathcal{V}^{(l)}|}{n}\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\xi_{l},$
(2.24)

where $\xi_{l}=1-G_{D^{(l)}}(\eta_{l})\in[0,1]$ and $\eta_{l}\in[0,1]$ is the
smallest solution of the fixed point equation

$\displaystyle\eta_{l}=G_{\tilde{D}^{(r)}}(G_{\tilde{D}^{(l)}}(\eta_{l})).$
(2.25)

We prove Theorem 2.17 in Appendix B.5.

Static giant component in the $\mathrm{DRIG}_{n}(\bm{w})$. The statement on
the giant in $\mathrm{DRIG}_{n}(\bm{w})$ follows immediately. See Theorem 1.5.

######  Remark 2.18.

The fact that the fixed point equation (1.16) shows up here can be intuitively
explained as follows: For a vertex to be in giant component its local
neighborhood has to survive. In the results on the local convergence we showed
that local neighborhoods are locally tree-like and are well approximated by
branching processes with offspring distributions $\tilde{D}^{(l)}$ and
$\tilde{D}^{(r)}$. Hence, the fixed point equation follows from the general
theory of branching processes and their extinction probability.

###  2.3 The union graph

Having shown multiple results for the static situation, we proceed to the
dynamic part. In Section 1.3 we explained that in order to describe the graph
dynamically for every time point $s$, it is helpful to first look collectively
at everything that happens during a time interval $[0,t]$, for $t$ fixed. For
that reason, we create a union graph $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ (and
accordingly, a resulting $\mathrm{DRIG}_{n}^{[0,t]}(\bm{w})$) which includes
any group that was ON at time $t=0$, but also all the groups that ever
switched on within the time interval $(0,t]$.

Group probabilities in $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$. Note that

$\displaystyle\mathbf{P}$ $\displaystyle(\text{$a$ ON within
$[0,t]$})=\pi^{a}_{\text{\rm{ON}}}+\pi^{a}_{\text{\rm{OFF}}}\mathbf{P}(\text{$a$
switches ON within $(0,t]$})$ (2.26)
$\displaystyle=\pi^{a}_{\text{\rm{ON}}}+\pi^{a}_{\text{\rm{OFF}}}\big{(}1-\mathbf{P}(\text{$a$
never ON within
$(0,t]$})\big{)}=\pi^{a}_{\text{\rm{ON}}}+\pi^{a}_{\text{\rm{OFF}}}\big{(}1-e^{-t\lambda^{a}_{\text{\rm{OFF}}}}\big{)}$
$\displaystyle=\frac{f(|a|)\prod_{i\in
a}w_{i}}{\ell_{n}^{|a|-1}+f(|a|)\prod_{i\in
a}w_{i}}+\frac{\ell_{n}^{|a|-1}}{\ell_{n}^{|a|-1}+f(|a|)\prod_{i\in
a}w_{i}}\big{(}1-e^{-t\frac{f(|a|)\prod_{i\in
a}w_{i}}{\ell_{n}^{|a|-1}}}\big{)}\leq\pi^{a}_{\text{\rm{ON}}}(1+t),$

using the fact that $1-e^{-x}\leq x$. Hence, we see that even though the group
probability in the union graph is somewhat complicated, it can be bounded from
above by $\pi^{a}_{\text{\rm{ON}}}(1+t)$, which is similar to the group
probability in the static graph. Thus, instead of deriving convergence results
directly for $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$, it is more convenient to
couple it with a graph that is closer to the static graph.

####  2.3.1 The rescaled bipartite graph $\mathrm{BGRG}_{n}^{(t)}(\bm{w})$

Remember that since $\mathrm{BGRG}_{n}(\bm{w})$ is uniform and fulfils the
required degree regularity conditions, we can relate it to the
$\mathrm{BCM}_{n}(\bm{d})$ model from [32] and [33] and hence deduce its local
convergence. It is not difficult to see that a graph with group ON probability
$\mathbf{P}(\text{$a$ is \rm{ON}})=\pi^{a}_{\text{\rm{ON}}}(1+t)$ would also
satisfy equivalent regularity conditions. However, a graph with
$\mathbf{P}(\text{$a$ is
\rm{ON}})=\pi^{a}_{\text{\rm{ON}}}(1+t),\mathbf{P}(\text{$a$ is
OFF})=1-\pi^{a}_{\text{\rm{ON}}}(1+t)$ will not _exactly_ be uniform (which is
easy to see after analysing the proofs of Proposition A.1 and Theorem 2.1 in
Appendix A) ). Therefore, we define a graph with group probability also
closely related to $\pi^{a}_{\text{\rm{ON}}}(1+t)$, but with a more convenient
structure:

Definition of $\mathrm{BGRG}_{n}^{(t)}(\bm{w})$. We introduce
$\mathrm{BGRG}_{n}^{(t)}(\bm{w})$, a graph following the same dynamic as the
static $\mathrm{BGRG}_{n}(\bm{w})$ but with slightly modified group
probabilities: we fix the holding times to be exponentially distributed with
rates

$\displaystyle\lambda^{a}_{\text{\rm{ON}}}=1\hskip 28.45274pt\text{and}\hskip
28.45274pt\lambda^{a}_{\text{\rm{OFF}}}=\frac{(1+t)f(|a|)\prod_{i\in
a}w_{i}}{\ell_{n}^{|a|-1}}.$ (2.27)

Hence, the new stationary distribution
$\pi^{(t)}=[\pi^{(t)}_{\text{\rm{ON}}},\pi^{(t)}_{\text{\rm{OFF}}}]$ is given
by

$\displaystyle\pi^{a,(t)}_{\text{\rm{ON}}}=\frac{(1+t)f(|a|)\prod_{i\in
a}w_{i}}{\ell^{|a|-1}+(1+t)f(|a|)\prod_{i\in a}w_{i}}\hskip
28.45274pt\text{and}\hskip
28.45274pt\pi^{a,(t)}_{\text{\rm{OFF}}}=\frac{\ell_{n}^{|a|-1}}{\ell_{n}^{|a|-1}+(1+t)f(|a|)\prod_{i\in
a}w_{i}},$ (2.28)

for every $a\in[n]_{k}$. We again impose Condition 1.2 on the weights
$\bm{w}=(w_{i})_{i\in[n]}$ and assume finite first and second moment of the
group-size distribution $p_{|a|}$, taking $f(|a|)=|a|!p_{|a|}$ (see (1.12) and
(1.13)). It turns out (see Remark B.14) that $\mathrm{BGRG}_{n}^{(t)}(\bm{w})$
conditioned on its degree sequence is uniform and that its degree sequences
fulfil the same regularity conditions as the degree sequences of
$\mathrm{BGRG}_{n}(\bm{w})$. The limiting variables of left- and right-degrees
are also analogous to the limiting degree variables in
$\mathrm{BGRG}_{n}(\bm{w})$, with Poisson parameters rescaled by a factor
$t+1$ (for an explicit statement of the regularity conditions see Remark
B.14). Hence, $\mathrm{BGRG}_{n}^{(t)}(\bm{w})$ is just like
$\mathrm{BGRG}_{n}(\bm{w})$ with slightly bigger group probabilities and thus,
it asymptotically behaves in the same way. To draw the same conclusion about
the union graph $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ it then suffices to show
it is asymptotically equivalent to $\mathrm{BGRG}_{n}^{(t)}(\bm{w})$, which we
explain further in the next section.

####  2.3.2 Asymptotic equivalence of multi-graphs

In this section, we briefly introduce the theory of asymptotic equivalence of
graph sequences. In particular, we extend the condition determining when two
inhomogeneous random graphs are asymptotically equivalent to the case of
random multi-graphs. We start by introducing the notion of asymptotic
equivalence for general random variables. We say that
$(\mathcal{X},\mathcal{F})$ is a measurable space when $\mathcal{X}$ is the
state space (the space of all possible outcomes) and $\mathcal{F}$ the set of
all possible events. We are particularly interested in finite measurable
spaces, in which case $\mathcal{X}$ is a finite set and $\mathcal{F}$ can be
taken to be the set of all subsets of $\mathcal{X}$.

######  Definition 2.19 (Asymptotic equivalence of sequences of random
variables).

Let $(\mathcal{X}_{n},\mathcal{F}_{n})$ be a sequence of measurable spaces.
Let $\mathbf{P}_{n}$ and $\mathbf{Q}_{n}$ be two probability measures on
$(\mathcal{X}_{n},\mathcal{F}_{n})$. We say that the sequences
$\big{(}\mathbf{P}_{n}\big{)}_{n\geq 1}$ and
$\big{(}\mathbf{Q}_{n}\big{)}_{n\geq 1}$ are asymptotically equivalent if, for
every sequence $\mathcal{E}_{n}\in\mathcal{F}_{n}$ of events,
$\lim_{n\to\infty}\mathbf{P}_{n}(\mathcal{E}_{n})-\mathbf{Q}_{n}(\mathcal{E}_{n})=0$.
Thus, $\big{(}\mathbf{P}_{n}\big{)}_{n\geq 1}$ and
$\big{(}\mathbf{Q}_{n}\big{)}_{n\geq 1}$ are asymptotically equivalent when
they have asymptotically equal probabilities.

In the following theorem, we give a criterion guaranteeing that two bipartite
multigraph sequences are asymptotically equivalent. The section follows from
results by [34]. We denote $(p_{a})_{a\in[n]_{k}}$ for the group probabilities
in some bipartite graph $\mathrm{BRG}_{n}(\bm{p})$ for which the probability
that a group $a$ is present equals $p_{a}$ and all groups exist independently
of each other.

######  Theorem 2.20 (Asymptotic equivalence of bipartite multi-graphs).

Let $\mathrm{BRG}_{n}(\bm{p})$ and $\mathrm{BRG}_{n}(\bm{q})$ be two random
graphs with group probabilities $\bm{p}=(p_{a})_{a\in[n]_{k\geq 2}}$ and
$\bm{q}=(q_{a})_{a\in[n]_{k\geq 2}}$ respectively. If there exists
$\hat{\varepsilon}>0$ such that $\max_{a\in\cup_{k\geq 2}[n]_{k}}q_{a}\leq
1-\hat{\varepsilon}$, then $\mathrm{BRG}_{n}(\bm{p})$ and
$\mathrm{BRG}_{n}(\bm{q})$ are asymptotically equivalent if

$\displaystyle\lim_{n\to\infty}\sum_{a\in\cup_{k\geq
2}[n]_{k}}\frac{(p_{a}-q_{a})^{2}}{q_{a}}=0.$ (2.29)

######  Remark 2.21.

If additionally there exists $\varepsilon>0$ such that $\max_{a\in\cup_{k\geq
2}[n]_{k}}p_{a}\leq 1-\varepsilon$, $\mathrm{BRG}_{n}(\bm{p})$ and
$\mathrm{BRG}_{n}(\bm{q})$ are asymptotically equivalent if and only if

$\displaystyle\lim_{n\to\infty}\sum_{a\in\cup_{k\geq
2}[n]_{k}}\frac{(p_{a}-q_{a})^{2}}{p_{a}\wedge q_{a}}=0.$ (2.30)

In particular, $\mathrm{BRG}_{n}(\bm{p})$ and $\mathrm{BRG}_{n}(\bm{q})$ are
asymptotically equivalent when they can be coupled in such a way that
$\mathbf{P}(\mathrm{BRG}_{n}(\bm{p})\neq\mathrm{BRG}_{n}(\bm{q}))=o(1)$.
Indeed, there is a strong relationship between the asymptotic equivalence and
coupling, which becomes obvious after the proof. We prove Theorem 2.20 in
Section 3.1.

Having explained what is meant by asymptotic equivalence, we state our main
equivalence result:

######  Theorem 2.22 (Asymptotic equivalence of
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ and $\mathrm{BGRG}_{n}^{(t)}(\bm{w})$).

Under Condition 1.2, the random graphs $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ and
$\mathrm{BGRG}_{n}^{(t)}(\bm{w})$ are asymptotically equivalent.

We prove Theorem 2.22 in Section 3.2. Thanks to the equivalence, all results
that we derive for $\mathrm{BGRG}_{n}^{(t)}(\bm{w})$ automatically hold for
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$.

####  2.3.3 Local limit of union graphs

We now state the results on the local convergence of the union graph, starting
with the bipartite one:

Local limit of $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$. Following the appropriate
statement for the rescaled graph $\mathrm{BGRG}_{n}^{(t)}(\bm{w})$, we
conclude that the bipartite union graph behaves very regularly and fulfils the
equivalent of Condition 2.3 (i). Moreover, the limiting variables of left- and
right-degrees in $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$, denoted further on as
$\tilde{D}^{(l),[0,t]}$ and $\tilde{D}^{(r),[0,t]}$ respectively, are just the
limiting variables of left- and right-degrees in $\mathrm{BGRG}_{n}(\bm{w})$
with Poisson parameters and proportion of groups of size $k$ rescaled by a
factor $t+1$. Hence, the union graph asymptotically behaves in the same way as
the stationary graph with accordingly larger edge probabilities.

The limiting object $(\mathrm{BP}_{\gamma}^{[0,t]},o)$. The local limit of
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ is again a mixture of two branching
processes corresponding to two types of vertices and everything is analogous
to the limit of $\mathrm{BGRG}_{n}(\bm{w})$, with $D^{(l),[0,t]}$ and
$D^{(r),[0,t]}$ taking the place of $D^{(l)}$ and $D^{(r)}$ as the offspring
distribution of the root, $\tilde{D}^{(l),[0,t]}$ replacing $\tilde{D}^{(l)}$
as the offspring distribution of the rest of the $l-$vertices and
$\tilde{D}^{(r),[0,t]}$ taking the place of $\tilde{D}^{(r)}$ as the offspring
distribution of the rest of the $r-$vertices.

Local limit of $\mathrm{DRIG}_{n}^{[0,t]}(\bm{w})$. The local limit
$(\mathrm{CP}^{[0,t]},o)$ of $\mathrm{DRIG}_{n}^{[0,t]}(\bm{w})$ can be
constructed from the local limit of $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ via
the appropriate community projection in exactly the same way as the local
limit of $\mathrm{DRIG}_{n}(\bm{w})$ was constructed via the community
projection from the local limit of $\mathrm{BGRG}_{n}(\bm{w})$ (see the
previous section):

######  Theorem 2.23 (Local limit of $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ and
$\mathrm{DRIG}_{n}^{[0,t]}(\bm{w})$).

Assume that Condition 1.2 holds. Then
$\big{(}\mathrm{BGRG}_{n}^{[0,t]}(\bm{w}),V_{n}^{b}\big{)}$ converges locally
in probability to $(\mathrm{BP}_{\gamma}^{[0,t]},o)$, where
$(\mathrm{BP}_{\gamma}^{[0,t]},o)$ is described above. Also
$\big{(}\mathrm{DRIG}_{n}^{[0,t]}(\bm{w}),o_{n}\big{)}$ converges locally in
probability to $(\mathrm{CP}^{[0,t]},o)$, where $(\mathrm{CP}^{[0,t]},o)$ is
described above.

We prove Theorem 2.23 in Section 3.3. From this analysis we also obtain
results on the degrees $D_{n}^{[0,t]}$ and its expectation as in Corollary
2.13 & Theorem 2.14. We refrain from stating those.

####  2.3.4 Marked union graph

Edge marks. We remark that the union graph is already dynamic, as it takes
dynamically appearing groups into account. However, it does not equal the
actual dynamic graph, as it does not take into account whether certain groups
were actually active at the same time. Therefore it might show connections
that were actually never made at any time in $[0,t]$. Yet, it enables tracking
the actual interactions between vertices. For this purpose, we add marks along
the edges of $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ indicating the switch on and
switch off times within $[0,t]$. These times are determined by the activity of
the groups responsible for the creation of these edges. We first mark the
groups (right-vertices): write $\sigma^{a}_{\rm{ON}}$ to denote the exact time
that a group $a$ switches on within $[0,t]$ and $\sigma^{a}_{\rm{OFF}}$ to
denote the first time it switches off in $(0,t]$. Hence, the new mark-set is
$\mathcal{M}_{d}=\\{l,r,[0,\infty)\times(0,\infty)\\}$. We then transfer the
marks to the edges, i.e., every edge in $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$
copies the marks of the right-vertex it is adjacent to.

The above marks are also well-behaved. The marks of group $a$ present in the
union graph are independent for different $a$ and they converge in
distribution with respect to the probability measure of the union graph to
some limiting marks $(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})$:

######  Lemma 2.24 (Convergence of the law of the edge marks.).

Let $F^{\textrm{ON,OFF}}_{n|t}$ denote the joint law of
$\big{(}\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}}\big{)}$ for
$a\in\cup_{k\geq 2}[n]_{k}$, conditioned on the fact that such
$a\in\cup_{k\geq 2}[n]_{k}$ is ON during $[0,t]$, i.e.,

$\displaystyle F^{\rm{ON,OFF}}_{n|t}(s_{1},s_{2})=\mathbf{P}$
$\displaystyle(\sigma_{\rm{ON}}^{a}\leq s_{1},\sigma_{\rm{OFF}}^{a}\leq
s_{2}|\text{{ON} at some point in $[0,t]$}),$ (2.31)

where $s_{1}\in[0,t]$ and $s_{2}\geq s_{1}$. Then, as $n\to\infty$,

$\displaystyle F^{\rm{ON,OFF}}_{n|t}(s_{1},s_{2})\longrightarrow
F^{\rm{ON,OFF}}_{t}(s_{1},s_{2}),$ (2.32)

with

$\displaystyle
F^{\rm{ON,OFF}}_{t}(s_{1},s_{2})=\frac{1-e^{-s_{2}+s_{1}}+s_{1}}{1+t}.$

Consequently,

$\displaystyle\big{(}\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}}\big{)}\stackrel{{\scriptstyle\text{d}}}{{\longrightarrow}}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}}),$
(2.33)

where $(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})$ has joint cumulative distribution
function $F^{\rm{ON,OFF}}_{t}$.

We prove Lemma 2.24 in Section 3.

The limit of the marked union graph. Lemma 2.24 is crucial in showing the
dynamic local convergence. Thanks to the facts that edge marks are
independent, as all the groups switch on and off independently of each other,
and that they converge in distribution to limiting marks
$(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})$ (as shown in Lemma 2.24) we know that
they converge jointly for all groups and all $s\in[0,t]$. Hence, the marked
bipartite union graph will converge to the marked limit of
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$, which will imply that also the marked
intersection union graph converges:

######  Theorem 2.25 (Local limit of marked
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ and $\mathrm{DRIG}_{n}^{[0,t]}(\bm{w})$).

$\big{(}\mathrm{BGRG}_{n}^{[0,t]}(\bm{w}),\big{(}(\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}})\big{)}_{a\in[M_{n}^{[0,t]}]},V_{n}^{b}\big{)}$
converges locally in probability to
$(\mathrm{BP}_{\gamma}^{[0,t]},\big{(}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})\big{)},o)$,
where
$(\mathrm{BP}_{\gamma}^{[0,t]},\big{(}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})\big{)},o)$
is a marked version of $(\mathrm{BP}_{\gamma}^{[0,t]},o)$. It follows that
$\big{(}\mathrm{DRIG}^{[0,t]}_{n}(\bm{w}),\big{(}(\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}})\big{)}_{a\in[M_{n}^{[0,t]}]},o_{n}\big{)}$
converges locally in probability to
$(\mathrm{CP}^{[0,t]},\big{(}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})\big{)},o)$,
where
$(\mathrm{CP}^{[0,t]},\big{(}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})\big{)},o)$ is
a marked version of $(\mathrm{CP}^{[0,t]},o)$.

We prove Theorem 2.25 in Section 3.5.

###  2.4 Dynamic local convergence

Switching pace. Note that we defined $\sigma^{a}_{\rm{ON}}$ and
$\sigma^{a}_{\rm{OFF}}$ as first switch-on and switch-off times within $[0,t]$
and we did not comment on the possibility that some groups might switch
$\rm{ON}$ again during this period of time. We address this issue by arguing
that it is unlikely to encounter such a group in a neighborhood of a uniformly
chosen vertex, which is the subject of the following lemma:

######  Lemma 2.26 (Existence of groups that switch on more than once in the
union graph).

Denote the neighbourhood of a uniformly chosen vertex in
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ by $B_{r}^{[0,t]}(V_{n}^{(l)})$. As
$n\to\infty$,

$\displaystyle\mathbf{P}\big{(}\exists a\in
B_{r}^{[0,t]}(V_{n}^{(l)}):\text{$a$ \rm{ON} twice in
$[0,t]$}\big{)}\big{)}\longrightarrow 0.$ (2.34)

We prove Lemma 2.26 in Section 3.6.
Lemma 2.26 implies that groups that switch on more than once in the union
graph do not contribute significantly to the structure of a neighborhood of a
uniformly chosen vertex. Hence, the union graph neglecting these groups is a
good approximation of the actual situation and it can be used to construct the
dynamic graph. We sum up this statement in the following corollary:

######  Corollary 2.27.

Denote the neighborhood of a uniformly chosen vertex in
$\mathrm{BGRG}_{n}^{s}(\bm{w})$ by $B^{s}_{r}(V^{(l)}_{n})$ and the
neighborhood of a uniformly chosen vertex in
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ restricted to groups that switch $\rm{ON}$
only once in $[0,t]$ and are present at time $s$ by
$\tilde{B}^{s,[0,t]}_{r}(V^{(l)}_{n})$. As $n\to\infty$, for every finite
$r>0$ and every $s\in[0,t]$, the event

$\displaystyle\big{\\{}B^{s}_{r}(V^{(l)}_{n})=\tilde{B}^{s,[0,t]}_{r}(V^{(l)}_{n})\big{\\}}$
(2.35)

holds with high probability.

We refrain from formally proving Corollary 2.27 and instead provide a short
justification here: the fact that $\tilde{B}^{s,[0,t]}_{r}(V^{(l)}_{n})$ is
contained in $B^{s}_{r}(V^{(l)}_{n})$ follows immediately. The other direction
follows directly from Lemma 2.26.

Thus, for every $s\in[0,t]$, $\mathrm{BGRG}_{n}^{s}(\bm{w})$ is a subgraph of
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ containing only these groups that are
active at time $s$, i.e., the groups $a$ with
$(\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}})$ such that
$s\in[\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}}]$.
$\mathrm{DRIG}_{n}^{s}(\bm{w})$ is then a community projection (see (1.14)) of
such a $\mathrm{BGRG}_{n}^{s}(\bm{w})$. Hence, the convergence of the union
graph and joint convergence of edge marks, guaranteed by the independence of
the marks and their convergence in distribution, yield convergence of finite-
dimensional distributions of the dynamic graph $\mathrm{BGRG}_{n}^{s}(\bm{w})$
for every $s\in[0,t]$. Thanks to that, we can describe local limits of
$\big{(}\mathrm{BGRG}_{n}^{s}(\bm{w})\big{)}_{s\in[0,t]}$ and consecutively of
$\big{(}\mathrm{DRIG}_{n}^{s}(\bm{w})\big{)}_{s\in[0,t]}$.

When looking at $\big{(}\mathrm{BGRG}_{n}^{s}(\bm{w})\big{)}_{s\in[0,t]}$ as a
process in time, we choose a random root $o_{n}$ _only_ once and then we
investigate its evolution in time. Since such a process encounters jumps with
respect to the local metric, convergence of finite-dimensional distributions
is not sufficient to deduce the convergence of the entire process. However, if
we treat $\big{(}\mathrm{BGRG}_{n}^{s}(\bm{w})\big{)}_{s\in[0,t]}$ for every
$s\in[0,t]$ as a function from the compact space of $[0,t]$ into the Polish
space of rooted graphs with the $\text{d}_{\mathcal{G}_{\star}}$ metric, it
suffices to add a suitable tightness criterion to deduce the dynamic
convergence of the process in time (see [36, Chapter 16]). Details are given
in the proof of Theorem 1.6 in Section 3.7.

###  2.5 Dynamic giant component

We want to show that the process
$J_{n}(s)=\mathds{1}_{\big{\\{}o_{n}\in\mathscr{C}^{s}_{1}\big{\\}}}$
converges for all $s\in[0,t]$ to another appropriate indicator process. Since
both of these processes encounter jumps, we need to use the Skorokhod $J_{1}$
topology in order to obtain the desired convergence. The Skorokhod $J_{1}$
topology on $D[0,t]$ \- the space of càdlàg functions on $[0,t]$ \- is given
by the metric $d^{0}$ (see [7, Eq. 12.16]), which takes care of the time
deformation present in processes with jumps. For more explanation, see a well-
known characterization of convergence in $D[0,t]$ (see [7]).

The most important step in our proofs of conditions from Lemma C.1 is
localization of the giant, i.e., noticing that the sequence of processes
$\big{(}J_{n}(s)\big{)}_{s\in[0,t]}$ is close in distribution to the sequence
of processes $\big{(}J^{(r)}_{n}(s)\big{)}_{s\in[0,t]}$, with

$\displaystyle J^{(r)}_{n}(s)=\mathds{1}_{\big{\\{}\partial
B^{G_{n}^{s}}_{r}(o_{n})\neq\varnothing\big{\\}}},$ (2.36)

where $\partial B^{G_{n}^{s}}_{r}(o_{n})$ denotes the set of vertices at
distance $r$ from the root in
$\big{(}\mathrm{BGRG}_{n}^{s}(\bm{w})\big{)}_{s\geq 0}$ at time $s$. Indeed,
for two distinct time points $s_{1},s_{2}\in[0,t]$,

$\displaystyle\mathbf{P}(J_{n}(s_{1})=J_{n}(s_{2})=1)$
$\displaystyle=\mathbf{P}(J^{(r)}_{n}(s_{1})=J^{(r)}_{n}(s_{2})=1)$ (2.37)
$\displaystyle+\mathbf{P}(J_{n}(s_{1})=J_{n}(s_{2})=1)-\mathbf{P}(J^{(r)}_{n}(s_{1})=J^{(r)}_{n}(s_{2})=1).$

Note that

$\displaystyle\big{|}$
$\displaystyle\mathbf{P}(J_{n}(s_{1})=J_{n}(s_{2})=1)-\mathbf{P}(J^{(r)}_{n}(s_{1})=J^{(r)}_{n}(s_{2})=1)\big{|}\leq\mathbf{P}(J_{n}(s_{1})=J_{n}(s_{2})=1,\neg\big{(}J^{(r)}_{n}(s_{1})=J^{(r)}_{n}(s_{2})=1\big{)})$
$\displaystyle=\mathbf{P}(J_{n}(s_{1})=J_{n}(s_{2})=1,J^{(r)}_{n}(s_{1})\neq
1\hskip 5.69046pt\text{OR}\hskip
5.69046ptJ_{n}(s_{1})=J_{n}(s_{2})=1,J^{(r)}_{n}(s_{2})\neq 1)\leq
2\mathbf{P}\big{(}J^{(r)}_{n}(s_{1})\neq J_{n}(s_{1})\big{)},$

where the last step follows from stationarity. Taking $n\to\infty$, thanks to
the static local limit and our result on the static giant component (see
Theorem 2.17), i.e., the fact for any $s$:

$\displaystyle\frac{|\mathscr{C}^{s}_{1}|}{n}\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}\mu\big{(}|\mathscr{C}^{s}(o)|=\infty\big{)},$
(2.38)

we obtain

$\displaystyle\lim_{n\to\infty}\mathbf{P}\big{(}J^{(r)}_{n}(s_{1})\neq
J_{n}(s_{1})\big{)}=\mathbf{P}\bigg{(}\mathds{1}_{\big{\\{}\partial
B^{G^{s}}_{r}(o)\neq\varnothing\big{\\}}}\neq\mathds{1}_{\big{\\{}|\mathscr{C}^{s}(o)|=\infty\big{\\}}}\bigg{)},$
(2.39)

which after taking additionally $r\to\infty$ yields

$\displaystyle\lim_{r\to\infty}\limsup_{n\to\infty}\big{|}$
$\displaystyle\mathbf{P}(J_{n}(s_{1})=J_{n}(s_{2})=1)-\mathbf{P}(J^{(r)}_{n}(s_{1})=J^{(r)}_{n}(s_{2})=1)\big{|}=0.$

Thus,

$\displaystyle\lim_{n\to\infty}\mathbf{P}(J_{n}(s_{1})=J_{n}(s_{2})=1)=\lim_{r\to\infty}\lim_{n\to\infty}\mathbf{P}(J^{(r)}_{n}(s_{1})=J^{(r)}_{n}(s_{2})=1).$

Thanks to this link, we can deduce the convergence of the dynamic giant
process from the dynamic local weak convergence (see Theorem 1.6), which
states that, as $n\to\infty$,

$\displaystyle\Big{(}J^{(r)}_{n}(s)\Big{)}_{s\in[0,t]}\stackrel{{\scriptstyle\text{d}}}{{\longrightarrow}}\Big{(}\mathcal{J}^{(r)}(s)\Big{)}_{s\in[0,t]}.$
(2.40)

In the proof of Theorem 1.8 we show how to extend the above argument to all
finite-dimensional distributions. As a result, the convergence of all finite-
dimensional distributions derived via localization paired with the tightness
of the process will guarantee convergence of
$\big{(}J_{n}(s)\big{)}_{s\in[0,t]}$. We remark that this technique is not
restricted to our model and it can be applied to any other dynamic graph for
which (2.38) and (2.40) hold.

###  2.6 Dynamic largest group

We investigate the behavior of the process
$\big{(}n^{-1/\alpha}K^{[0,t]}_{\max}\big{)}_{t\geq 0}$, where
$K^{[0,t]}_{\max}$ is the maximum group size in the time interval $[0,t]$. It
is an increasing process describing the largest group observed by a certain
time point $t$. As such, the process in question also encounters jumps, just
like the previous dynamic processes we have described, and hence, to deduce
its convergence, we once again use the theory of convergence in Skorokhod
topology.

##  3 Proofs of the main results

Here we provide proofs of all mentioned results, unless we stated we would
prove them in the Appendix.

###  3.1 Proof of the condition for asymptotic equivalence for bipartite
multi-graphs

###### Proof of Theorem 2.20.

The proof of (2.29) for simple random graphs can be found in [30, Theorem
6.18], which follows [34, Corollary 2.12]. The multi-graph version follows
analogously, as $\mathrm{BRG}_{n}(\bm{p})$ and $\mathrm{BRG}_{n}(\bm{q})$ can
be entirely encoded by the group presence, just like simple random graphs are
encoded by the edge presence, i.e., the asymptotic equivalence of two graphs
$\mathrm{BRG}_{n}(\bm{p})$ and $\mathrm{BRG}_{n}(\bm{q})$ is equivalent to the
asymptotic equivalence of their group variables, which are independent
Bernoulli random variables with success probabilities
$\bm{p}=(p_{a})_{a\in\cup_{k\geq 2}[n]_{k}}$ and
$\bm{q}=(q_{a})_{a\in\cup_{k\geq 2}[n]_{k}}$. ∎

###  3.2 Proof of asymptotic equivalence of the union graph and the rescaled
graph

###### Proof of Theorem 2.22.

Recall (2.26) and (2.28). To verify condition (2.29) we first compute

$\displaystyle
0\leq\pi^{a,[0,t]}_{\text{\rm{ON}}}-\pi^{a,(t)}_{\text{\rm{ON}}}$
$\displaystyle\leq\frac{(1+t)f(|a|)\prod_{i\in
a}w_{i}}{\ell^{|a|-1}+f(|a|)\prod_{i\in a}w_{i}}-\frac{(1+t)f(|a|)\prod_{i\in
a}w_{i}}{\ell^{|a|-1}+(1+t)f(|a|)\prod_{i\in a}w_{i}}$ (3.1)
$\displaystyle\leq\frac{(1+t)^{2}f^{2}(|a|)\big{(}\prod_{i\in
a}w_{i}\big{)}^{2}}{\ell^{|a|-1}\big{(}\ell^{|a|-1}+(1+t)f(|a|)\prod_{i\in
a}w_{i}\big{)}},$

where we have used the fact that $1-e^{-x}\leq x$. Hence, by the fact that
$k!<k^{k}$,

$\displaystyle\sum_{a\in\cup_{k\geq
2}[n]_{k}}\frac{\big{(}\pi^{a,[0,t]}_{\text{\rm{ON}}}-\pi^{a,(t)}_{\text{\rm{ON}}}\big{)}^{2}}{\pi^{a,(t)}_{\text{\rm{ON}}}}$
$\displaystyle\leq(1+t)^{3}\sum_{k=2}^{\infty}\sum_{j_{1}<...<j_{k}\in[n]}\frac{(k!)^{3}(p_{k})^{3}(w_{j_{1}}\cdots
w_{j_{k}})^{3}}{\big{(}\ell_{n}^{k-1}\big{)}^{3}}$ (3.2)
$\displaystyle\leq(1+t)^{3}\sum_{k=2}^{\infty}k^{4}p_{k}^{3}\frac{1}{\ell_{n}^{k-1}}\bigg{(}\frac{k^{2}}{\ell_{n}}\bigg{)}^{k-2}\bigg{(}\frac{\mathbf{E}[W_{n}^{3}]}{\mathbf{E}[W_{n}]}\bigg{)}^{k}=o(1),$

which can be shown using suitable truncation arguments: one with respect to
the group size and one with respect to the weights. For the first truncation,
we can fix a sequence $b_{n}\to\infty$ and show that the contribution from
groups $a$ with $|a|>b_{n}$ vanishes. Then take $b_{n}=o(\sqrt{n})$ to bound
(3.2) for $a$ with $|a|\leq b_{n}$. For the second truncation, we eliminate
vertices with large weights in a similar manner. For more technical details
see Appendix B, where analogous truncation arguments occur frequently. Hence,
for some sequence $\varepsilon_{n}$, as $n\to\infty$,

$\displaystyle\mathbf{P}\Bigg{(}\sum_{a\in\cup_{k\geq
2}[n]_{k}}\frac{\big{(}\pi^{a,[0,t]}_{\text{\rm{ON}}}-\pi^{a,(t)}_{\text{\rm{ON}}}\big{)}^{2}}{\pi^{a,(t)}_{\text{\rm{ON}}}}\geq\varepsilon_{n}\Bigg{)}\longrightarrow
0.$ (3.3)

The desired equivalence of $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ and
$\mathrm{BGRG}_{n}^{(t)}(\bm{w})$ follows. ∎

###  3.3 Proof of local convergence of the union graph

###### Proof of Theorem 2.23.

Convergence of $\mathrm{BGRG}^{0}_{n}(\bm{w})$ follows from convergence of the
stationary graph $\mathrm{BGRG}_{n}(\bm{w})$. For time interval $[0,t]$, we
prove convergence of the union graph by showing that it is asymptotically
equivalent to $\mathrm{BGRG}_{n}^{(t)}(\bm{w})$ (see Theorem 2.22). The
latter, in turn, converges as it fulfils the same conditions (see Remark B.14)
that guaranteed convergence of $\mathrm{BGRG}_{n}(\bm{w})$ (described in
Section 2.2, proven in Appendix B). Hence, it also turns out that the limiting
degree sequences in the union graph satisfy similar properties as the ones in
the static graph, with the Poisson parameter and proportion of groups of size
$k$ rescaled by the factor $t+1$. Hence, the bipartite union graph
asymptotically behaves like the static graph with slightly larger edge
probabilities and converges locally in probability to a related limiting
object with accordingly larger offspring distributions. ∎

###  3.4 Proof of the law of the marks

###### Proof of Lemma 2.24.

We compute the law of the marks of a fixed group $a$ taking into account
starting in ON and OFF state:

$\displaystyle\mathbf{P}$ $\displaystyle(\sigma_{\rm{ON}}^{a}\leq
s_{1},\sigma_{\rm{OFF}}^{a}\leq s_{2}|\text{ON in
$[0,t]$})=\frac{\mathbf{P}(\text{$\sigma_{\rm{ON}}^{a}\leq
s_{1},\sigma_{\rm{OFF}}^{a}\leq s_{2}$, ON in $[0,t]$})}{\mathbf{P}(\text{ON
in $[0,t]$})}$ (3.4) $\displaystyle=\frac{\mathbf{P}(\sigma_{\rm{ON}}^{a}\leq
s_{1},\sigma_{\rm{OFF}}^{a}\leq s_{2})}{\mathbf{P}(\text{ON in
$[0,t]$})}=\frac{\mathbf{P}(\sigma_{\rm{ON}}^{a}=0,\sigma_{\rm{OFF}}^{a}\leq
s_{2})+\mathbf{P}(\text{OFF at $0$},\sigma_{\rm{ON}}^{a}\leq
s_{1},\sigma_{\rm{OFF}}^{a}\leq s_{2})}{\mathbf{P}(\text{ON in $[0,t]$})}.$

We compute all three ingredients separately.
Step 1.

$\displaystyle\mathbf{P}(\sigma_{\rm{ON}}^{a}=0,\sigma_{\rm{OFF}}^{a}\leq
s_{2})=\pi^{a}_{\text{\rm{ON}}}\mathbf{P}(\text{$a$ goes OFF in
$(0,s_{2}]$})=\pi^{a}_{\text{\rm{ON}}}(1-e^{-s_{2}}).$ (3.5)

Step 2.

$\displaystyle\mathbf{P}(\text{OFF at $0$},\sigma_{\rm{ON}}^{a}\leq
s_{1},\sigma_{\rm{OFF}}^{a}\leq s_{2})=\pi^{a}_{\text{\rm{OFF}}}\mathbf{P}$
$\displaystyle(\text{$a$ goes ON in $(0,s_{1}]$, goes OFF in
$(\sigma_{\rm{ON}}^{a},s_{2}]$ }).$ (3.6)

The second term can be computed as

$\displaystyle\mathbf{P}$ $\displaystyle(\text{$a$ goes ON in $(0,s_{1}]$ and
goes OFF in $(\sigma_{\rm{ON}}^{a},s_{2}]$ })$ (3.7)
$\displaystyle=\int_{0}^{s_{1}}\mathbf{P}(Exp(\lambda^{a}_{\text{\rm{ON}}})\leq
s_{2}-Exp(\lambda^{a}_{\text{\rm{OFF}}})\mid
Exp(\lambda^{a}_{\text{\rm{OFF}}})=x)f_{Exp(\lambda^{a}_{\text{\rm{OFF}}})}(x)\text{d}x$
$\displaystyle=\int_{0}^{s_{1}}(1-e^{-\lambda^{a}_{\text{\rm{ON}}}(s_{2}-x)})\lambda^{a}_{\text{\rm{OFF}}}e^{-\lambda^{a}_{\text{\rm{OFF}}}x}\text{d}x.$

Splitting the terms and using the fact that
$\int_{0}^{s_{1}}\lambda^{a}_{\text{\rm{OFF}}}e^{-\lambda^{a}_{\text{\rm{OFF}}}x}\text{d}x=\mathbf{P}(Exp(\lambda^{a}_{\text{\rm{OFF}}})\leq
s_{1})$ we obtain

$\displaystyle\mathbf{P}$ $\displaystyle(\text{$a$ goes ON in $(0,s_{1}]$ and
goes OFF in $(\sigma_{\rm{ON}}^{a},s_{2}]$ })$ (3.8)
$\displaystyle=\mathbf{P}(Exp(\lambda^{a}_{\text{\rm{OFF}}})\leq
s_{1})-\lambda^{a}_{\text{\rm{OFF}}}\int_{0}^{s_{1}}e^{-(s_{2}-x)}e^{-\lambda^{a}_{\text{\rm{OFF}}}x}\text{d}x$
$\displaystyle=1-e^{-\lambda^{a}_{\text{\rm{OFF}}}s_{1}}-\frac{\lambda^{a}_{\text{\rm{OFF}}}e^{-s_{2}}}{\lambda^{a}_{\text{\rm{OFF}}}-1}(1-e^{-s_{1}(\lambda^{a}_{\text{\rm{OFF}}}-1)}).$

Hence,

$\displaystyle\mathbf{P}(\text{OFF at $0$},\sigma_{\rm{ON}}^{a}\leq
s_{1},\sigma_{\rm{OFF}}^{a}\leq
s_{2})=\pi^{a}_{\text{\rm{OFF}}}\bigg{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}s_{1}}-\frac{\lambda^{a}_{\text{\rm{OFF}}}}{\lambda^{a}_{\text{\rm{OFF}}}-1}(e^{-s_{2}}-e^{-s_{1}\lambda^{a}_{\text{\rm{OFF}}}}e^{s_{1}-s_{2}})\bigg{)}.$
(3.9)

Step 3. For the probability in the denominator of (3.4) recall once more
(2.26).

Gathering all three steps together, the expression in (3.4) becomes

$\displaystyle\mathbf{P}$ $\displaystyle(\sigma_{\rm{ON}}^{a}\leq
s_{1},\sigma_{\rm{OFF}}^{a}\leq s_{2}\mid\text{ON in $[0,t]$})$ (3.10)
$\displaystyle=\frac{\pi^{a}_{\text{\rm{ON}}}(1-e^{-s_{2}})}{\pi^{a}_{\text{\rm{ON}}}+\pi^{a}_{\text{\rm{OFF}}}\big{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}\big{)}}+\frac{\pi^{a}_{\text{\rm{OFF}}}\bigg{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}s_{1}}-\frac{\lambda^{a}_{\text{\rm{OFF}}}}{\lambda^{a}_{\text{\rm{OFF}}}-1}(e^{-s_{2}}-e^{-s_{1}\lambda^{a}_{\text{\rm{OFF}}}}e^{s_{1}-s_{2}})\bigg{)}}{\pi^{a}_{\text{\rm{ON}}}+\pi^{a}_{\text{\rm{OFF}}}\big{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}\big{)}}.$

We will now take the limit of the two fractions separately as $n\to\infty$. We
simplify

$\displaystyle\frac{\pi^{a}_{\text{\rm{ON}}}(1-e^{-s_{2}})}{\pi^{a}_{\text{\rm{ON}}}+\pi^{a}_{\text{\rm{OFF}}}\big{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}\big{)}}=\frac{1-e^{-s_{2}}}{1+1/(\lambda^{a}_{\text{\rm{OFF}}})\big{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}\big{)}}$
(3.11)

As we know,
$\lim_{n\to\infty}\lambda^{a}_{\text{\rm{OFF}}}=\lim_{n\to\infty}\frac{f(|a|)\prod_{i\in
a}w_{i}}{\ell_{n}^{|a|-1}}=0.$ Substituting $x=\frac{f(|a|)\prod_{i\in
a}w_{i}}{\ell_{n}^{|a|-1}}$ we obtain

$\displaystyle\lim_{n\to\infty}{\lambda^{a}_{\text{\rm{OFF}}}}^{-1}\big{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}\big{)}=\lim_{x\to
0}\frac{1-e^{-xt}}{x}=\lim_{x\to 0}\frac{te^{-xt}}{1}=t,$ (3.12)

so that

$\displaystyle\lim_{n\to\infty}\frac{\pi^{a}_{\text{\rm{ON}}}(1-e^{-s_{2}})}{\pi^{a}_{\text{\rm{ON}}}+\pi^{a}_{\text{\rm{OFF}}}\big{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}\big{)}}=\frac{1-e^{-s_{2}}}{1+t}.$
(3.13)

Now we compute the limit as $n\to\infty$ of the second term in (3.10). We
again simplify, dividing by $\pi^{a}_{\text{\rm{OFF}}}$, to obtain

$\displaystyle\frac{1-e^{-\lambda^{a}_{\text{\rm{OFF}}}s_{1}}+\frac{\lambda^{a}_{\text{\rm{OFF}}}}{1-\lambda^{a}_{\text{\rm{OFF}}}}(e^{-s_{2}}-e^{-s_{1}\lambda^{a}_{\text{\rm{OFF}}}}e^{s_{1}-s_{2}})}{\lambda^{a}_{\text{\rm{OFF}}}+1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}}$
(3.14)
$\displaystyle=\frac{1-e^{-\lambda^{a}_{\text{\rm{OFF}}}s_{1}}}{\lambda^{a}_{\text{\rm{OFF}}}+1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}}+\frac{\lambda^{a}_{\text{\rm{OFF}}}(e^{-s_{2}}-e^{-s_{1}\lambda^{a}_{\text{\rm{OFF}}}}e^{s_{1}-s_{2}})}{(1-\lambda^{a}_{\text{\rm{OFF}}})(\lambda^{a}_{\text{\rm{OFF}}}+1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t})}=A_{n}+B_{n}.$

Then, using the same substitution as previously,

$\displaystyle\lim_{n\to\infty}A_{n}=\lim_{x\to
0}\frac{1-e^{-xs_{1}}}{x+1-e^{-xt}}=\lim_{x\to
0}\frac{s_{1}e^{-xs_{1}}}{1+te^{-xt}}=\frac{s_{1}}{1+t},$ (3.15)

and

$\displaystyle\lim_{n\to\infty}B_{n}$ $\displaystyle=\lim_{x\to
0}\frac{xe^{-s_{2}}-xe^{-s_{1}x}e^{s_{1}-s_{2}}}{1-e^{-xt}-x^{2}+xe^{-xt}}=\frac{e^{-s_{2}}-e^{s_{1}-s_{2}}}{1+t}.$
(3.16)

Combining,

$\displaystyle\lim_{n\to\infty}\frac{\pi^{a}_{\text{\rm{OFF}}}\bigg{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}s_{1}}-\frac{\lambda^{a}_{\text{\rm{OFF}}}}{\lambda^{a}_{\text{\rm{OFF}}}-1}(e^{-s_{2}}-e^{-s_{1}\lambda^{a}_{\text{\rm{OFF}}}}e^{s_{1}-s_{2}})\bigg{)}}{\pi^{a}_{\text{\rm{ON}}}+\pi^{a}_{\text{\rm{OFF}}}\big{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}\big{)}}=\frac{s_{1}+e^{-s_{2}}-e^{s_{1}-s_{2}}}{1+t}.$
(3.17)

Thus, by (3.10),

$\displaystyle\lim_{n\to\infty}\mathbf{P}$
$\displaystyle(\sigma_{\rm{ON}}^{a}\leq s_{1},\sigma_{\rm{OFF}}^{a}\leq
s_{2}\mid\text{ON in $[0,t]$})=\frac{1-e^{s_{1}-s_{2}}+s_{1}}{1+t},$ (3.18)

as required. ∎

###  3.5 Proof of local limit of marked union graphs

###### Proof of Theorem 2.25.

Theorem 2.23 shows local convergence of the unmarked
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$, which means that for any fixed rooted
graph $(H_{\star},o^{\prime})$ and $r\in\mathbf{N}$,

$\displaystyle\mathbf{P}(B_{r}(G_{n}^{[0,t]},V^{(l)}_{n})\simeq(H_{\star},o^{\prime})\mid
G_{n})$
$\displaystyle:=\frac{1}{|G_{n}|}\sum_{i\in[n]}\mathds{1}_{\\{B_{r}(G_{n}^{[0,t]},i)\simeq(H_{\star},o^{\prime})\\}}$
$\displaystyle\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\hskip
2.84544pt\mathbf{P}(B_{r}(\mathrm{BP}^{[0,t]}_{\gamma},o)\simeq(H_{\star},o^{\prime})),$

where we have written $(G_{n}^{[0,t]},o)$ instead of
$\mathrm{BGRG}^{[0,t]}_{n}$ for the sake of simplicity of notation in this
proof. If the marked version of the union graph converges locally in
probability, then for any fixed marked rooted graph
$(H_{\star},(\bar{m}_{1},\bar{m}_{2}),o^{\prime})$ and $r\in\mathbf{N}$,

$\displaystyle\mathbf{P}$
$\displaystyle\bigg{(}\text{d}_{\mathcal{G}_{\star}}\big{(}(G_{n}^{[0,t]},\big{(}(\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}})\big{)}_{a\in\cup_{k\geq
2}[n]_{k}},V^{(l)}_{n}),(H_{\star},(\bar{m}_{1},\bar{m}_{2}),o^{\prime})\big{)}\leq\frac{1}{r+1}\mid(G_{n}^{[0,t]},\big{(}(\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}})\big{)}_{a\in\cup_{k\geq
2}[n]_{k}}\bigg{)}$
$\displaystyle:=\frac{1}{n}\sum_{i\in[n]}\mathds{1}_{\big{\\{}\text{d}_{\mathcal{G}_{\star}}\big{(}(G_{n}^{[0,t]},\big{(}(\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}})\big{)}_{a\in\cup_{k\geq
2}[n]_{k}},i),(H_{\star},(\bar{m}_{1},\bar{m}_{2}),o^{\prime})\big{)}\leq\frac{1}{r+1}\big{\\}}}$
$\displaystyle\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}\hskip
2.84544pt\mathbf{P}\bigg{(}\text{d}_{\mathcal{G}_{\star}}\big{(}(\mathrm{BP}^{[0,t]}_{\gamma},\big{(}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})\big{)},o),(H_{\star},(\bar{m}_{1},\bar{m}_{2}),o^{\prime})\big{)}\leq\frac{1}{r+1}\bigg{)}.$

Note that the edge marks are independent since all the groups switch on and
off independently of each other. Hence, if the marks converge in distribution
to some limiting marks they will converge jointly for all groups and all
$s\in[0,t]$. In Lemma 2.24 we showed that they indeed converge and also that
the marks of all groups present within $[0,t]$ are also identically
distributed. This implies that we can couple each pair of marks with their
limiting marks so that they are appropriately close to each other. Hence, the
proportion of vertices whose neighborhoods look like
$(H_{\star},(\bar{m}_{1},\bar{m}_{2}),o^{\prime})$ must converge to the
probability that neighborhoods in
$(B_{r}(\mathrm{BP}^{[0,t]}_{\gamma},\big{(}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})\big{)},o)$
look like $(H_{\star},(\bar{m}_{1},\bar{m}_{2}),o^{\prime})$, which precisely
means that the marked version of $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$
converges. Next, the convergence of the marked intersection graph follows from
the convergence of the underlying bipartite structure, as community projection
preserves marked graphs’ distance. ∎

###  3.6 Proof of the switching pace of the groups in the union graph

###### Proof of Lemma 2.26.

For any finite $r>0$, we investigate

$\displaystyle\mathbf{P}\big{(}\exists a\in
B_{r}^{[0,t]}(V_{n}^{(l)}):\text{$a$ \rm{ON} twice in
$[0,t]$}\big{)}=\mathbf{E}\bigg{[}\mathbf{P}\big{(}\exists a\in
B_{r}^{[0,t]}(V_{n}^{(l)}):\text{$a$ \rm{ON} twice in $[0,t]$}\mid
G_{n}^{[0,t]}\big{)}\bigg{]},$ (3.19)

where we denote the $r$-neighbourhood of a uniformly chosen vertex in
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ by $B_{r}^{[0,t]}(V_{n}^{(l)})$ and for
simplification we write $G_{n}^{[0,t]}$ instead of
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ to denote conditioning on the union graph.
Applying the union bound yields

$\displaystyle\mathbf{P}\big{(}\exists a\in
B_{r}^{[0,t]}(V_{n}^{(l)}):\text{$a$ \rm{ON} twice in $[0,t]$}\mid
G_{n}^{[0,t]}\big{)}\leq 1\wedge\sum_{a\in
B_{r}^{[0,t]}(V_{n}^{(l)})}\mathbf{P}\big{(}\text{$a$ \rm{ON} twice in
$[0,t]$}\mid G_{n}^{[0,t]}\big{)}$ (3.20)

We first apply a suitable truncation (for more details see similar cases, for
instance, proof of Theorem B.4 or Remark B.11): we truncate the maximum vertex
weight by $a_{n}$ and the maximum group size by $b_{n}$, with
$a_{n}=\log(n),b_{n}=\log(n)$ to obtain

$\displaystyle\sum_{a\in B_{r}^{[0,t]}(V_{n}^{(l)})}$
$\displaystyle\mathbf{P}\big{(}\text{$a$ \rm{ON} twice in $[0,t]$}\mid
G_{n}^{[0,t]}\big{)}$ (3.21) $\displaystyle=\sum_{a\in
B_{r}^{[0,t]}(V_{n}^{(l)})}\mathbf{P}\big{(}\text{$a$ \rm{ON} twice in
$[0,t]$}\mid G_{n}^{[0,t]}\big{)}\mathds{1}_{\\{\max_{i}w_{i}\leq
a_{n},\max_{a}|a|\leq b_{n}\\}}+o_{\mathbf{P}}(1),$

where the maximums are taken w.r.t. a vertex $i\in B_{r}^{[0,t]}(V_{n}^{(l)})$
and group $a\in B_{r}^{[0,t]}(V_{n}^{(l)})$. The remainder is small since
Condition 1.2 implies that our union graph is sparse, and hence observing
large groups and vertices with large weights in a uniformly chosen
$r$-neighborhood is unlikely. We now compute

$\displaystyle\mathbf{P}(\text{$a$ switches ON twice in $[0,t]$}\mid
G_{n}^{[0,t]})$ $\displaystyle=\frac{\mathbf{P}(\text{$a$ switches ON twice in
$[0,t]$}\mid\text{$a$ active in $[0,t]$})}{\mathbf{P}(\text{$a$ active in
$[0,t]$})}$ (3.22) $\displaystyle=\frac{\mathbf{P}(\text{$a$ switches ON twice
in $[0,t]$})}{\mathbf{P}(\text{$a$ active in $[0,t]$})},$

where the first equality follows from the independence of groups. We have

$\displaystyle\mathbf{P}$ $\displaystyle(\text{$a$ switches ON twice in
$[0,t]$})=\pi^{a}_{\text{\rm{ON}}}\mathbf{P}(\text{$a$ switches OFF and ON
again in $[0,t]$})$ (3.23)
$\displaystyle+\pi^{a}_{\text{\rm{OFF}}}\mathbf{P}(\text{$a$ switches ON, then
OFF and ON again in $[0,t]$}).$

Recall that the times that groups spend in the ON and OFF states are
exponentially distributed with rates $Exp(\lambda^{a}_{\text{\rm{ON}}})$ and
$Exp(\lambda^{a}_{\text{\rm{OFF}}})$ respectively. Hence, using the fact that
for all $x,1-e^{-x}\leq x$,

$\displaystyle\mathbf{P}(\text{$a$ switches OFF and ON again in $[0,t]$})$
$\displaystyle=\mathbf{P}(Exp(\lambda^{a}_{\text{\rm{ON}}})+Exp(\lambda^{a}_{\text{\rm{OFF}}})\leq
t)$ (3.24) $\displaystyle\leq\mathbf{P}(Exp(\lambda^{a}_{\text{\rm{OFF}}})\leq
t)=\big{(}1-e^{-\lambda^{a}_{\text{\rm{OFF}}}t}\big{)}\leq
t\lambda^{a}_{\text{\rm{OFF}}}\wedge 1,$

and, applying the same inequality again,

$\displaystyle\mathbf{P}$ $\displaystyle(\text{$a$ switches ON, then OFF and
ON again in
$[0,t]$})=\mathbf{P}(Exp(\lambda^{a}_{\text{\rm{OFF}}})+Exp(\lambda^{a}_{\text{\rm{ON}}})+Exp^{\prime}(\lambda^{a}_{\text{\rm{OFF}}})\leq
t)$ (3.25)
$\displaystyle\leq\mathbf{P}(Exp(\lambda^{a}_{\text{\rm{OFF}}})+Exp^{\prime}(\lambda^{a}_{\text{\rm{OFF}}})\leq
t)=1-e^{-t\lambda^{a}_{\text{\rm{OFF}}}}-t\lambda^{a}_{\text{\rm{OFF}}}e^{-t\lambda^{a}_{\text{\rm{OFF}}}}\leq
t\lambda^{a}_{\text{\rm{OFF}}}(1-e^{-t\lambda^{a}_{\text{\rm{OFF}}}})\leq(t\lambda^{a}_{\text{\rm{OFF}}})^{2}\wedge
1.$

Substituting (3.24) and (3.25) into (3.23) and using the facts that
$\pi^{a}_{\text{\rm{ON}}}\leq\lambda^{a}_{\text{\rm{ON}}},\pi^{a}_{\text{\rm{OFF}}}\leq
1$ yields

$\displaystyle\mathbf{P}$ $\displaystyle(\text{$a$ switches ON twice in
$[0,t]$})\leq(t+t^{2})(\lambda^{a}_{\text{\rm{OFF}}})^{2}\wedge 1.$ (3.26)

To obtain the probability in the denominator of (3.22) recall (2.26).
Combining all of the above, we arrive at the bound

$\displaystyle\mathbf{P}$ $\displaystyle(\text{$a$ switches ON twice in
$[0,t]$}\mid G_{n}^{[0,t]})\leq c(t)\lambda^{a}_{\text{\rm{OFF}}}\wedge 1,$
(3.27)

where $c(t)$ is a constant. Thus, substituting (3.27) into (3.20) and invoking
(3.21) yields

$\displaystyle\mathbf{E}$ $\displaystyle\bigg{[}\mathbf{P}\big{(}\exists a\in
B_{r}^{[0,t]}(V_{n}^{(l)}):\text{$a$ \rm{ON} twice in $[0,t]$}\mid
G_{n}^{[0,t]}\big{)}\bigg{]}$ (3.28)
$\displaystyle\leq\mathbf{E}\bigg{[}\bigg{(}\sum_{a\in
B_{r}^{[0,t]}(V_{n}^{(l)})}(\lambda^{a}_{\text{\rm{OFF}}}\wedge
1)\cdot\mathds{1}_{\\{\max_{i}w_{i}\leq a_{n},\max_{a}|a|\leq
b_{n}\\}}\bigg{)}\wedge 1\bigg{]}.$

Note that by the local limit of $\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ shown in
Theorem 2.23 we know that $|B_{r}^{[0,t]}(V_{n}^{(l)})|$ is tight. We also
know that $\lambda^{a}_{\text{\rm{OFF}}}$ is small for $n$ large for a group
$a$ with $\max_{i\in a}w_{i}\leq a_{n}$ and $|a|\leq b_{n}$. Therefore, as
$n\to\infty$,

$\displaystyle\sum_{a\in
B_{r}^{[0,t]}(V_{n}^{(l)})}\big{(}\lambda^{a}_{\text{\rm{OFF}}}\wedge
1\big{)}\mathds{1}_{\\{\max_{i\in a}w_{i}\leq a_{n},\max|a|\leq
b_{n}\\}}\stackrel{{\scriptstyle\mathbf{P}}}{{\longrightarrow}}0.$ (3.29)

Hence, by applying the dominated convergence theorem to (3.28) we conclude

$\displaystyle\mathbf{P}\big{(}\exists a\in
B_{r}^{[0,t]}(V_{n}^{(l)}):\text{$a$ \rm{ON} twice in
$[0,t]$}\big{)}\big{)}=o(1).$ (3.30)

∎

###  3.7 Proof of dynamic local limit of the intersection graph

###### Proof of Theorem 1.6.

We first show the dynamic local weak convergence of
$\big{(}\mathrm{BGRG}^{s}_{n}(w)\big{)}_{s\in[0,t]}$, i.e.,

$\displaystyle\bigg{(}\big{(}\mathrm{BGRG}^{s}_{n},V^{(l)}_{n}\big{)}\bigg{)}_{s\in[0,t]}\stackrel{{\scriptstyle\text{d}}}{{\longrightarrow}}\bigg{(}(\mathrm{BP}^{s}_{\gamma},o)\bigg{)}_{s\in[0,t]}.$
(3.31)

The proof follows in two steps: we first show convergence of finite-
dimensional distributions and then tightness - the two conditions for weak
convergence of processes from compact space to separable and complete space
given in literature [36, Lemma 16.2, Theorem 16.3]. For the convenience of the
reader, we reproduce these results in Appendix C (see Lemma C.2 and Theorem
C.3).

Condition (i): Convergence of finite-dimensional distributions. Once more, for
the sake of simplicity of notation, throughout the proof we abbreviate
$\mathrm{BGRG}_{n}^{s}(\bm{w})$ to $\mathrm{G}^{s}_{n}$. We need to show that
for all $s_{1}\leq s_{2}\leq...\leq s_{k}\in[0,t]$

$\displaystyle\mathbf{P}(\forall
j\in[k]:B_{r}(G^{s_{j}}_{n},V^{(l)}_{n})\simeq(H_{j},o)\mid G_{n})$
$\displaystyle=\frac{1}{n}\mathbf{E}\Bigg{[}\sum_{i\in[n]}\mathds{1}_{\big{\\{}B_{r}(G^{s_{j}}_{n},i)\simeq(H_{j},o)\big{\\}}}\Bigg{]}$
(3.32) $\displaystyle\longrightarrow\mathbf{P}(\forall
j\in[k]:B_{r}(\mathrm{BP}^{s_{j}}_{\gamma},o)\simeq(H_{j},o)).$

The convergence follows immediately from the convergence of the marked union
graph. Indeed, if the marked union graph converges, appropriate marked-graph
isomorphisms must hold. In particular, since marks converge,

$\displaystyle\mathbf{P}\big{(}s\in[\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}}]\big{)}\longrightarrow\mathbf{P}\big{(}s\in[t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}}]\big{)}.$
(3.33)

Thus indeed, if a neighborhood of a uniformly chosen vertex in the marked
union graph resembles a neighborhood in a marked
$(\mathrm{BP}^{[0,t]}_{\gamma},o)$, then for every $s\in[0,t]$ a neighborhood
of a uniformly chosen vertex in a subgraph of
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$ restricted to groups $a$ such that
$s\in[\sigma^{a}_{\rm{ON}},\sigma^{a}_{\rm{OFF}}]$ must resemble a subgraph of
$(\mathrm{BP}_{\gamma}^{[0,t]},\big{(}(t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}})\big{)},o)$
incorporating accordingly only right-vertices $a$ such that
$s\in[t^{a}_{\rm{ON}},t^{a}_{\rm{OFF}}]$.

Condition (ii): Tightness of the process. Since for random processes between a
compact and a Polish space, the convergence of finite-dimensional
distributions combined with tightness (which, in separable and complete
spaces, is equivalent to relative compactness in distribution) yields process
convergence (see Appendix C for a brief summary of results we use, taken from
[36], Chapter 16), it remains to show that our dynamic graph process is tight,
with respect to its local topology. This translates to verifying if for all
$0<s_{1}<s<s_{2}<t$, $\varepsilon,\eta>0$ there exists $n_{0}\geq 1$ and
$\delta>0$ such that for all $n\geq n_{0}$

$\displaystyle\mathbf{P}\bigg{(}\sup_{(s,s_{1},s_{2})\in\mathscr{S}_{\delta}}\min\big{[}\text{d}_{\mathcal{G}_{\star}}\big{(}(G^{s_{1}}_{n},V^{(l)}_{n}),(G^{s}_{n},V^{(l)}_{n})\big{)},\text{d}_{\mathcal{G}_{\star}}\big{(}(G^{s}_{n},V^{(l)}_{n}),(G^{s_{2}}_{n},V^{(l)}_{n})\big{)}\big{]}>\varepsilon\bigg{)}\leq\eta,$
(3.34)

with
$\mathscr{S}_{\delta}=\\{(s,s_{1},s_{2}):s\in[s_{1},s_{2}],|s_{2}-s_{1}|\leq\delta\\}$.
Note that the above is equivalent to

$\displaystyle\mathbf{P}\bigg{(}\exists
s\in[s_{1},s_{2}],s_{2}-s_{1}<\delta:B_{1/\varepsilon}(G^{s_{1}}_{n},V^{(l)}_{n})\not\simeq
B_{1/\varepsilon}(G^{s}_{n},V^{(l)}_{n}),B_{1/\varepsilon}(G^{s}_{n},V^{(l)}_{n})\not\simeq
B_{1/\varepsilon}(G^{s_{2}}_{n},V^{(l)}_{n})\bigg{)}\leq\eta.$ (3.35)

We partition $[0,t]$ into intervals of length $\delta$ and introduce

$\displaystyle S_{l}=\\{\text{two jumps in the neighbourhood of $V^{(l)}_{n}$
in the $l$-th interval of length $\delta$}\\}.$ (3.36)

Note that thanks to the stationarity, the probability of a jump in $[0,s]$ and
then another jump in $[s,\delta]$ can be bounded by the probability of two
jumps in $[0,\delta]$. Hence,

$\displaystyle(\ref{dyn_loc_lim_tight_tobebounded})\leq\mathbf{P}(\bigcup_{l=1}^{t/\delta}S_{l})\leq\frac{t}{\delta}\mathbf{P}(S_{1}),$
(3.37)

where $S_{1}$ is then accordingly the event of two jumps in the time interval
$[0,\delta]$. Recall that the only aspect that can cause changes in
neighborhoods is group activation and deactivation. Note that the groups that
changed their status within $[0,t]$ must in particular be active during
$[0,t]$, which means they are in the union graph
$\mathrm{BGRG}_{n}^{[0,t]}(\bm{w})$. Therefore, as it turns out to be useful
for the upper bound, we now condition event $S_{1}$ on the union graph. For
simplicity, we denote the union graph by $G_{n}^{[0,t]}$. We also denote the
$r$-neighborhood of $V_{n}^{(l)}$ in the union graph by
$B_{r}^{[0,t]}(V_{n}^{(l)})$. We compute

$\displaystyle\mathbf{P}(S_{1}\mid G^{[0,t]}_{n})=$
$\displaystyle\mathbf{P}(\text{$\exists a_{1}\neq a_{2}\in
B_{1/\varepsilon}^{[0,t]}(V_{n}^{(l)}):a_{1},a_{2}$ switch OFF in
$[0,\delta]$}\mid G^{[0,t]}_{n})$ (3.38)
$\displaystyle+\mathbf{P}(\text{$\exists a_{1}\neq a_{2}\in
B_{1/\varepsilon}^{[0,t]}(V_{n}^{(l)}):a_{1}$ switches OFF, $a_{2}$ switches
ON in $[0,\delta]$}\mid G^{[0,t]}_{n})$
$\displaystyle+\mathbf{P}(\text{$\exists a_{1}\neq a_{2}\in
B_{1/\varepsilon}^{[0,t]}(V_{n}^{(l)}):a_{1},a_{2}$ switch ON in
$[0,\delta]$}\mid G^{[0,t]}_{n}).$

Hence,

$\displaystyle\mathbf{P}(S_{1}\mid G^{[0,t]}_{n})=$
$\displaystyle\big{(}1-e^{-\delta\\#\\{a\in
B_{1/\varepsilon}^{[0,t]}(V_{n}^{(l)})\\}}\big{)}^{2}$ (3.39)
$\displaystyle+\big{(}1-e^{-\delta\\#\\{a\in
B_{1/\varepsilon}^{[0,t]}(V_{n}^{(l)})\\}}\big{)}\big{(}1-e^{-\delta\sum_{a\in
B_{1/\varepsilon}^{[0,t]}(V_{n}^{(l)})}\lambda^{a}_{\text{\rm{OFF}}}}\big{)}\wedge
1$ $\displaystyle+\big{(}1-e^{-\delta\sum_{a\in
B_{1/\varepsilon}^{[0,t]}(V_{n}^{(l)})}\lambda^{a}_{\text{\rm{OFF}}}}\big{)}^{2}\wedge
1.$

Fix a large constant $b_{\delta}$, and consider

$\displaystyle\mathscr{E}=\big{\\{}|B_{1/\varepsilon}^{[0,t]}(V_{n}^{(l)})|\leq
b_{\delta}\big{\\}}.$ (3.40)

Given $\mathscr{E}$,

$\displaystyle\mathbf{P}(S_{1}\mid G^{[0,t]}_{n})$ $\displaystyle\leq
3\delta^{2}b^{2}_{\delta}.$ (3.41)

Recall that in Theorem 2.23 we derived local convergence of the union graph,
which guarantees that the neighbourhood of a uniformly chosen vertex in the
union graph is bounded. Thus, for every $\varepsilon>0$, we can find a
$b_{\delta}$ sufficiently large, such that $\mathbf{P}(\mathscr{E})\geq
1-\varepsilon$. After taking the expectation of (3.41) with respect to the
union graph, and substituting the result into (3.37), we obtain

$\displaystyle\mathbf{P}$ $\displaystyle\bigg{(}\exists
s\in[s_{1},s_{2}],s_{2}-s_{1}<\delta\colon
B_{1/\varepsilon}(G^{s_{1}}_{n},V^{(l)}_{n})\not\simeq
B_{1/\varepsilon}(G^{s}_{n},V^{(l)}_{n}),B_{1/\varepsilon}(G^{s}_{n},V^{(l)}_{n})\not\simeq
B_{1/\varepsilon}(G^{s_{2}}_{n},V^{(l)}_{n});\mathscr{E}\bigg{)}$ (3.42)
$\displaystyle\leq\frac{t}{\delta}\mathbf{E}\big{[}3\delta^{2}b^{2}_{\delta}\mathds{1}_{\mathscr{E}}\big{]}=3t\mathbf{E}\big{[}b^{2}_{\delta}\mathds{1}_{\mathscr{E}}\big{]}\delta,$

which, for every $b_{\delta}$, can be made arbitrarily small by taking
$\delta$ small. As we argued that for such a choice of $b_{\delta}$, event
$\mathscr{E}$ holds with probability at least $1-\varepsilon$, we conclude
that (3.35) holds by taking $\delta$ and $\varepsilon$ small as a function of
$\eta$.

Consequence. For every $s\in[0,t]$, $\mathrm{DRIG}_{n}^{s}(\bm{w})$ can be
built from $\mathrm{BGRG}_{n}^{s}(\bm{w})$ via a community projection, which
preserves graph isomorphism and tightness. Hence, its convergence follows from
the just shown convergence of $\mathrm{BGRG}_{n}^{s}(\bm{w})$, and its local
limit, $(\mathrm{CP}^{s},o)$, is a community projection of the limit of
$\mathrm{BGRG}_{n}^{s}(\bm{w})$. ∎

######  Remark 3.1.

In the proof of Theorem 1.6 we show dynamic local weak convergence. However,
we argue that in the same manner, we could derive dynamic local convergence in
probability. Indeed, note that neighborhood processes of two distinct
uniformly chosen vertices are i.i.d. stochastic processes, and hence, their
convergence can be derived in the same way as in the proof above. The authors
of [24] prove this result rigorously (see [24, Lemma 3.10]).

###  3.8 Proof of convergence of the dynamic giant membership process

###### Proof of Theorem 1.8.

Note again that the giant component in the intersection graph is strictly
connected to the giant component in the underlying bipartite structure. Hence,
in this proof, we only focus on the underlying bipartite structure. To show
the desired convergence it suffices to show that
$\big{(}J_{n}(s)\big{)}_{s\in[0,t]}$ and
$\big{(}\mathcal{J}(s)\big{)}_{s\in[0,t]}$ satisfy Conditions (i)-(iii) from
Lemma C.1.

Condition (i): Convergence of finite-dimensional distributions. Note that
thanks to our results on the static giant component (see Theorem 2.17),

$\displaystyle\mathbf{P}(J_{n}(s)=1)=\mathbf{P}(o_{n}\in\mathscr{C}^{s}_{1})=\frac{\mathbf{E}[|\mathscr{C}^{s}_{1}|]}{n}\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}\mu\big{(}|\mathscr{C}^{s}(o)|=\infty\big{)},$
(3.43)

where $(G^{s},o)$ is the limiting, rooted graph at time $s$. Furthermore, as a
consequence of the dynamic local weak convergence (Theorem 1.6), as
$n\to\infty$,

$\displaystyle\Big{(}J^{(r)}_{n}(s)\Big{)}_{s\in[0,t]}=\Big{(}\mathds{1}_{\big{\\{}\partial
B^{G_{n}^{s}}_{r}(o_{n})\neq\varnothing\big{\\}}}\Big{)}_{s\in[0,t]}\stackrel{{\scriptstyle\text{d}}}{{\longrightarrow}}\Big{(}\mathds{1}_{\big{\\{}\partial
B_{r}^{G^{s}}(o)\neq\varnothing\big{\\}}}\Big{)}_{s\in[0,t]}=\big{(}\mathcal{J}^{(r)}(s)\big{)}_{s\in[0,t]},$
(3.44)

with $\partial B^{G_{n}^{s}}_{r}(o_{n})=\\{i\in[n]:\text{d}(o,v)=r\\}$, i.e.,
the set of vertices of graph distance $r$ from the root. Since we know what is
happening in local neighborhoods jointly for all $s\in[0,t]$ we try to link
the distribution of $\big{(}J_{n}(s)\big{)}_{s\in[0,t]}$ to the distribution
of $\big{(}J^{(r)}_{n}(s)\big{)}_{s\in[0,t]}$. For any $r>0$ and for all
$\\{s_{1},...,s_{k}\\}\in[0,t]$,

$\displaystyle\mathbf{P}$
$\displaystyle(J_{n}(s_{1})=...=J_{n}(s_{k})=1)=\mathbf{P}(J^{(r)}_{n}(s_{1})=...=J^{(r)}_{n}(s_{k})=1)$
(3.45)
$\displaystyle+\mathbf{P}(J_{n}(s_{1})=...=J_{n}(s_{k})=1)-\mathbf{P}(J^{(r)}_{n}(s_{1})=...=J^{(r)}_{n}(s_{k})=1).$

We look at the difference of probabilities in (3.45):

$\displaystyle\big{|}\mathbf{P}$
$\displaystyle(J_{n}(s_{1})=...=J_{n}(s_{k})=1)-\mathbf{P}(J^{(r)}_{n}(s_{1})=...=J^{(r)}_{n}(s_{k})=1)\big{|}$
(3.46)
$\displaystyle\leq\mathbf{P}(J_{n}(s_{1})=...=J_{n}(s_{k})=1,\neg\big{(}J^{(r)}_{n}(s_{1})=...=J^{(r)}_{n}(s_{k})=1\big{)})$
$\displaystyle=\mathbf{P}\big{(}J_{n}(s_{1})=...=J_{n}(s_{k})=1,\bigcup_{i=1}^{k}\big{\\{}J^{(r)}_{n}(s_{i})\neq
1\big{\\}}\big{)}$
$\displaystyle=\mathbf{P}\big{(}\bigcup_{i=1}^{k}\big{\\{}J_{n}(s_{1})=...=J_{n}(s_{k})=1,J^{(r)}_{n}(s_{i})\neq
1\big{\\}}\big{)}\leq\mathbf{P}\big{(}\bigcup_{i=1}^{k}\big{\\{}J^{(r)}_{n}(s_{i})\neq
J_{n}(s_{i})\big{\\}}\big{)}.$

Note that by the static local limit and (3.43),

$\displaystyle\lim_{r\to\infty}\lim_{n\to\infty}\mathbf{P}\big{(}\bigcup_{i=1}^{k}\big{\\{}J^{(r)}_{n}(s_{i})\neq
J_{n}(s_{i})\big{\\}}\big{)}\leq
k\cdot\lim_{r\to\infty}\lim_{n\to\infty}\mathbf{P}(J^{(r)}_{n}(s)\neq
J^{n}(s))=0.$ (3.47)

Hence,

$\displaystyle\lim_{r\to\infty}\lim_{n\to\infty}\big{|}\mathbf{P}$
$\displaystyle(J_{n}(s_{1})=...=J_{n}(s_{k})=1)-\mathbf{P}(J^{(r)}_{n}(s_{1})=...=J^{(r)}_{n}(s_{k})=1)\big{|}=0,$
(3.48)

and thus,

$\displaystyle\lim_{n\to\infty}\mathbf{P}$
$\displaystyle(J_{n}(s_{1})=...=J_{n}(s_{k})=1)=\lim_{r\to\infty}\lim_{n\to\infty}\mathbf{P}(J^{(r)}_{n}(s_{1})=...=J^{(r)}_{n}(s_{k})=1).$
(3.49)

However, by (3.44),

$\displaystyle\mathbf{P}(J^{(r)}_{n}(s_{1})=1,...,J^{(r)}_{n}(s_{k})=1)$
$\displaystyle\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}\mathbf{P}(\mathcal{J}^{(r)}(s_{1})=1,...,\mathcal{J}^{(r)}(s_{k})=1)$
(3.50) $\displaystyle\stackrel{{\scriptstyle
r\to\infty}}{{\longrightarrow}}\mu(|\mathscr{C}^{G^{s_{1}}}(o)|=...=|\mathscr{C}^{G^{s_{k}}}(o)|=\infty).$

Hence,

$\displaystyle\mathbf{P}$
$\displaystyle(J_{n}(s_{1})=...=J_{n}(s_{k})=1)\stackrel{{\scriptstyle
r\to\infty}}{{\longrightarrow}}\mu(|\mathscr{C}^{G^{s_{1}}}(o)|=...=|\mathscr{C}^{G^{s_{k}}}(o)|=\infty).$

Similarly, for another combination of values of the finite-dimensional
distribution,

$\displaystyle\mathbf{P}$
$\displaystyle(J_{n}(s_{1})=...=1,J_{n}(s_{k})=0)=\mathbf{P}(J^{(r)}_{n}(s_{1})=...=1,J^{(r)}_{n}(s_{k})=0)$
(3.51)
$\displaystyle+\mathbf{P}(J_{n}(s_{1})=...=1,J_{n}(s_{k})=0)-\mathbf{P}(J^{(r)}_{n}(s_{1})=...=1,J^{(r)}_{n}(s_{k})=0).$

We again look at the difference in the second line:

$\displaystyle\mathbf{P}$
$\displaystyle(J_{n}(s_{1})=...=1,J_{n}(s_{k})=0)-\mathbf{P}(J^{(r)}_{n}(s_{1})=...=1,J^{(r)}_{n}(s_{k})=0)$
(3.52)
$\displaystyle\leq\mathbf{P}\big{(}(J_{n}(s_{1})=...=1,J_{n}(s_{k})=0),\neg(J^{(r)}_{n}(s_{1})=...=1,J^{(r)}_{n}(s_{k})=0)\big{)}$
$\displaystyle=\mathbf{P}\big{(}(J_{n}(s_{1})=...=1,J_{n}(s_{k})=0),(J^{(r)}_{n}(s_{1})\neq
1\hskip 4.26773pt\text{or}\hskip 2.84544pt...\hskip 2.84544pt\text{or}\hskip
4.26773ptJ^{(r)}_{n}(s_{k})\neq 0)\big{)},$

which would again imply that for at least some $s_{i}\in[0,t]$ we have
$\mathbf{P}(J^{(r)}_{n}(s_{i})\neq J_{n}(s_{i}))$, so by the same argument as
previously we have that the above vanishes. Hence, we can use the same
argument to show the convergence of all finite-dimensional distributions.

Condition (ii): Tightness of the limiting process. We want to show that, for
all $\varepsilon>0$, as $\delta\to 0$,

$\displaystyle\mathbf{P}\big{(}|\mathcal{J}(t)-\mathcal{J}(t-\delta)|>\varepsilon\big{)}\longrightarrow
0.$ (3.53)

Since $\big{(}\mathcal{J}(s)\big{)}_{s\in[0,t]}$ is an indicator process, the
difference in absolute value between any two points of the process equals
either $0$ or $1$. Hence
$\mathbf{P}\big{(}|\mathcal{J}(t)-\mathcal{J}(t-\delta)|>\varepsilon\big{)}$
is equivalent to
$\mathbf{P}\big{(}|\mathcal{J}(t)-\mathcal{J}(t-\delta)|=1\big{)}$, which is
equivalent to
$\mathbf{P}(\mathcal{J}(t-\delta)=0,\mathcal{J}(t)=1)+\mathbf{P}(\mathcal{J}(t-\delta)=1,\mathcal{J}(t)=0)$.
We investigate these two factors separately. From the proof of condition
$(i)$,

$\displaystyle\lim_{\delta\to
0}\mathbf{P}(\mathcal{J}(t-\delta)=0,\mathcal{J}(t)=1)$
$\displaystyle=\lim_{\delta\to
0}\lim_{n\to\infty}\mathbf{P}(J_{n}(t-\delta)=0,J_{n}(t)=1)$ (3.54)
$\displaystyle=\lim_{\delta\to
0}\lim_{r\to\infty}\lim_{n\to\infty}\mathbf{P}(J^{(r)}_{n}(t-\delta)=0,J^{(r)}_{n}(t)=1).$

We compute

$\displaystyle\mathbf{P}(J^{(r)}_{n}(t-\delta)=0,J^{(r)}_{n}(t)=1)=\mathbf{P}\bigg{(}\partial
B^{G^{t-\delta}_{n}}_{r}(V^{(l)}_{n})=\varnothing,\partial
B^{G^{t}_{n}}_{r}(V^{(l)}_{n})\neq\varnothing\bigg{)}$ (3.55)

which means that the boundary of the $r$-neighborhood of a uniformly chosen
vertex is empty at time $t-\delta$ but non-empty at time point $t$. For that
to happen there has to be a change in groups’ statuses. Similarly as in the
proof of Theorem 1.6 we use the link with the union graph:

$\displaystyle\mathbf{P}\bigg{(}\partial
B^{G^{t-\delta}_{n}}_{r}(V^{(l)}_{n})=\varnothing,\partial
B^{G^{t}_{n}}_{r}(V^{(l)}_{n})\neq\varnothing\mid G_{n}^{[0,t]}\bigg{)}$
$\displaystyle=\mathbf{P}(\text{$\exists a\in B^{[0,t]}_{r}(V^{(l)}_{n}):a$
switches ON in $[t-\delta,t]\mid G_{n}^{[0,t]}$})$ (3.56)
$\displaystyle=\bigg{(}1-e^{-\delta\sum_{a\in
B^{[0,t]}_{r}(V^{(l)}_{n})}\lambda^{a}_{\text{\rm{OFF}}}}\bigg{)}\wedge 1.$

Hence,

$\displaystyle\mathbf{P}(J^{(r)}_{n}(t-\delta)=0,J^{(r)}_{n}(t)=1)\leq\mathbf{E}_{G_{n}^{[0,t]}}\bigg{[}\delta|B^{[0,t]}_{r}(V^{(l)}_{n})|\bigg{]},$
(3.57)

which can be bounded in the same way as the terms in (3.39) and hence
converges to $0$ as $\delta\to 0$. We can compute the complementary
probability, $\mathbf{P}\big{(}\partial
B^{G^{t-\delta}_{n}}_{r}(V^{(l)}_{n})\neq\varnothing,\partial
B^{G^{t}_{n}}_{r}(V^{(l)}_{n})=\varnothing\big{)}$, using similar reasoning.
Note that, conveniently, the probability of switching off is the same for all
groups. Thanks to this and the independence of groups we obtain

$\displaystyle\mathbf{P}\big{(}\partial
B^{G^{t-\delta}_{n}}_{r}(V_{n}^{(l)})\neq\varnothing,\partial
B^{G^{t}_{n}}_{r}(V_{n}^{(l)})=\varnothing\mid G_{n}^{t-\delta}\big{)}$
$\displaystyle=\mathbf{P}(\text{all $a\in\partial
B^{G^{t-\delta}_{n}}_{r}(V^{(l)}_{n})$ switch OFF$\mid G_{n}^{t-\delta}$})$
(3.58) $\displaystyle=\prod_{a\in\partial
B^{G^{t-\delta}_{n}}_{r}(V^{(l)}_{n})}(1-e^{-\delta}),$

and thus,

$\displaystyle\mathbf{P}\big{(}\partial
B^{G^{t-\delta}_{n}}_{r}(V_{n}^{(l)})\neq\varnothing,\partial
B^{G^{t}_{n}}_{r}(V_{n}^{(l)})=\varnothing\big{)}=\mathbf{E}_{G_{n}^{t-\delta}}\bigg{[}(1-e^{-\delta})^{\\#\\{a:a\in\partial
B^{G^{t-\delta}_{n}}_{r}(V^{(l)}_{n})\\}}\bigg{]}.$ (3.59)

With arguments similar to those used before, we can show that the above
vanishes as $\delta\to 0$ and $n\to\infty$. Combining (3.56) and (3.59) we
conclude that condition (3.53) holds.

Condition (iii): Tightness of the original process. We want to show that for
any $\varepsilon,\eta>0$ there exists $n_{0}\geq 1$ and $\delta>0$ such that,
for all $n\geq n_{0}$,

$\displaystyle\mathbf{P}\Bigg{(}\sup_{(s,s_{1},s_{2})\in\mathscr{S}_{\delta}}\min\Big{(}\Big{|}J_{n}(s)-J_{n}(s_{1})\Big{|},\Big{|}J_{n}(s_{2})-J_{n}(s)\Big{|}\Big{)}>\varepsilon\Bigg{)}\leq\eta,$
(3.60)

with
$\mathscr{S}_{\delta}=\\{(s,s_{1},s_{2}):s\in[s_{1},s_{2}],|s_{2}-s_{1}|\leq\delta\\}$.
Note that since $\big{(}J_{n}(s)\big{)}_{s\in[0,t]}$ is an indicator process,
$\min\Big{(}\Big{|}J_{n}(s)-J_{n}(s_{1})\Big{|},\Big{|}J_{n}(s_{2})-J_{n}(s)\Big{|}\Big{)}>\varepsilon$
if and only if
$\Big{|}J_{n}(s)-J_{n}(s_{1})\Big{|}=\Big{|}J_{n}(s_{2})-J_{n}(s)\Big{|}=1$,
which is equivalent to $J_{n}(s)\neq J_{n}(s_{1}),J_{n}(s_{2})\neq J_{n}(s)$.
This means two mutually exclusive events might occur: either
$J_{n}(s_{1})=J_{n}(s_{2})=1$ and $J_{n}(s)=0$, or the opposite
$J_{n}(s_{1})=J_{n}(s_{2})=0$ and $J_{n}(s)=1$. Note that we can skip the
supremum since for any $s\in[s_{1},s_{2}]$ the value of
$\Big{|}J_{n}(s)-J_{n}(s_{1})\Big{|}$ and
$\Big{|}J_{n}(s_{2})-J_{n}(s)\Big{|}$ is at most 1. Taking this all into
consideration, (3.60) becomes

$\displaystyle\mathbf{P}$ $\displaystyle\big{(}\exists\hskip
2.84544pts,s_{1},s_{2}:\hskip
2.84544ptJ_{n}(s_{1})=J_{n}(s_{2})=1,J_{n}(s)=0\hskip 2.84544pt\text{or}\hskip
2.84544ptJ_{n}(s_{1})=J_{n}(s_{2})=0,J_{n}(s)=1\big{)}$ (3.61)

with $s\in[s_{1},s_{2}]$ and $s_{1},s_{2}$ such that $s_{2}-s_{1}<\delta$. We
apply the same approach as in the proof of tightness for Theorem 1.6: we
partition $[0,t]$ into intervals of length $\delta$ and denote

$\displaystyle\mathbf{P}(R_{l})=\mathbf{P}(\text{two jumps of
$\big{(}J_{n}(s)\big{)}_{s\in[0,t]}$ in the $l$-th interval of length
$\delta$}).$ (3.62)

Then, by stationarity,

$\displaystyle(\ref{cond_iii_rewritten})=\mathbf{P}(\bigcup_{l=1}^{t/\delta}R_{l})\leq\frac{t}{\delta}\mathbf{P}(R_{1}).$
(3.63)

From the proof of the Condition (i) from Lemma C.1 we know that for some
$n_{0}$ big enough for all $n\geq n_{0}$ and some $s\in[0,\delta]$

$\displaystyle\mathbf{P}$
$\displaystyle\big{(}J_{n}(0)=J_{n}(\delta)=1,J_{n}(s)=0\big{)}=\lim_{r\to\infty}\mathbf{P}\big{(}J^{(r)}_{n}(0)=J^{(r)}_{n}(\delta)=1,J^{(r)}_{n}(s)=0\big{)}$
(3.64)
$\displaystyle=\lim_{r\to\infty}\mathbf{P}\bigg{(}\mathds{1}_{\big{\\{}\partial
B^{G^{0}_{n}}_{r}(V^{(l)}_{n})\neq\varnothing\big{\\}}}=\mathds{1}_{\big{\\{}\partial
B^{G^{\delta}_{n}}_{r}(V^{(l)}_{n})\neq\varnothing\big{\\}}}=1,\mathds{1}_{\big{\\{}\partial
B^{G_{n}^{s}}_{r}(V^{(l)}_{n})\neq\varnothing\big{\\}}}=0\bigg{)},$

and naturally, the analogous will hold for the complementary probability
$\mathbf{P}\big{(}J_{n}(0)=J_{n}(\delta)=0,J_{n}(s)=1\big{)}$. Hence, from the
proof of tightness from Theorem 1.6 it follows that

$\displaystyle\mathbf{P}(R_{1})\leq\mathbf{P}(S_{1})=o(\delta),$ (3.65)

with

$\displaystyle\mathbf{P}(S_{l})=\mathbf{P}(\text{two jumps in the
neighbourhood of $V^{(l)}_{n}$ in the $l$-th interval of length $\delta$}).$
(3.66)

Thus, the required condition holds.

Conclusion. Since all three conditions of Lemma C.1 hold, the convergence
follows. ∎

###  3.9 Proof of convergence of the size of the largest group in $[0,t]$

###### Proof of Theorem 1.9.

The proof consists of two parts. We start by deriving convergence in
distribution for $K^{[0,t]}_{\max}/n^{\frac{1}{\alpha}}$ and afterwards
proceed to show that
$\big{(}K^{[0,t]}_{\max}/n^{\frac{1}{\alpha}}\big{)}_{t\geq 0}$ and the
limiting process $\big{(}\kappa^{(0,t]}_{\max}\big{)}_{t\geq 0}$ satisfy
conditions of Lemma C.1, which will yield the desired convergence.

Part 1: Convergence in distribution. To shorten the computations in the next
part of the proof, we first derive convergence in distribution of the random
variable $K^{[0,t]}_{\max}/n^{\frac{1}{\alpha}}$. We compute

$\displaystyle\mathbf{P}(K^{[0,t]}_{\max}\leq
kn^{1/\alpha})=\mathbf{P}(\max\\{K^{\\{0\\}}_{\max},K^{(0,t]}_{\max}\\}\leq
kn^{1/\alpha})=\prod_{l>kn^{1/\alpha}}\prod_{a\in[n]_{l}}\pi^{a}_{\text{\rm{OFF}}}\cdot\mathbf{P}(\text{$a$
never ON in $(0,t]$}).$

Hence,

$\displaystyle\mathbf{P}$ $\displaystyle(K^{[0,t]}_{\max}\leq
kn^{1/\alpha})=\prod_{l>kn^{1/\alpha}}\prod_{a\in[n]_{l}}\frac{\ell_{n}^{l-1}}{\ell_{n}^{l-1}+l!p_{l}\prod_{i\in
a}w_{i}}\times\prod_{l>kn^{1/\alpha}}\prod_{a\in[n]_{l}}e^{-\frac{l!p_{l}\prod_{i\in
a}w_{i}}{\ell_{n}^{l-1}}t}.$ (3.67)

Note that

$\displaystyle\prod_{l>kn^{1/\alpha}}\prod_{a\in[n]_{l}}e^{-\frac{l!p_{l}\prod_{i\in
a}w_{i}}{\ell_{n}^{l-1}}t}=\prod_{l>kn^{1/\alpha}}e^{-t\sum_{j_{1}<...<j_{l}\in[n]}\frac{l!p_{l}\prod_{i\in
a}w_{i}}{\ell_{n}^{l-1}}}$ $\displaystyle=$
$\displaystyle\prod_{l>kn^{1/\alpha}}e^{-\frac{l!p_{l}t\ell_{n}}{l!}\sum_{j_{1},...,j_{l}\in[n]}\frac{w_{j_{1}}...w_{j_{l}}}{\ell_{n}^{l}}}=e^{-t\ell_{n}\sum_{l>kn^{1/\alpha}}p_{l}}+o_{\mathbf{P}}(1)=e^{-t\ell_{n}(kn^{1/\alpha})^{-\alpha}}+o_{\mathbf{P}}(1),$

which plugged into (3.67) yields

$\displaystyle\mathbf{P}$ $\displaystyle(K^{[0,t]}_{\max}\leq
kn^{1/\alpha})=e^{-t\ell_{n}(kn^{1/\alpha})^{-\alpha}}\prod_{l>kn^{1/\alpha}}\prod_{a\in[n]_{l}}\frac{\ell_{n}^{l-1}}{\ell_{n}^{l-1}+l!p_{l}\prod_{i\in
a}w_{i}}+o_{\mathbf{P}}(1).$ (3.68)

We have that

$\displaystyle\lim_{n\to\infty}\prod_{l>kn^{1/\alpha}}\prod_{a\in[n]_{l}}\frac{\ell_{n}^{l-1}}{\ell_{n}^{l-1}+l!p_{l}\prod_{i\in
a}w_{i}}=\lim_{n\to\infty}\prod_{l>kn^{1/\alpha}}\prod_{a\in[n]_{l}}\frac{1}{1+\frac{l!p_{l}\prod_{i\in
a}w_{i}}{\ell_{n}^{l-1}}}=1.$ (3.69)

Further, since $\mathbf{E}[W_{n}]\to\mathbf{E}[W]$ as $n\to\infty$,

$\displaystyle\lim_{n\to\infty}\ell_{n}(kn^{1/\alpha})^{-\alpha}=\lim_{n\to\infty}\frac{\ell_{n}}{k^{\alpha}n}=\lim_{n\to\infty}\frac{\mathbf{E}[W_{n}]}{k^{\alpha}}=\frac{\mathbf{E}[W]}{k^{\alpha}},$
(3.70)

we obtain for every $t\geq 0$

$\displaystyle\lim_{n\to\infty}\mathbf{P}\bigg{(}\frac{K^{[0,t]}_{\max}}{n^{1/\alpha}}\leq
k\bigg{)}=e^{-tk^{-\alpha}\mathbf{E}[W]}.$ (3.71)

Note that $g(k)=e^{-tk^{-\alpha}\mathbf{E}[W]}$ is a CDF of the Fréchet
distribution.

Part 2: Verifying conditions of Lemma C.1. We again check if our processes
fulfil conditions $(i)-(ii)$ of Lemma C.1.
Condition (i): Convergence of the finite-dimensional distribution. We want to
show that for all $\\{s_{1},...,s_{t}\\}\in[0,t]$ and
$k_{1},k_{2},...,k_{t}\in\mathbf{N}$, as $n\to\infty$,

$\displaystyle\mathbf{P}\bigg{(}\frac{K^{[0,s_{1}]}_{\max}}{n^{1/\alpha}}\leq
k_{1},\frac{K^{[0,s_{2}]}_{\max}}{n^{1/\alpha}}\leq
k_{2},...,\frac{K^{[0,s_{t}]}_{\max}}{n^{1/\alpha}}\leq
k_{t}\bigg{)}\longrightarrow\mathbf{P}\bigg{(}\kappa^{(0,s_{1}]}_{\max}\leq
k_{1},\kappa^{(0,s_{2}]}_{\max}\leq k_{2},...,\kappa^{(0,s_{t}]}_{\max}\leq
k_{t}\bigg{)}.$ (3.72)