Objectives
- patterns in time series data.
Questions
- when is important to consider network dynamics in the study of dynamical processes on networks with changing topologies?
- to understand its formulation and change mechanism, find significant factors.
- what is the difference between a growing network and a general temporal network?
- growing: links appear
- temporal: links appear and disappear???
- Define what a temporal network is. Give an example for two different temporal networks that give rise to the same weighted, time-aggregated network.
- $t_1:a\to b, t_2:b\to c$
- $t_1: b\to c, t_2: a\to b$
- What is a second-order time-aggregated network? For the two temporal networks created above, construct the second-order time-aggregated networks and argue whether they are different.
- Give the definition of a causal path. When are causal paths transitive?
- How would you define a shortest and a fastest causal paths? Are these two notions the same? Provide an example temporal network that supports your answer.
Keywords
- temporal networks
- time-aggregated network
- second-order
- higher-order network models
- representation learning
- betweenness preference
- causal path
- shortest
- fastest
Research fields
- multi-layer networks: capture multiple relations between nodes.
- dynamic(temporal) network: study the sequence of links.
- time-aggregated network: assume that a link to exist whenever it occurs at any time.
Temporal network
We study temporal network to capture the complex effects introduced by the temporal dynamics of links
Components
- nodes
- time-stamped links (v,w;t)
We can represent it by a directed, acyclic graph.
Causal paths
$(v_0,v_1;t_1)\to(v_1,v_2;t_2)\to (v_2,v_3;t_3)\to \cdots\to(v_{l-1},v_l,t_l)$
the ordering of links matters!
Maximum time difference
\delta: we only consider the causal paths with time difference smaller than the maximum time difference.
It actually restricts the links we study.
Time-aggregated network
the static representation of temporal network.
- weight: the number of times a time-stamped link was active.
- transitive: paths in time-aggregated networks are transitive.
- by changing the ordering: we can get a same time-aggregated network from different temporal networks.
Problems
- A false sense of transitivity: since we discard all information on the ordering of links in the dynamic network, which influences causal paths.
- we use the time-aggregated network as a maximum entropy model.
- The power of its adjacency matrix doesn’t indicate the causal paths of length k.
Betweenness preference
it is
to identify for which paths differ from the expectation in the aggregate network.
to quantify how much they differ.
to measure the amount of information in terms of the ordering of links which is discarded when studying the time-aggregated network
Matrix based on directed, acyclic graph
$P^v: Nr.|S|\ast Nr.|D|$: dimension: the number of sources passing through node v times the number of destinations passing through node v, all $s\to v\to d$
$P^v_{sd}$: the joint probabilities of $S$ and $D$.
It should be defined under some given maximum time difference.
A null matrix can be built from the time-aggregated network.
$$
\hat{P}^v_{sd}=\frac{w(s,v)}{\sum_{s’}w(s’,v)}\cdot\frac{w(v,d)}{\sum_{d’}w(v,d’)}a
$$
Index: mutual information
$$
I^v(S;D)=\sum_{s,d}P^v_{sd}\log_2(\frac{P^v_{sd}}{P^v(S=s)P^v(D=d)})
$$
captures how much bits of information the sources provide for destinations when aggregating interactions around $v$.
if s and d are uncorrelated, the measure should be 0.
interpretation: does $v$ prefer to mediate paths between particular pairs of its neighbors.
Markovian
Markovian: the next step only depends on the current nostate, no more previous status.
if the betweenness preference of any node in the network is around 0, we call it Markovian temporal network.
$$
I^v(S;D)\simeq 0,\forall v\in V
$$
It means the time-respecting paths do not differ from what is expected from the time-aggregated network.
Transitivity
Paths in real systems are non-Markovian, thus breaking transitivity.
Betweenness preference
It can be judged by betweenness preference. In real network, many of them are far from 0.
A study of the betweenness preference distribution of nodes in real temporal networks confirms that time-respecting paths cannot be modeled as a simple memoryless stochastic process
Diffusion
temporal characteristics of dynamic networks alone can both slow down or speed up dynamical processes
- Non-markovianity slows down diffusion.
A simulation of ant colony indicates the slow-down factor of 2. That means the process in the temporal
network is about two times slower than in the static network.
the reason for that are that time-respecting paths in the real temporal network are longer than what one would expect in the static network
- London Tube: speeds up $S=0.25$
High-order model
It is to capture the length k of causal paths, for a given maximum time difference \delta.
- nodes: the links in the lower-orders model
- links (weights): the number of times the causal path occurs in the underlying sequence.
Expected 2-nd order topology/matrix
We can get the expected 2-nd order matrix based on the time-aggregated 1-st order network.
From this matrix and the actual number of outer-links of each node in the original 2nd order network, we can get the expected 2nd order topology.
Sensitive to ordering
the second-order network changes when time-stamped links are reordered while the first-order topology stays the same
Diffusion
The second eigenvalue of the transition matrix of the 2nd order network.
$$
S\simeq \frac{\ln|\lambda_2(\tilde{T})|}{\ln|\lambda_2(T)|}
$$
Question
From the node construction from a lower-order model, can we construct 3-order???? I think we can only construct $2^k$ order…….
