Temporal Network

Posted on 2023-05-18 Edited on 2023-05-18 In Literature Views: Symbols count in article: 9.5k Reading time ≈ 9 mins.

Temporal Network

本文是Petter Holme综述的总结

时序拓扑结构的measure

首先时序网络有两种构造方式：(i, j, t) 和(i, j, (t0, t1))

其次，measure可以有static网络的经典measure和结合时间的。

time-respecting paths and reachability
- 时序图是另一种有向图
- the set of influence of i
- reachability ratio: 一段window内，node可达node的平均比例
  - 个人想法：可以用过去一段时间某个node的ratio作为中心度衡量
- source count: i的source set
time path with limits on waiting times
- 不同的网络，waiting time大不同
connectivity
- 强连通(每两个node都有directed time path)和弱联通
  - 定义需要定义time window
- transitive connectivity
Distance, latency, fastest path
- 空间上有shortest path
- 时间上有latency（多久能从i到j）和duration（作用持续多长）
  - latency：age of info
    - vector clock: $\left[\phi_{i, t}(1), \ldots, \phi_{i, t}(N)\right]$
  - forward latency:
  - average latency: = velocity
- edge activation sequence v.s. vertex activation sequence
- 个人想法：
  - 信息传输效率
  - 对信息进行时间加权
Diameter
1. diameter: largest distance
2. network efficiency:
  - average over path length
  - harmonic average of the latency: combines average latency and reachability ratio
Minimum spanning tree
- time sub-interval minimum spanning tree: 最小average latency
centrality
- closeness centrality $C_C$: $C_C(i)=\frac{N-1}{\sum_{j \neq i} d(i, j)}$
- temporal closeness centrality \[ C_C(i, t)=\frac{N-1}{\sum_{j \neq i} \lambda_{i, t}(j)} \]
efficiency \[ C_E(i, t)=\frac{1}{N-1} \sum_{j \neq i} \frac{1}{\lambda_{i, t}(j)} \]
betweenness centrality $C_B$: $C_B(i)=\frac{\sum_{i \neq j \neq k} v_i(j, k)}{\sum_{i \neq j \neq k} v(j, k)}$
- define temporal boundaries
- to use the whole observation period, or only consider the fastest time-respecting paths that begin at times closest to t at each vertex j.
eigenvector centrality
- the algorithm of a generalization of the eigenvector centrality:
  1. Start with a centrality value 1 at each vertex.
  2. At every contact between vertices $i$ and $j$, let the $C_E$ values after the contact at timestep $t$ be
  \[ C_E^{t+1}(i)=\zeta C_E^t(i)+(1-\zeta) C_E^t(j) \]
  
  and \[ C_E^{t+1}(j)=\zeta C_E^t(j)+(1-\zeta) C_E^t(i) \]
- can stuck at vertices
- To make the contribution uniform over time, one can normalize the score after every timestep (or, equivalently, increase the added value so that it is a constant fraction of the total centrality score).
Katz centrality
PageRank
Persistent patterns
- define subgraphs that are persistent in temporal networks. They define the support set $S\left(G^{\prime}\right)$ of a subgraph $G^{\prime}$ (where $G^{\prime} \subseteq G_t$ is a subgraph of $G_t$-the graph of all edges active at time $t$ in a temporal graph) as the set of timesteps when $G^{\prime} \subseteq G_t$. They go on to define a "frequent" subgraph that we rather call a persistent subgraph as a graph that has a support larger than a certain threshold value. The authors have subsequently developed a method of detecting periodic patterns among subgraphs using the support set concept.
- support set: $G_t$的子集，要满足一个阈值。紧接着试图从中找出一些periodic pattern
- interval graph的特征往往和window有紧密的联系
- adjacency correlation function：

\[ \gamma_i(t)=\frac{\sum_{j \in \phi(i, t)} a(i, j, t) a(i, j, t+1)}{\sqrt{\sum_{j \in \phi(i, t)} a(i, j, t)} \sqrt{\sum_{j \in \phi(i, t)} a(i, j, t+1)}} \]

Motifs（检测网络中一些pattern）
- two contact events $e_i$ and $e_j$ are adjacent if they share a vertex, and they are $\Delta t$-adjacent if additionally their time difference is no larger than $\Delta t$.
- Further, two events $e_i$ and $e_k$ are $\Delta$-connected, if there exists a sequence of $\Delta t$-adjacent events joining $e_i$ and $e_k$.
- similarity of the temporal order of events
- temporal subgraphs map to static directed graph
- 时间网络 → 时间聚类网络
- temporal motifs have causal explanation: Kovanen et al.
- over- under- representation 导致信息丢失
- reoccurance for some vertexs set
Mersuring inter-contact times and burstiness
- 突发事件：Poisson process
- Nodes (edges) are binned according to their numbers of contacts, and the inter-contact time distributions are scaled by the average inter-contact time in each bin, $P\left(\tau / \tau^*\right)$. 并呈现厚尾形式
- Measure of burstness from sequence of inter-contact times.
  
  Coefficient of varition: defined as the ration of the standard deviation of the intercontact times to their mean, $\sigma_\tau / m_\tau$. For a Poissonian contact sequence, $\sigma_\tau / m_\tau=1$. Using this quantity, the burstiness of a sequence is then defined as \[ B=\frac{\left(\sigma_\tau / m_\tau-1\right)}{\left(\sigma_\tau / m_\tau+1\right)}=\frac{\left(\sigma_\tau-m_\tau\right)}{\left(\sigma_\tau+m_\tau\right)} \] For finite contact sequences, the variance is always finite, and $B \in(-1,1)$, such that $B=1$ indicates a most bursty sequence, $B=0$ a sequence with Poissonian inter-contact times, and $B=-1$ a completely periodic sequence.
Entropies and other information-theoretic measures
- Blackmore and Hanlen’s entropy-based method to account for temporal uncertainties in communication networks
- “ascendency” to quantify how well a system process its environmental input

Representing Temporal Data as Static Graph

map dynamic SIR model to static edge percolation model
- takes into account the temporal correlations and infomogeneities of edges
Reachability graph
- directed graph
  - average degree k
- line graph of G
  - vertices are edges of G, if share vertex in G
  - structure of concurrent partnership
Transmission graph
- A graph where an edge $e$ is active over an interval $\left[t_{\text {start }}(e), t_{\text {stop }}(e)\right]$. There is a directed edge from $e$ to $e^{\prime}$ in the transmission graph if $e$ and $e^{\prime}$ share a vertex, $t_{\text {start }}(e)<t_{\text {start }}\left(e^{\prime}\right)+\delta$ and $t_{\text {start }}\left(e^{\prime}\right)<t_{\text {start }}(e)$.

Models for temporal networks

Temporal exponential random graph
- probability of a contact to happen between a pair of vertices at a given time.
- measure quantities of topological and temporal structure
Models of group dynamics
- 区间图：基于master(or 'rate') equations，捕捉expected change in the number of people in a group of a certain size.
- 时点图：find community of strong ties with weak links
Contact network models
- model：
  1. 1. A new partnership is formed with probability $\rho$. The individuals participating in the pair are chosen according to the mixing function $\phi$ :
    1. draw two random individuals $i$ and $j$;
    2. decide whether they form a pair according to $\phi(i, j)$
    3. if yes, done; else go to $i$.
    1. Repeat step 1a $ N / 2-P$ times.
  2. In every pair consisting of a susceptible(易感者) and an infected(感染者), the disease is transmitted with probability $\eta$.
  3. Every pair splits up with probability $\sigma$.
- mixing function: (assortative 同源) high degree vertex tend to connect with high
  
  \[ \phi(i, j)=1-\xi+\xi \frac{k_i k_j}{k_{\max }^2} \]
- mixing function: (disassortative) high degree vertex tend to connect with low \[ \phi(i, j)=1-\xi+\xi \frac{\left(k_i-k_j\right)^2}{k_{\max }^2} \]
- 现代方法：draw degree from a distribution(power-law degree distribution) and connect them with a function like $/phi$
Randomized reference models

对于static network，评估importanceof topological features的方法：compare features with reference model（随机生成的）
时序网络：设计temporal null model，看特征的贡献（随机生成或者remove某些特定correlation），下面介绍一些temporal null models
1. Randomized edges：研究拓扑结构的影响，保留了总的degree、时序的correlation、distribution。
2. Go over all edges sequentially.
3. For every edge $(i, j)$, pick another edge $\left(i^{\prime}, j^{\prime}\right)$.
4. With a probability $1 / 2$ replace $(i, j)$ and $\left(i^{\prime}, j^{\prime}\right)$ by $\left(i, j^{\prime}\right)$ and $\left(i^{\prime}, j\right)$, otherwise replace them by $\left(i, i^{\prime}\right)$ and $\left(j, j^{\prime}\right)$.
5. If the move in step 3 created a self-edge or multiple edge, then undo it and start over from step 2 .
6. Randomly permuted times (RP)：研究event order、distribution、correlation and effect
  
  Permute the contact times randomly while keeping the network structure and the numbers of contacts between all pairs of vertices fixed.
7. Randomized edges with randomly permuted times (RE + RP)：
  
  先用RE randomize，再shuffle timestamps of all contacts
8. Random times (RT)：每个contact of edge被分配时间窗口内的随机时间。generating from chosen distribution.
9. Randomized contacts (RC)：keeps the graph topology fixed but redistributes the contacts randomly among the edges. 每个edge的contact数量符合binomial distribution。可以研究这些分布。
10. Equal-weight edge randomization (EWER)：再具有相同contact的边之间随机交换。消除相邻边的接触序列之间的时间相关性，同时保留与边相关的时间特征，包括单个边上的接触间时间分布。问题在于系统要足够大，足够多具有相同时间数量的边。
11. Edge randomization (ER)：the sequences can be exchanged between edges that have any numbers of contacts.
12. Time reversal (TR)：评估frequency和causal sequences of contacts

SPREADING DYNAMICS AND COMPARTMENTAL MODELS ON TEMPORAL GRAPHS

SIR模型（Susceptible-Infective-Removed）显示了更丰富的动态变化。在这个模型中，受感染的个体在单位时间内以某种概率$\beta$或在固定的时间段后恢复并变得对传播有免疫力。现在SIR动态的结果取决于两个速率（感染率$\mu$和恢复率$\beta$）以及网络结构之间的相互作用。
传播的过程具有异质性，例如传播方式的不同，另外存在互动事件引起进一步事件的相关性。
交流事件不一定符合Poisson或者uniform，可以用厚尾或者power law来描述。
In the Poisson approximation泊松估计, the probability of one vertex to interact with another within a time interval $d t$ is $d t /\langle\tau\rangle$, where $\langle\tau\rangle$ is the average interevent time. Thus, the time between consecutive contacts is exponentially distributed, $P(\tau) \sim \exp (-t /\langle\tau\rangle)$. However, for the email data studied by Vazquez et al., after correcting for finite observation window, it was seen that $P(\tau) \sim 1 / \tau$, followed by an exponential cutoff.
broad inter-event time distribution，符合计算机蠕虫病毒的传播数据（prevalence dynamics of the SI model）
Later, Min, Goh and Vazquez [106] studied the SI model with 幂律时间间时间分布(power-law inter-event time distributions) using theoretical arguments that assume a tree-like network structure, as well as with simulated spreading with uncorrelated power-law activity patterns and the priority-queue network model. They concluded that a power-law waiting time distribution leads to a power-law decay in the number of new infections in the long time limit, with an exponent determined through the generation time distribution. 这篇论文用树模型研究传播特征，不太适合股票网络，因为病毒感染基本是单向的，而股票网络的影响是双向的。
Iribarren和Moro的营销模型中，响应时间（接收和转发之间的时间）被认为是遵循对数正态分布。
Fernandez-Gracia et al. [46] studied the effect of broad inter-event time distributions on the ordering dynamics of the Voter model
Burstiness and other temporal and structural inhomogeneities
- Karsai et al. [71] provided further insight into the effect of temporal heterogeneities on spreading dynamics by studying the behavior of the SI model. 电话呼叫数据库，3亿多数据。interevent times have broad distribution
- Miritello et al. [107]将SIR model map到静态网络，并且估计了dynamic transmissibility（二次感染平均值）
- SI传播的速度--特别是在确定的情况下，即感染者总是在接触后感染易感者--与时间路径的长度、延迟和可及性有关[59, 120]
Utilizing temporal structure for disease control
- 随机抽取一个人，name一个人，然后打疫苗，直到理想比例的人被接种疫苗。首先是按照degree k的比例抽样，经典理论：这个人对疾病传播的importance是$k^2$，感染其他人的于其数量也与k成正比。
- contact可以分为最近和最频繁的接触。