Dynamics in Networks
IV124
Josef Spurný & Eva Výtvarová
Faculty of Informatics, Masaryk University
May 12, 2023
Outline
Dynamics in Networks
dynamic processes on a static network
time-evolving network
static network in sliding window
temporal network – measures
temporal network – events in bursts
null models
network states
change points
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 2 / 29
Time-Evolving Networks
Time-Evolving Networks
Motivation
real networks are based on links that are subject to change in
time
static network does not represent information about the
sequence of steps and distance in time
communication networks, face-to-face interaction, neuronal networks,
ecological networks, interaction between species ...
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 3 / 29
Time-Evolving Networks
Time-evolving Networks – Motivation1
T = 240 min, a) ∆t = 60 min, b) ∆t = 30 min
1
Nicosia V., 2013
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 4 / 29
Time-Evolving Networks
2
network structure = riverbed
dynamic network = change of riverbed (friendship network)
temporal network = river flow (network of meetings and
communication)
2
Saramäki, 2014
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 5 / 29
Time-Evolving Networks
3
network structure = aggregation in time
dynamic network = existing links are active all the time
temporal network = existing links are switched on and off
3
Saramäki, 2014
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 6 / 29
Time-Evolving Networks
Temporal, Time-Varying Networks
G[0,T] ≡ G = {G1, G2, . . . , GM},
Gm – network snapshot
Commonly equidistant snapshots
tm+1 = tm + ∆t, m = 1, . . . , M.
G fully described by
adjacency matrix A(tm)
list of contacts (contact c = (i, j, t, δt) between nodes i, j, initial
contact 0 ≤ t ≤ T and its duration δt)
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 7 / 29
Time-Evolving Networks
Temporal Scale
Temporal window of size ∆t
∆t = T ...static network
∆t → 0 ...infinite sequence of instantaneous networks
Recommended: maximum possible temporal resolution
? Multiscale systems
→ Utilization of knowledge from signal processing, information
theory, time series analysis, granularity of the model, time series
segmentation, ...
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 8 / 29
Time-Evolving Networks
Temporal Scale – Interactions in a Class4
4
Bender-deMoll S., 2006, Sulo Caceres R., 2013
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 9 / 29
Sliding Window
Representing the temporal component
analyzing static networks in sliding window
5
temporal network analysis
5
Kondor D., 2014
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 10 / 29
Sliding Window
Topology Evaluation – Connectivity
temporally strongly connected component of node i: In a
directed graph, node i is temporally reachable from other nodes
of the component in the time interval [0, T], and all nodes of the
component are temporally reachable from i.
temporally weakly connected component of node i: Node i is
temporally reachable from other component nodes and vice
versa in the corresponding undirected temporal network.
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 11 / 29
Sliding Window
Metrics – temporal paths I.
Pij = {eik(t1), ekl(t2), . . . , exj(tL) | t1 ≤ t2 ≤ · · · ≤ tL}
topological/temporal path length = number of contacts/time
between i and j
temporal distance (latency) dij = temporal length of the shortest
temporal path
temporal diameter of the network D = maxijdij
no reciprocity: a path i → j doesn’t guarantee an existence of
path j → i
no transitivity: a path i → j and a path j → k don’t guarantee an
existence of path i → j → k
temporal dependence: a path i → j in a time t doesn’t guarantee
the same path in the time t′ > t
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 12 / 29
Sliding Window
Metrics – temporal paths II.
6
Nodes are often temporally unreachable from each other, i.e.,
dij = ∞, hence temporal (global) efficiency E = 1
N(N−1) ij
1
dij
6
Tang J., 2009.
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 13 / 29
Sliding Window
Metrics – clustering coefficient
= ability of events to persist across frames
- Ci(tm, tm+1) topological overlap of the node’s neighborhood
local clustering coefficient
Ci =
1
M − 1
M−1
m=1
Ci(tm, tm+1)
global clustering coefficient
C =
1
N
i
Ci
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 14 / 29
Sliding Window
Metrics – centrality7
betweenness: CB
i = j∈V k∈V,k̸=j
σjk(i)
σjk
Useful to take into account the interval during which
information waits at the node before being sent on
closeness: CC
i = N−1
j dij
broadcast, receive centrality:
not everything is spread via shortest paths
based on static Katz centrality (a version of eigenvector centrality
for directed graphs)
identification of spreaders and main recipients of information
7
Nicosia V., 2013, Holme & Saramäki, 2013, Newman, 2010, Grindrod &
Parsons, 2011
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 15 / 29
Sliding Window
Static vs. temporal centrality ENRON8
static ... corporate role in the organisation
temporal ... information dissemination and the role of information
mediators
8
Tang J., 2010. Analysing Information Flows and Key Mediators
through Temporal Centrality Metrics
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 16 / 29
Sliding Window
Metrics – community structure
rearrangement of cohesive groups
formation of new groups
fragmentation of existing ones
9
maximization of optimization function, parameters of spatial
and temporal resolution
9
Bassett D., 2013
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 17 / 29
Bursts
Burstiness10
temporal inhomogeneity
events cluster in time
B = στ −mτ
στ +mτ
mτ ...mean time between events
στ ...std of times
B = −1: periodic
B = 0: Poisson
B = 1: maximally bursty
An uncorrelated burstiness increases the latency of temporal paths.
10
Saramäki, 2014, Goh K.-L., 2008
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 18 / 29
Models of Temporal Networks
Models of Temporal Networks
Randomized null or reference models
used to interpret significance, to understand the effects of diverse
temporal and structural characteristics
A randomize a network in one way; the rest is kept as is
B normalized metrics
C z-scores of unnormalized metrics against normalized counterpart
there is no ’THE ONE’ null model (compared to static networks
with the configuration model)
Generative, mechanistic and predictive models
generative model to capture structure
mechanistic models that explain the evolution of large-scale
structures (temporal extensions to WS small-world, BA scale-free)
predictive models to forecast a graph behavior in the near future
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 19 / 29
Models of Temporal Networks
Reference (Null) Models I.
randomly permuted times
(DCW): disturbs all temporal
correlations, keeps static
topology and numbers of
contacts between node-pairs
random swaps of whole
sequences (DCB): disturbs
correlations between
neighboring events while
preserving a sequence
character and weights
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 20 / 29
Models of Temporal Networks
Small but slow world: how network topology and burstiness slow down spreading11
11
Karsai et al., 2011; D: configuration model – null model from a static network;
DCWB: as DCB but shuffles only sequences with the same number of events
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 21 / 29
Models of Temporal Networks
Reference (Null) Models II.
randomly shifted times in a
sequence: disturbs
correlations between
neighboring events, leaves
nodes sequences
random times in a sequence:
disturbs other correlations in
a sequence and between
sequences
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 22 / 29
Temporal Networks – Summary
Temporal Networks Summary
describes network topology and properties with respect to time
defined as a set of network slices tracking the flow of time
can use a fast temporal scale
... which is comparable with the temporal scale of dynamic
processes on a network
defines time-respecting paths
real-world systems exhibit small-world characteristics and
bursty timing of events
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 23 / 29
Change Points
Change-Point Detection
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 24 / 29
Change Points
Change-Point Detection II.12
12
Zhu, 2018
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 25 / 29
Network States
Network States
13
identification of stable states of a network
dwell-time, the fraction of total time spent in each state,
transition matrix
13
Husic, 2018
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 26 / 29
Network States
Sliding Window Approaches for Correlation Networks
sliding window approach (SW)
Pearson’s correlation
tapered sliding window approach (TSW)
weighted Pearson’s correlation
weights distributed according to Gaussian distribution
centered at t
dynamic conditional correlations (DCC)
Engle 200014
, Lindquist 2014
model-based multivariate method from GARCH family
estimates conditional variances and correlations
uses past values
14
https://escholarship.org/uc/item/56j4143f
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 27 / 29
Summary
Summary
An aggregated static network leads to
overestimating the number of paths and walks
underestimating the effective distances
BUT is essential for topological (rather than temporal) analysis.
Studying network dynamics allows us to
capture network topology evolving in time
identify network states
detect exact change points
asses temporal network properties and identify key nodes in
processes on a network
reveal real-life behavior of complex systems.
J. Spurný, E. Výtvarová ·Dynamics in Networks ·May 12, 2023 28 / 29