网络的时间属性会对扩散过程产生怎样的影响，解决这一问题的第一种方法是在真实或人工合成的带时间戳的事件序列数据上模拟随机游走过程，并与所定义的空模型比较相应的动态属性^[7-9]。第二种方法，研究分析在特定时序网络模型上的随机游走属性^[10-11]。

文献^{[10, 12-13]}提出将时序网络建模成事件随机序列，其中每个链接上的事件服从规定的间隔时间分布。考虑N个节点的一个无向网络，由节点集V ={1,2,L,N}和边集E组成，这种网络往往被称为聚合网络，它被认为是时序网络的聚合。用更新方式给每个边e分配一个随机事件间隔时间τ_e，通过在聚合网络上添加时间维度生成随机时序网络^{[10, 12]}。用${\psi _e}(t)$表示${\tau _e}$的概率密度函数(probability density function,PDF)，并假设${\tau _e}$的均值有限。随机游走者可以立刻从当前节点跳到一个邻近节点，只要这两个节点之间的链接出现。

在时序网络中，根据随机游走者沿着一个链接到达一个节点时，该节点的其他链接的事件间隔时间^[14]是否重新初始化，随机游走过程可以分为主动随机游走和被动随机游走两种模式。1) 主动随机游走过程被定义为一个更新过程，一个随机游走者到达一个节点后，这个节点的所有链接的事件间隔时间重新初始化^{[10, 12]}。它的非马尔科夫性是由于这样一个事实：一个事件发生的概率取决于前面的事件。这种随机过程可以用广义主方程表示，并且可以获得一些属性的解析解，比如稳态密度^[12]和弛豫时间。2) 被动随机游走模式，当一个游走者到达一个节点时，只初始化刚使用的链接的事件间隔时间。与主动随机游走相比，被动随机游走被认为是一种更自然的网络扩散模式。因为在现实中，扩散的实体，如病毒，通常不会重新启动一个活跃边两端的节点。被动随机游走比主动随机游走表现出更强的非马尔科夫性，因为被动随机游走者在某种程度上记住了过去的游走轨迹。

本文提出的随机游走模型包含多个随机游走者，每一个随机游走者都是一个免疫粒子，它作为一种特殊的蠕虫程序，可以转移但不能增生，即它可以从一个节点转移到另一节点，但不能增加免疫体数量。获得免疫粒子的节点获得免疫力，失去免疫粒子的节点转换成非免疫的易感态。在多随机游走者的模型中，无论是主动随机游走模式还是被动随机游走模式都存在一个同样的问题，即随机游走者之间在转移时是否相互影响。任意一个免疫粒子在随机游走中不受其他免疫粒子影响的模型被称为独立随机游走免疫模型。免疫粒子在随机游走中相互影响的模型被称为非独立随机游走免疫模型。

如图 1所示，当一个边被激活后，这条边的两个端节点中的免疫粒子便可以从一个端节点沿着这条活跃边转移到另一个端节点。图 1中的直线表示连接两个节点的边，直线上方的实心圆数目表示将要转移的粒子数，直线上方的箭头表示免疫粒子的转移方向，以上解释同样适用于图 2和图 3。当端节点中含有的免疫粒子数不超过1个时，独立与非独立的随机游走方式是相同的。图 1b中的双方互换免疫粒子，看似是一个浪费网络资源的无意义的数据传输，但它避免了通信双方在传输数据前互换彼此状态信息(含有的免疫粒子数)所带来的网络开销，同时也简化了免疫粒子转移时的传输协议。

图  1  节点含有单个免疫粒子的随机游走

图  2  节点含有多个免疫粒子的随机游走

当出现节点含有多个免疫粒子的情形时，这两种随机游走方式存在区别。由于独立随机游走的免疫粒子互不影响，当其所在节点有边出现(激活)时，免疫粒子就会沿着边转移到另一节点，而无论其所在节点中是否有其他免疫粒子存在或转移。因此，如图 2a所示，对于独立随机游走方式，当图中的边被激活后，该边左侧端节点中的所有免疫粒子都会向右侧端节点转移。而对于非独立的随机游走方式，如图 2b所示，当图中的边被激活时，该边左侧端节点中的多个免疫粒子只有一个会向右侧端节点转移，而其他免疫粒子或者选择该节点同时激活的其他边，或者等待该节点下一个活跃边的到来。如图 3所示，$t$时刻，节点有两个活跃边，每个活跃边都有一个免疫粒子经此转移。${t}'$时刻$({t}'>t)$，节点有一个活跃边，剩下的一个免疫粒子经此活跃边转移至另一端的邻节点。

图  3  非独立随机游走示例图

将节点上的免疫粒子看作是一种有限资源，用$({{A}_{i}},{{B}_{i}})$表示节点$i$上的资源信息，其中${{A}_{i}}\ge 0{{B}_{i}}\ge 0$。${{A}_{i}}$表示节点$i$上现有的免疫粒子数，即该节点在本时间步内还可以转移的免疫粒子数；而B_i 表示本时间步内已从邻居节点转移来的免疫粒子数，这些免疫粒子在本时间步内不允许再转移出去，以防止一个免疫粒子在一个时间步内出现多跳，即防止一个免疫粒子在一个时间步内依次完成经历多 个节点的转移。比如免疫粒子从一个节点转移到另一节点后，再转移到第3个节点上。

设$({{A}_{i}},{{B}_{i}})$、$({{A}_{j}},{{B}_{j}})$分别是边${{e}_{ij}}$被激活时节点$i$、$j$的资源信息，如果 A_i> 0 且 A_j> 0 ，则本次数 据传输结束时，独立随机游走方式下的节点 i 、 j 的 资源分别为 (0, B_i+ A_j ) 和 (0, B_j+ A_i ) ；而非独立随机 游走方式下的节点 i 、 j 的资源分别为 ( A_i −1, B_i +1) 和 ( A_j−1, B_j + 1) 。如果 A_i> 0 而 A_j= 0 ，则本次数据 传输结束，独立随机游走方式下的节点 i 、 j 的资源 分别为 (0, B_i ) 和 (0, B_j+ A_i ) ；而非独立随机游走方式 下的节点 i 、j 的资源分别为 ( A_i−1, B_i ) 和 (0, B_j+ 1) 。 其他情况可以参照图 1、图 2类推。

在每个时间步 t ，为避免由于激活边的处理顺序 使得随机游走实验结果偏好节点序号小或大的节 点，每次从第 t 个时间步激活的边集$E_{t}^{a}$中随机取出一条边，直至集合$E_{t}^{a}$为空。在每个时间步，所有活跃边都处理完毕后，统一更新所有节点的资源状态，节点 i 的资源状态由 ( A_i , B_i ) 更新为 ( A_i+ B_i ,0) ，i = 1, 2,L, N 。非独立随机游走免疫模型的具体算法如下。

算法1：非独立随机游走免疫模型算法

输入：网络中的免疫粒子总数m，免疫开始时间${{t}_{0}}$，时序网络活跃边集序列${{E}^{a}}=\{E_{0}^{a},E_{1}^{a},\cdots ,E_{T-1}^{a}\}$，其中$E_{t}^{a}$表示t时刻所有活跃边所构成的集合。

输出：网络所有节点的免疫粒子分布M=${{({{A}_{0}},{{A}_{1}},\cdots ,{{A}_{N-1}})}^{\text{T}}}$。

从网络的所有节点中随机选出m个节点；

将每个选出的节点的资源置成(1,0) ，其他节点的资源置成(0,0) ；

for$\leftarrow $t to T-1

while $E_{t}^{a}\ne \phi $ do

从活跃边集合$E_{t}^{a}$中随机选出一条边${{e}_{ij}}$；

$E_{t}^{a}\leftarrow E_{t}^{a}-\{{{e}_{ij}}\}$；

if ${{A}_{i}}$>0 then

${{A}_{i}}\leftarrow {{A}_{i}}-1$；

${{B}_{j}}\leftarrow {{B}_{j}}+1$；

end if

if ${{A}_{j}}$>0 then

${{A}_{j}}\leftarrow {{A}_{j}}-1$；

${{B}_{i}}\leftarrow {{B}_{i}}+1$；

end if

end while

for i$\leftarrow $0 to N-1

${{A}_{i}}\leftarrow {{A}_{i}}+{{B}_{i}}$；

${{B}_{i}}\leftarrow 0$；

end for

end for

独立随机游走模型有一个很明显的问题，如图 2a所示，一旦有多个游走者到达同一节点，则它们将永远结伴而行，因为只要有边激活，它们便一同沿边转移，这对免疫一定数量的节点非常不利。一个好的解决办法是：当一个节点有边激活时，该节点上的每个免疫粒子便以概率P转移，以概率1-P不转移。每个免疫粒子是否转移与节点上是否有其他免疫粒子存在或转移无关，称这种独立随机游走免疫模型为P_独立随机游走免疫模型。具体算法如下：

算法2：P_独立随机游走免疫模型算法

输入：免疫粒子转移概率$P$，免疫粒子总数$m$，免疫开始时间${{t}_{0}}$，时序网络活跃边集序列${{E}^{a}}=\{E_{0}^{a},$ $E_{1}^{a},\cdots ,E_{T-1}^{a}\}$，其中$E_{t}^{a}$表示$t$时刻所有活跃边所构成的集合。

输出：网络所有节点的免疫粒子分布M= ${{({{A}_{0}},{{A}_{1}},\cdots ,{{A}_{N-1}})}^{\text{T}}}$。

从网络的所有节点中随机选出$m$个节点；

将每个选出的节点的资源置成(1,0) ，其他节点的资源置成(0,0) ；

for t$\leftarrow $${{t}_{0}}$to T-1

while $E_{t}^{a}\ne \phi $ do

从活跃边集合$E_{t}^{a}$中随机选出一条边${{e}_{ij}}$；

$E_{t}^{a}\leftarrow E_{t}^{a}-\{{{e}_{ij}}\}$；

Particle_num←A_i；

for k←1 to Particle_num

产生[0,1) 之间的随机数RandomNum；

if RandomNum<P then

${{A}_{i}}\leftarrow {{A}_{i}}-1$；

${{B}_{j}}\leftarrow {{B}_{j}}+1$；

end if

end for

Particle_num←${{A}_{j}}$；

for k←1 to Particle_num

产生[0,1) 之间的随机数RandomNum；

if RandomNum<P then

${{A}_{j}}\leftarrow {{A}_{j}}-1$；

${{B}_{i}}\leftarrow {{B}_{i}}+1$；

end if

end for

end while

for i←0 to N-1

${{A}_{i}}\leftarrow {{A}_{i}}+{{B}_{i}}$；

${{B}_{i}}\leftarrow 0$；

end for

end for

如图 4所示，实验所使用的时序网络底图(聚合网络)为BA网络，其节点总数$N=1\text{ }000$，每个新加入节点连接5个已有节点，边的激活间隔时间服从指

图  4  BA网络为底图的免疫效果对比

数为2.1的幂律分布。对于随机游走免疫模型而言，免疫粒子密度是指要设定的免疫粒子数与网络节点总数的比值。对于目标免疫模型与熟人免疫模型而言，免疫粒子密度是指要选择的免疫节点数与网络节点总数的比值。实验结果中的感染密度是指实验结束时，网络中处于感染态的节点数与网络节点总数的比值。每次实验的总时间步为5 000，对于每一个给定的免疫粒子密度值，图中对应的各模型的感染密度值均为100次重复实验的均值。实验结果的图例中及分析论述中出现的URW、PRW分别表示非独立随机游走免疫模型和P_独立随机游走免疫模型，其中$P=0.5$。

实验以随机游走免疫模型的开始实施时间为0时刻，目标免疫和熟人免疫开始实施时间为${{t}_{0}}$时刻，将$[0,{{t}_{0}}]$时间内收集到的所有节点间的交互聚合成一个无重边的无向网络，就获得了时序网络在这个时间段内的拓扑结构信息。这个结构信息是熟人免疫和目标免疫为选择免疫节点而需要收集的网络信息，可以用一个称之为网络拓扑信息量的定义来量化，它可以由下式定义：

$网络拓扑信息量\equiv \frac{给定时间内所收集的边数量}{网络底图的总边数}$

随机游走免疫模型与熟人免疫模型、目标免疫模型的免疫效果对比如图 4所示。图例前缀AI表示熟人免疫，TI表示目标免疫，图例中的数字表示熟人免疫模型和目标免疫模型实施免疫的开始时刻${{t}_{0}}$。由于熟人免疫(AI)结果的3条曲线基本重合，目标免疫(TI)结果的3条曲线非常接近，需要在图中的曲线旁注明其对应的免疫策略。在本实验中，在${{t}_{0}}=1$时，网络拓扑信息量为43.8%，在${{t}_{0}}=$1000时，网络拓扑信息量增加至98.1%，熟人免疫模型和目标免疫模型分别以这两个不同时刻作为免疫开始时间，所获得的免疫效果并没有明显的区别，这个信息表明网络拓扑信息量的持续增加并不能明显地持续改善这两种免疫策略的免疫效果。

如图 4所示，各免疫模型的免疫效果由好至差依次为URW免疫模型、PRW免疫模型、目标免疫模型、熟人免疫模型。与PRW免疫模型和目标免疫相比，URW免疫模型的免疫效果有明显的优势，而前两者又明显优于熟人免疫模型。PRW免疫模型与目标免疫模型相比较，随着免疫粒子密度的增大，PRW免疫模型的优势逐渐显现。

本实验所使用的真实网络数据是来自俄勒冈州立大学的路由器视角项目的在线数据。这个数据集包含了从1997年11月8日～2000年1月2日共785天中的733天的英特网自治域间的数据交换，所有数据交换关系聚合成一个AS网络。以这个AS网络作为时序网络的底图，只有底图上存在的边才有可能在某个时刻被激活，并发送数据。本次实验仍设网络边激活间隔时间服从指数为2.1的幂律分布。测试前对网络做预处理，剔除网络中不连通的部分，只保留最大连通子图，处理后的聚合网络节点数$N$=6474，边的总数为26467，在这里简记为AS20网络。

如图 5所示，以AS20网络为底图的时序网络上，各免疫模型的免疫效果由好至差依次为目标免疫模型(TI)、URW免疫模型、PRW免疫模型、熟人免疫模型(AI)。AS20网络与前面所用的BA网络相比较有一个显著区别：网络度分布的异质性程度。BA网络度分布是服从幂指数为3的幂律分布，而AS20网络度分布的幂指数是小于1.5，即AS20网络的拓扑结构远比BA网络拓扑结构的异质性要强。意味着，与BA网络相比，AS20网络中的节点度集中在更少的节点上。因此，与以BA网络为底图的时序网络上的相应免疫模型的免疫效果(见图 4) 相比较，目标免疫模型和熟人免疫模型都有显著提高，尤其是目标免疫的免疫效果有了很大的飞跃，其免疫粒子密度临界值${{f}_{C}}$<0.01，成为免疫效果最好的模型。但目标免疫必须要能够搜集到足够的信息，并汇总分析以产生全局信息，只有这样才能对节点排序、免疫。因此，在大的时序网络上比较免疫效果，目标免疫只是作为一个标杆，其难以实施。另一方面，即便在拓扑结构的异质性很强的AS20网络上，URW免疫模型和PRW免疫模型的免疫效果也是优于熟人免疫模型的免疫效果，它们的免疫粒子密度临界值${{f}_{C}}$分别小于或等于0.03和0.05，而熟人免疫模型的免疫粒子密度临界值${{f}_{C}}$是大于这两个值的(超出了图 5的横坐标范围)。

图  5  AS20网络为底图的免疫效果对比

与以BA网络为底图的时序网络上的各模型免疫效果比较，不仅是目标免疫模型和熟人免疫模型的免疫效果有显著提高，URW免疫模型和PRW免疫模型的免疫效果也有较大的提高。在以AS20网络为底图的时序网络上，URW免疫模型和PRW免疫模型在免疫更少比例的节点基础上，获得了更好的免疫效果。其原因仍然是与BA网络相比，AS20网络的拓扑结构异质性更强。对于拓扑结构异质性越强的网络，就会有越少的重要性更强的节点。基于随机游走扩散机制的免疫粒子更倾向于游走到这些更重要的节点上，所以在以AS20网络为底图的时序网络上，通过免疫这些少量的重要节点，就可以获得好的免疫效果。

本文提出了基于随机游走机制的免疫模型，包括非独立随机游走免疫模型和P_独立随机游走免疫模型，这两种免疫模型的免疫节点密度都不超过给定的免疫粒子密度。通过实验，发现随机游走免疫模型的免疫效果优于熟人免疫模型，与目标免疫模型的比较结果取决于网络拓扑结构的异质性程度。随机游走免疫模型具有无需搜集、分析网络拓扑信息，以及可以随时部署实施的优势。随机游走免疫模型需要考量免疫粒子传播所需要的网络开销，而这一网络开销可以直接通过事先设定的免疫粒子密度等模型参数得以控制。

本文研究工作还得到了网络与数据安全四川省重点实验室开放课题(NDSMS201603) 、新疆维吾尔自治区高校科研计划科学研究重点项目(XJEDU2016I036) 以及新疆财经大学博士启动基金(2016BS008) 的资助，在此表示感谢。