大数据管理与应用系列丛书《复杂网络》（吕欣等著）读书笔记-时序网络
在线开源学习地址https://github.com/XL-lab-bigdata/ComplexNetworks什么是时序网络带你了解随时间变化的动态网络世界在我们日常生活中无论是微信朋友圈的互动、公交车路线的变化还是人与人之间的接触行为背后都隐藏着一个个复杂而又动态的网络结构。这类网络并不是一成不变的而是随着时间不断变化我们称之为时序网络。为什么要研究时序网络传统的网络分析方法通常把整个网络看作一个静态的整体——就像拍下一张全景照片。但在真实世界里网络是“活”的新的节点不断加入旧的连接随时间消失人与人之间的互动也可能只发生在特定时段。如果我们忽略这些时间信息把时序网络静态化处理可能会出现什么问题呢举个例子在一个社交网络中如果我们不考虑消息传递的先后顺序就可能错误地认为某些连接具有“传递性”从而影响信息传播、社群划分、甚至未来连接的预测。所以我们必须把时间“装”进网络里才能更真实地还原网络的演化过程和内部规律。时序网络都研究什么在时序网络的研究中通常包括以下几个关键内容1. 建模方式我们首先要思考的是**如何建模一个时序网络**不同的建模方式适用于不同的应用场景。常见的方式包括时间戳网络Time-stamped Network、时序图Temporal Graph、滑动窗口法Sliding Window等每种方法在保留时间信息的同时也要兼顾分析的效率和清晰度。2. 网络指标在静态网络中我们常用“度”、“聚类系数”、“最短路径”等指标来描述网络结构。那么在时序网络中这些指标还能用吗当然可以但我们也需要引入新的、考虑时间因素的指标比如时间相关的中心性、时间路径长度等来更准确地刻画动态演化的特征。3. 关键节点识别哪些节点在时序网络中起着至关重要的作用这类问题对于疫情传播控制、舆情引导等场景具有重要意义。我们可以根据节点的活跃时间、传播速度等多种维度来识别“关键玩家”。4. 网络生成模型除了分析已有网络我们也关心**这些时序网络是如何形成的**通过构建生成模型我们可以更好地理解网络的演化机制并预测其未来的变化趋势。5. 动力学过程随机游走 疾病传播在时序网络中很多经典的网络过程也变得更加复杂。比如随机游走Random Walk在时序网络上会受到时间约束的影响而疾病传播模型如SIR模型也需要考虑个体接触的时间顺序这些都会对最终传播范围和速度产生显著影响。常见的时序网络建模方法有哪些1. 标签图我们可以把时序信息“贴标签”地加在网络的连边上这就是标签图的思想。怎么做在网络中每条边不仅连接两个节点还附带一个时间信息比如说“节点 A 在时间 t 与节点 B 有过交互”。其 简单直观适合展示节点之间在特定时刻发生的联系。但无法很好地描述边的出现与消失过程也无法体现网络的动态变化全貌。因此它更适用于小规模、低频交互的网络。小贴士标签图其实更像是给网络“打上时间戳”虽然能看时间但不能看过程。2. 时线图如果我们希望更清楚地看到网络交互是如何随时间演变的那么时线图可能是一个更好的选择。两种方式A不考虑交互时长的时线图每个节点用一条水平线表示时间沿水平方向流动。如果某两个节点在某一时刻发生了联系用一条垂直线连接它们的时刻点即可。适合用于展示“事件发生的时间点”。B考虑交互时长的时线图如果交互持续了一段时间我们就用一段水平的矩形表示。比如从 t2 到 t5 的交互就是一个从时间轴2延伸到5的矩形条。其特点在于非常直观能够看到节点之间交互的先后、频率以及持续时间等信息。网络规模一旦变大节点数量和交互频率上升图会变得非常复杂难以可视化和分析。小贴士时线图适合讲故事比如“谁先跟谁联系”“联系了多久”这些细节非常适合对时间敏感的传播过程建模。3. 快照序列当我们需要处理更大规模、更复杂的网络时快照序列可能是最常用的建模方法。怎么做把整个时间轴按照固定的时间窗口比如每5分钟进行切分然后在每个时间段内构建一个静态的网络“快照”。举个例子如果我们有一个从0到30分钟的交互数据并设置时间窗口为10分钟那我们就会得到3个快照网络0-10 分钟、10-20 分钟、20-30 分钟。如何判断是否在某个快照中连边存在只要一个交互事件发生在这个时间窗口内、或跨越了这个窗口就会在对应的快照图中保留它。其容易实现适合大规模网络分析。还可以用三维邻接矩阵进行建模便于算法计算。但网络动态细节被“窗口粗化”不同的时间窗口长度会影响最终的分析结果——窗口太大可能忽略了微小变化太小则会产生过多的重复信息。小贴士快照序列就像把动态电影切成一帧帧的静态画面适合整体趋势分析但不适合追踪具体细节。4. 时间顺序图时间顺序图其实就是把一个时序网络一个随着时间变化的网络转成一个静态的网络。简单来说它通过将网络的每个时间点看成一个独立的快照把这些快照串起来来展示网络在不同时间点上的状态。怎么做我们假设网络的时间分辨率是1即每个时间单位就对应一个“快照”。然后把时序网络分成多个静态网络每个静态网络表示某个时刻的网络情况。每个快照内节点之间不会有连边只有相邻的时间点之间才会有连边把这些连边看作是“时序路径”。比如图9-4所示的虚线表示从一个时间段到下一个时间段的连接。虽然这种方法能清晰地显示不同时间点上节点的关系但它也有个问题就是会产生大量重复的数据尤其是当网络很大时处理起来会非常复杂。5. 多层网络多层网络是一种将时序网络划分为多个时间层的建模方式。每一层代表时序网络在某个特定时刻的状态而层与层之间通过时序关系来连接表示不同时间点之间的节点相互关系。怎么做假设时序网络有N个节点时间分辨率是Δt那么就可以把网络分成T层每一层代表某个时间点的网络结构。每层内节点之间的连边可以用传统的邻接矩阵表示层与层之间的连接关系则通过“层间关联矩阵”表示。举个例子如果某一时刻节点A和节点B有连接而在另一个时刻节点A和节点C有连接那么层间关联矩阵就能够表示A、B和C在不同时间点之间的时序关系。时序网络指标时序网络的分析离不开一些关键的指标它们帮助我们理解网络中节点间的交互关系、传播效率以及网络的稳定性。下面我们来了解一些重要的时序网络指标包括时序路径、时序距离、时序效率和拓扑重复率与时序相关系数。1. 时序路径时序路径是在时序网络中从一个节点到另一个节点的时间顺序路径。它不仅仅是连接节点的路径更重要的是这条路径上的节点交互必须按照特定的时间顺序发生。例如假设我们有三个节点A、B和C如果A到B的交互发生在B到C之前那么从A到C的时序路径就有效。而反过来B到A可能不成立因为时间顺序不符合。时序路径的关键特点是它不具有可逆性和传递性。换句话说虽然从节点A到节点B可能存在时序路径但从节点B到节点A不一定能找到时序路径。因此时序路径的定义适用于任意时序网络模型它是理解时序网络中节点间交互的基础。2. 时序距离时序距离是指两个节点之间的时序最短路径即通过最短的时序路径从一个节点到达另一个节点所需要的时间。具体来说时序最短路径是连接两个节点的路径中交互起始时间的差异最小的路径。时序距离的一些相关定义包括时序直径时序网络中所有节点对之间的最大时序距离表示网络中最远的两个节点之间的时序距离。平均时序距离所有节点对之间时序最短路径的时序长度的平均值。需要注意的是时序网络中可能存在一些节点对之间无法通过时序路径到达的情况这时平均时序距离会趋向于无穷大。3. 时序效率时序效率是指时序网络中信息传播的效率通常通过时序距离的简谐平均Harmonic mean来衡量。时序效率越高表示网络中节点之间的时序距离越短信息传播越快速。简单来说时序效率越高网络中节点之间的联系越紧密信息能够更快地传播。时序效率是一个重要的网络性能指标尤其在分析信息传播、流量控制等问题时非常有用。4. 拓扑重复率与时序相关系数拓扑重复率表示在两个相邻的时间片段中节点与其邻居之间连边存在的概率。即在一个时间片段内某节点与它的邻居是否保持连接在下一个时间片段中是否继续保持这种连接。拓扑重复率的计算方法是拓扑重复率衡量节点在相邻时间窗口之间是否与同样的邻居保持连接。平均拓扑重复率表示节点在整个时间段内保持与邻居连边的平均概率。时序相关系数则是网络中所有节点的平均拓扑重复率的平均值。这个系数反映了整个网络中节点之间的稳定性。如果时序相关系数为1表示网络在不同时间片段之间没有变化时序网络退化为静态网络如果时序相关系数接近0说明时序网络在不同时间窗口之间变化非常快节点之间的连接关系不稳定。时序网络中心性指标时序网络中的节点中心性是指衡量节点在网络中重要性的指标它们通常是静态网络节点中心性概念的扩展。在时序网络中主要有四种常见的时序中心性指标时序介数中心性、时序接近中心性、广播中心性和接收中心性。这些指标帮助我们理解节点在时序网络中的信息控制能力、传播能力和接收能力。1. 时序介数中心性时序介数中心性衡量的是一个节点在网络中作为信息传递中介的能力。它基于节点对之间的最短时序路径的数量节点的介数中心性越高说明该节点在信息传递过程中越关键。具体来说时序介数中心性是通过计算所有节点对之间经过该节点的最短时序路径数量与所有最短时序路径总数的比值之和来确定的。公式如下C B ( v i ) ∑ j ≠ i , k ≠ i B ( v i , j , k ) C ( i , j , k ) C_B(vi) \sum_{j \neq i, k \neq i} \frac{B(vi, j, k)}{C(i, j, k)}CB(vi)ji,ki∑C(i,j,k)B(vi,j,k)其中B ( v i , j , k ) B(vi, j, k)B(vi,j,k)表示从节点j到节点k经过节点v i vivi的时序最短路径数量C ( i , j , k ) C(i, j, k)C(i,j,k)表示从节点j jj到节点k kk的所有最短时序路径数量。除了最短时序路径外时序网络中的介数中心性还需要考虑信息在路径上传递时的停留时间。通过考虑节点的停留时间时序介数中心性可以更准确地反映节点的重要性。例如假设节点A和节点B之间的路径是唯一连接的如果通过节点C传递信息那么信息将在C上停留一段时间。这种停留时间会影响信息的传递效率从而影响时序介数中心性的计算。2. 时序接近中心性时序接近中心性衡量的是一个节点到达其他所有节点的平均时序距离。时序接近中心性越高表示该节点能够更快速地传播信息到其他节点。具体来说时序接近中心性是节点到其他节点的时序距离的倒数。公式如下C C ( v i ) 1 ∑ j ≠ i λ i j ( t ) C_C(vi) \frac{1}{\sum_{j \neq i} \lambda_{ij}(t)}CC(vi)∑jiλij(t)1其中λ i j ( t ) \lambda_{ij}(t)λij(t)表示节点v i vivi到节点v j vjvj的时序距离时序接近中心性较大的节点意味着其可以较快地到达网络中的其他节点。如果网络中存在一些节点之间无法通过时序路径到达的情况这会影响时序接近中心性的计算。因此时序接近中心性也可以通过调整公式忽略这些不可达的节点。3. 广播中心性与接收中心性广播中心性和接收中心性是通过时序网络的传播矩阵来定义的。传播矩阵基于节点间不同长度的时序路径度量了节点间相互到达的可能性。广播中心性衡量一个节点将信息传播到其他节点的能力。具体来说广播中心性计算节点在整个时序网络中能传播信息到其他节点的能力。公式如下C Broad ( i ) ∑ j Q i j C_{\text{Broad}}(i) \sum_{j} Q_{ij}CBroad(i)j∑Qij接收中心性衡量一个节点接收来自其他节点信息的能力。接收中心性计算的是节点能从网络中其他节点接收到信息的能力。公式如下C Recv ( i ) ∑ j Q j i C_{\text{Recv}}(i) \sum_{j} Q_{ji}CRecv(i)j∑Qji通过传播矩阵的计算广播中心性和接收中心性为我们提供了一个网络中节点对信息传播和接收的控制能力的量化指标。4. 时序网络的连通性在时序网络中节点间的连通性非常重要。时序网络的连通性有时不具备传递性因此在分析时序网络时我们需要特别关注节点间的时序强连通和时序弱连通。时序强连通如果在有向时序网络中从节点A到节点B有时序路径且从节点B到节点A也有时序路径则称节点A和节点B是时序强连通的。时序弱连通去掉时序网络的有向性得到一个无向时序网络。如果在这个无向网络中节点A和节点B之间有路径可达则称它们是时序弱连通的。此外时序网络中的时序出连通分支和时序入连通分支也非常重要。时序出连通分支指的是从节点出发能够到达的所有节点集合而时序入连通分支则是指能到达节点的所有节点集合。时序出连通分支从时序网络中的某个节点出发能够通过时序路径到达的所有节点所构成的集合称为时序出连通分支。它表示从某个节点出发通过时序路径可以传播信息的范围。时序入连通分支与时序出连通分支相反时序入连通分支是指能够通过时序路径到达某个节点的所有节点构成的集合。它表示哪些节点能够接收到来自某个节点的信息。时序强连通分支SCC在有向时序网络中时序强连通分支是指时序出连通分支和时序入连通分支的交集。也就是说时序强连通分支表示的是那些可以互相到达、并且存在双向时序路径的节点集合。时序弱连通分支WCC时序弱连通分支则是在无向时序网络中通过节点间不考虑方向的路径来定义的连通分支。它是由时序网络中时序出连通分支和时序入连通分支的交集构成。时序网络关键节点识别时序网络中的关键节点识别是帮助我们找到那些在信息传播、资源分配等过程中起到重要作用的节点。这些节点对于网络的运行效率和稳定性至关重要。与静态网络不同时序网络不仅需要考虑节点的拓扑位置还要结合时间因素。下面我们来讨论几种基于拓扑结构的时序网络关键节点识别方法。1. 基于时序网络指标的关键节点识别这一方法基于时序网络中的重要性指标如时序介数中心性、时序接近中心性等对节点进行排序从而识别出关键节点。与静态网络相比时序网络指标需要考虑时间对节点交互的影响例如信息传播的时间衰减和路径长度。时序介数中心性衡量节点在信息传播过程中的中介作用即一个节点通过多少时序路径连接了其他节点。时序接近中心性表示节点到其他节点的平均时序距离的倒数接近中心性高的节点通常意味着其能够更快速地与其他节点建立联系。这些时序中心性指标可以帮助我们评估哪些节点在网络中对信息流动、传播和控制具有更高的影响力。2. 基于 k-壳分解的关键节点识别k-壳分解方法源自静态网络的k-核中心性应用于时序网络时通过将网络分割成多个时间窗口中的静态网络然后计算每个节点的时序k-核值来识别关键节点。时序k-壳Temporal k-shellTK通过k-壳分解得到每个节点在不同时间窗口内的k-核值并将这些值作为节点的重要性指标。每条边的权值是通过节点之间的k-核值最小值来决定的最终通过所有时间窗口上的加权边的总和来计算节点的时序k-核值。平均时序k-壳TKD将节点在各时间窗口中的时序k-核值除以节点在静态网络中的度进一步优化节点重要性的识别。平均静态k-壳ASK对时序网络中的每个快照进行k-壳分解并计算所有快照中节点的k-核值的平均值。这有助于识别那些在所有时间点上都表现出较高重要性的节点。这种方法适用于那些依赖于网络节点间长期联系的场景因为它能够综合考虑节点在多个时间段内的相对重要性。3. 基于特征向量的关键节点识别基于特征向量的关键节点识别方法主要通过构建时序网络的多层结构利用邻接张量来衡量节点在不同时间层上的重要性。通过计算节点在时间层内和层间的耦合强度识别出关键节点。联合中心性在特定时间层节点的中心性反映了节点和时间层的结合重要性。通过计算主特征向量中的元素来量化节点的重要性。边际节点中心性这是对节点在整个时间窗口长度内的重要性进行度量通过计算节点在所有时间层上的联合中心性之和来得出。边际时间层中心性衡量一个时间层在整个时序网络中的重要性。它表示了时间层内所有节点的联合中心性的总和。条件中心性反映特定时间层中节点相对于其他节点的重要性。这有助于识别哪些节点在特定时刻对网络中的信息传播具有更大影响力。这种方法的优势在于它能够提供较为精细的时序网络节点重要性分析特别是在不同时间快照中节点的表现可能会有所不同。它能够有效识别出在某些时刻或时间段内特别重要的节点。4.基于动力学的方法除了基于拓扑结构的识别方法基于动力学的方法通过模拟网络中信息或疾病的实际传播过程直接量化节点的真实影响力。这类方法往往能够捕捉到静态或结构性方法难以发现的时序传播特性。这里主要介绍两种思路TempoRank和传播动力学评估。(1)TempoRankTempoRank是将经典的 PageRank 概念扩展到时序网络的一种方法。它基于时序网络上随机游走者的长期分布稳态密度来评价节点的重要性。简单来说想象有一个随机游走者在时序网络中随时间移动它按照网络结构和交互频率在节点之间转移。当时间无限长、或者周期性重复网络快照时游走者会达到某种稳态分布。某节点的 TempoRank 值越高意味着在长期中游走者停留在该节点的概率越大这个节点在时序网络中的影响力越大。TempoRank 不再局限于最短时序路径它综合考虑了所有可能的传播路径包括非最短路径因此能够更全面地衡量节点对信息流的实际贡献。TempoRank的关键步骤将时序网络分割为快照序列在每个快照中构建随机游走的转移概率矩阵周期性地串联这些快照形成周期性边界条件通过矩阵连乘得到稳态密度用特征向量表示平均周期内的稳态密度作为 TempoRank 值。TempoRank 的优点是它天然地融入了节点活跃度、交互频率和交互时间顺序等信息而这些是简单的静态指标无法捕捉的。(2)传播动力学评估传播动力学方法并不是直接识别关键节点的方法而是用来验证和评估关键节点识别方法是否有效。思路是在时序网络上建立传播模型比如流行的 SI易感-感染、SIS易感-感染-易感、SIR易感-感染-恢复模型通过仿真传播过程看不同节点作为初始传播源时能传播到多少节点、传播的速度、或传播所需的时间等节点在这些传播过程中表现得越具影响力就说明它在网络中的传播能力越强也就越关键。具体评估方式包括感染规模用单个节点作为感染源观察最终能感染多少节点数量越大说明该节点越关键。传播平均距离传播覆盖网络所需的平均时间/步数越短表示节点传播能力越强。半感染时间单节点作为传播源时需要多长时间感染一半节点时间越短节点越关键。免疫仿真将一个节点“移除”相当于免疫该节点比较移除前后网络中感染规模或感染时间的变化。如果移除某节点让传播大幅减缓或减少说明该节点在网络中具有重要影响。这类方法的核心优势是直接基于传播过程本身结果具有高度的实际参考价值。其缺点是需要进行大量传播仿真计算成本较高尤其在大型时序网络中需要较长时间。时序网络模型时序网络模型是为了帮助我们理解和模拟真实世界中动态系统的演化过程。它们能再现节点之间随时间不断变化的交互关系并提供分析时序网络结构和行为的基础。在这一小节中我们介绍随机时序网络模型以及它如何基于静态网络引入时间信息来生成动态网络。随机时序网络模型把静态网络“动”起来随机时序网络模型的核心思想是在给定的静态网络结构上随机生成每条边的激活时间事件何时发生和事件的持续时间交互持续多久从而将原本“死板”的静态网络变成随时间变化的动态网络。用一个形象的例子来说假设静态网络中的每条边是“可能会发生的联系”随机时序网络模型就相当于在每条边上安排交互“剧本”什么时候开始、持续多久。最终生成的时序网络就像一场在固定演员节点之间上演着各自独立剧情交互时间线的动态表演。模型构建步骤随机时序网络模型的构建可以分为以下几个步骤生成静态网络使用配置模型等方法生成一个无重边、无自环的静态网络G GG这是时序网络的骨架。分配激活时间区间为每条边随机生成一个时间区间表示它可能在这个时间范围内被激活。生成IET序列根据预设的事件间隔时间分布IETInter-Event Time为每条边生成多次交互的起始时间序列图9-12C。匹配交互时间将生成的事件序列随机匹配到每条边的激活区间内根据区间大小合理分配交互起始时间图9-12D。生成时序网络去掉激活区间后保留边上所有交互的起始时间信息得到包含交互事件但不含持续时间的时序网络图9-12E。分配交互时长为每次交互生成服从事件持续时间分布EWTEdge Waiting Time的持续时间并分配到每条边最终生成完整的随机时序网络。最终每条边由多次交互事件组成表示为四元组{ ( i , j , t i j l , Δ t i j l ) } \{(i, j, t_{ij}^{l}, \Delta t_{ij}^{l})\}{(i,j,tijl,Δtijl)}其中i , j i,ji,j是交互节点对t i j l t_{ij}^{l}tijl是第l ll次交互的起始时间Δ t i j l \Delta t_{ij}^{l}Δtijl是第l ll次交互的持续时间。活动驱动模型活动驱动模型是描述时序网络动态演化的模型之一它通过引入活动或活跃潜力来生成时序网络中的节点交互。与静态网络模型相比活动驱动模型能够有效地捕捉到节点活跃性的动态变化和这些变化对网络结构的影响。下面我们来详细介绍活动驱动模型的构建过程、理论分析及其扩展。1. 模型概述在传统的静态网络模型中网络拓扑结构是静态的节点之间的连接关系没有时间变化。而在活动驱动模型中节点的交互是基于节点的活跃潜力来决定的。活跃潜力反映了节点与其他节点发生交互的可能性。活跃潜力定义为节点在给定时间窗口内与其他节点发生交互的次数与该时间窗口内所有节点交互次数的比值。节点的活跃潜力高意味着该节点有更高的概率与其他节点建立连接。活动驱动模型的关键特点是节点的激活状态是随机的且基于其活跃潜力分布。节点以一定的概率活跃并在该状态下与其他节点建立连接。非活跃节点也可以与活跃节点建立连接。活跃节点连接到其他节点时若没有直接连接连接会通过重新连接的方式随机生成。2. 活动驱动模型构建流程活动驱动模型的构建流程如下初始化静态网络在模型的初始阶段我们生成一个包含孤立节点的静态网络。此时节点之间没有任何连接。节点激活在每个离散时间步骤t tt每个节点以一定概率处于活跃状态并随机与m mm个其他节点生成无向连边。生成快照网络对于每个时刻节点与其他节点的连接形成一个快照网络。接着删除所有连边生成下一个时刻的网络快照。重复生成快照这个过程会重复多次通过多次快照的生成最终得到时序网络。通过不断的时间步长迭代我们可以生成一个动态演化的时序网络节点的活跃状态和连接行为随时间不断变化。接。活跃节点连接到其他节点时若没有直接连接连接会通过重新连接的方式随机生成。2. 活动驱动模型构建流程活动驱动模型的构建流程如下初始化静态网络在模型的初始阶段我们生成一个包含孤立节点的静态网络。此时节点之间没有任何连接。节点激活在每个离散时间步骤t tt每个节点以一定概率处于活跃状态并随机与m mm个其他节点生成无向连边。生成快照网络对于每个时刻节点与其他节点的连接形成一个快照网络。接着删除所有连边生成下一个时刻的网络快照。重复生成快照这个过程会重复多次通过多次快照的生成最终得到时序网络。通过不断的时间步长迭代我们可以生成一个动态演化的时序网络节点的活跃状态和连接行为随时间不断变化。
