IEEE Circuits and Systems Magazine - Q4 2021 - 15

m other individuals {, ,}, chosen uniformly
at random as an m-tuple in the population;
,,
iim
1
f
iii) undirected links (, h),ii hm1= f are added to
the edge set ();tE and
iv) the time index is increased by 1 step, and the algorithm
resumes from step i).
The formation process of an ADN is depicted in Fig. 8.
Note that, at each discrete-time, the network generated
by the ADN process is always undirected, but not necessarily
connected.
The main strength of this paradigm lies in its simplicity:
the temporal nature of the system is encapsulated in
a single n-dimensional vector. Such a simple formulation
has enabled the researchers to perform rigorous analytical
studies of the properties of the network generated
and of dynamical processes evolving on it. Specifically,
in [79], the following result has been established.
Theorem 5. Consider an SIS model on an ADN with
i V! Let us define the followmm
i
= and
nni
= for all
,
ing epidemic threshold:
v =
ma a
1
+
()
GH GH
2
,
.
(22)
For / 1mn v the epidemic is quickly eradicated with probability
converging to 1 as the network size
n " 3 while
for / 2mn v the epidemic becomes endemic with probability
converging to 1 as the network size n " 3.
The original formulation of ADNs was proposed in a
discrete-time framework, so the discrete-time counterpart
of the SIS model in Eq. (17) was studied. A continuous-time
formulation of ADNs has been proposed in
[80], where the synchronous activations ruled by the
activity-based mechanism are substituted by an asynchronous
mechanism, where each node is activated according
to a Poisson process with the rate equal to its
activity, yielding thus a Markov process. Therein, the
continuous-time SIS model is analyzed, giving rise to the
same threshold identified in Theorem 5.
One of the major advantages of the ADN formulation
is its simplicity that, besides enabling rigorous analytical
studies, allows to expand the formalism in several directions.
In fact, in the last few years, several extensions
and generalizations of the ADN paradigm have been proposed.
These extensions allow to include several features
of real-world complex systems in the model. The analytical
tractability of ADN-based models has enabled the rigorous
computation of the epidemic threshold for these
models and the characterization of their behavior, similar
to Theorem 5, shedding light on the role of these realworld
phenomena on the spreading of epidemics. These
extensions include the presence of preferential connectivity
patterns [81]-[83], community structures [84], [85],
heterogeneous propensity to receive connections [86],
FOURTH QUARTER 2021
.
memory and burstiness in the link formation process
[87]-[89], and high-order relations [90]. A detailed review
of the results for classical activity-driven networks and
for the explicit results of the epidemic thresholds for
these recent extensions can be found in [91].
D. Edge-Markovian Dynamic Graphs
A different approach, which to a certain extent combines
the presence of a connectivity pattern, determined
a-priori, and the stochasticity of its evolution, are edgeMarkovian
dynamic graphs. This paradigm has been
proposed in [92] to model stochastic evolution of dynamic
networks. In edge-Markovian dynamic graphs,
each potential link (edge) of the graph (i.e., each pair
(, )
ij VV#!
, with ij! ) is associated with a two-state
Markov chain (independent of the other links), where the
two states represent the existence and nonexistence of
the link, respectively. Two probabilities ,[ ,]pq 01!
are
defined so that, at each discrete time-step, the chain
switches from nonexistence to existence with probability
p, while the opposite transition happens with probability
q, as illustrated in Fig. 9. In plain words, the network
is initialized as a given (static) network. Then, each link
that exists at time t disappears at the following time-step
with probability q (independent of the others), while nonexisting
links at time t appear with probability p (independent
of the others). A continuous-time formulation of
the model can be obtained by substituting the Markov
chains with continuous-time Markov processes [93].
Epidemic processes on edge-Markovian dynamic graphs
have been proposed and studied in [93], [94]. Specifically,
in [94], the authors derived the value of the epidemic
threshold in terms of the basic reproduction number,
which has a complex expression. Edge-Markovian dynamic
graphs are amenable of several analytically tractable
extensions to overcome the limitations of their
original formulation. For instance, the Markov chain (or
process) underlying the network evolution determines
the inter-event time distribution for the appearance and
3
4
5
6
(a) t = 0
2
1
4
5
6
(b) t = 1
3
2
1
4
5
6
(c) t = 2
Figure 8. Exemplary evolution of a discrete-time ADN. At
discrete-time t = 0, node 2 is activated and generates m = 3
undirected links. At discrete-time t = 1, nodes 3 and 5 are activated,
generating m = 3 undirected links each. At discretetime
t = 2 none of the nodes is activated and, consequently,
no links are generated.
IEEE CIRCUITS AND SYSTEMS MAGAZINE
15
3
2
1
IEEE Circuits and Systems Magazine - Q4 2021

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q4 2021
