时序网络演化速度对传播的影响分析

时序网络演化速度对传播的影响分析

作者：朱义鑫 张凤荔 秦志光 来源：《计算机应用》2014年第11期

摘要：为分析时序网络演化速度对传播过程的影响，通过改进已有的时序相关系数定义，给出了一个网络演化速度指标；同时，提出了一个具有非马尔可夫性质的时序网络演化模型。在每个时间步，每一个给定的激活节点都以概率r在网络中随机选择一个节点，以概率1-r在该激活节点的原邻居中随机选择一个节点，并在该激活节点与所选节点间建立连边。模拟结果表明：网络模型参数r与网络演化速度指标之间有单调增的关系；同时，激活节点随机连边的概率r越大，网络传播范围就越广。由此可知：演化速度快的时序网络有利于网络传播；进一步地，网络拓扑结构的快速变化有利于信息的快速传播，但不利于抑制病毒传播。 关键词：复杂网络；时序网络；非马尔可夫过程；传播动力学；幂律分布 中图分类号： TP393.08文献标志码：A英文标题 0引言

传统上对网络的研究是基于静态网络结构[1-2]，它假设网络节点间的连接是持续不断、始终存在的，而这种假设往往与现实不符，是对现实系统基本元素之间相互作用关系的简化。智能手机、无线传感器、可穿戴设备等各种无线终端的广泛使用，使得人们可以获得各种系统的大量实时交互数据，这些数据包括个体间交互的时间、时长以及其他一些信息。对大量数据的分析表明，个体之间的交互往往是间歇性和复发性的，并且只能持续一个有限时间[3-7]，表现出典型的阵发性[4， 6， 8]。时间维度的加入使得网络模型变得比以往更加复杂，网络中原有的许多概念和指标都需要重新定义或修改[9-10]。网络中的个体交互活动是有记忆的，即网络节点的连边是一个非马尔可夫过程[4-7， 11-13]。包含时间信息的网络模型对于人们进一步认识系统的结构、特征，发现网络上的各种规律是极其重要的。静态网络的拓扑结构对网络上的传播过程有着至关重要的影响。然而，人们对时序网络的演化规律，尤其是网络演化快慢对传播动力学过程的影响[14]仍然知之甚少。如何描述、定义网络演化速度，网络演化快慢对传播过程（如病毒传播、信息传播）是否会产生影响，以及产生怎样的影响，这些问题的解决对了解、认识甚至是控制（抑制或促进）网络上的传播现象将产生积极的作用。 1时序相关系数 1.1时序网络的表示

网络是一个包含了大量个体以及个体间相互作用的系统。把个体视为节点，个体间的相互作用视作节点间的连边，任意复杂系统都可以用图来表示。图是对系统中基本单元（或称个体、节点）集合，以及基本单元间的关系（或称交互、边）集合的描述，即图可以定义为一个

龙源期刊网 http://www.qikan.com.cn

二元组G=（V，E），其中集合V={v1，v2，…，vN}称为节点集，集合E={e1，e2，…，eH}称为边集。

在时序网络中，边集E中的元素可以用形如（i， j，t，δt）的四元组来表示[9]，它表示个体i与个体j在时刻t开始并持续时长为δt的交互。如手机通话数据网络中，用户A在t1时刻给用户B打电话，在t2时刻结束通话，则这个事件可以用（A，B，t1，t2-t1）表示。网络中的所有通话记录都可以表示成这样的四元组，所有这些四元组的序列就构成了手机通话数据的时序网络。如果所研究的系统中个体间发生事件的时长信息对网络的建模、分析影响不大，则可以省略节点间的交互时长，而只考虑交互发生的起始时刻，即可以用三元组（i， j，t）来表示，它表示个体i与个体j在时刻t发生交互。 1.2时序相关系数的改进

文献[16]给出了一个时序网络相关系数的概念。网络节点i在相邻两个快照Gm、Gm+1上的共同邻居数量的占比称为节点i在快照Gm、Gm+1上的邻居拓扑重叠系数，具体形式如下 它可以用来衡量网络中的任意一条边持续出现在相继两个快照中的概率。如果所有快照都完全相同，即网络是静止不变的，那么时序相关系数C为1；若所有相继的两个快照间都没有重叠边，则时序相关系数C为0；除了这两个极端情况，时序相关系数C的取值是介于0和1之间的。

然而，网络在其演化过程中并不能保证其一定不出现孤立节点（度为零的节点）。对式（1）所定义的节点邻居拓扑重叠系数进行补充定义：

对式（2）、式（3）调换求和顺序得到式（5）和式（6）。所有节点在相邻快照Gm、Gm+1上的邻居拓扑重叠系数的均值被称为相邻快照Gm、Gm+1的邻居拓扑重叠系数，用Cm表示。

Cm表示网络在tm、tm+1两个时刻的快照的相似度。Cm越接近1，表示两个快照越相似；Cm等于1，表示两个快照完全相同。在整个观察期[t1，t1+T）内，所有相邻快照的邻居拓扑重叠系数均值，就是时序网络的时序相关系数C：

按照式（4）的定义，若节点i在Gm或Gm+1中是孤立节点，则其邻居拓扑重叠系数Ci（tm，tm+1）=0，这样的节点在计算相邻快照的邻居拓扑重叠系数时应予以排除。对式（5）的修改如下：

其中：Um、Um+1 分别为Gm、Gm+1上的孤立节点集，|Um∪Um+1|表示这两个孤立节点集的并集的势。

在此，称由式（4）～（6）定义时序相关系数的方法为方法1，而由式（4）、（7）、（6）定义时序相关系数的方法为方法2。若图在演变过程中始终为连通图，则方法2等同于

龙源期刊网 http://www.qikan.com.cn

方法1。事实上，在网络的整个演变过程中无法保证网络的连通性，在此情形下，按方法1计算的时序相关系数不能正确反映时序网络的变化情况。图1给出了一个具有7个节点的连续快照的简单示例。

由式（4），可以计算出各节点的邻居拓扑重叠系数，如表1所示。

如图1所示，时序网络在tm时刻和tm+1时刻的快照是完全相同的，这两个快照的邻居拓扑重叠系数Cm应该为1，方法1明显低估了这两个图的相关性，而方法2准确地表达了这两个快照是相同的。图1在tm+1时刻和tm+2时刻的快照之间只有一条边的区别，这两个快照的邻居拓扑重叠系数Cm+1应该接近1，方法1再次低估了这两个图的相关性，方法 2则合理地表达了这两个快照的相似关系。 图片图1一组连续快照的简单示例

在计算时序网络的时序相关系数时，方法1只适用于整个网络始终保持连通的时序网络，而这往往是不现实的，方法2则把它拓展到可以含有任意多个连通子图的一般情形。 2有记忆的网络演化模型 2.1网络演化速度

在时序网络中，时序相关系数C是所有相邻快照的邻居拓扑重叠系数均值，表示相邻快照间的平均相似度。那么，1-C是所有相邻快照的非重叠边的比例均值，可以表示相邻快照间的平均变化率。当1-C=1时，所有相邻快照之间都没有重叠边；当1-C=0时，所有相邻快照完全相同，即网络拓扑结构是完全静止不变的。对于一个时序网络，在其时间分辨率确定的前提下，1-C的大小可以作为衡量网络演化速度的指标。

显然，这里所谓的速度并不是物理学上的单位时间内位移变化量的速度概念。不同系统的规模（节点总数）是有很大差异的，这里网络连边的变化量是个比值，即它是一个网络连边的变化比率而不是绝对变化量。此外，对于研究不同现实系统、不同应用需求的时序网络模型，往往会有不同的时间尺度或时间分辨率，即快照的时间跨度是不同的。即使在采集数据时采用相同的采样频率，例如每秒一次，在分析、建模时，也会根据系统特征、研究目标而合并成不同时间尺度的快照序列。因此，这里所谓的时序网络演化速度是用于比较同一时序网络在不同时期的演化快慢，也可以比较时间尺度相同的两个时序网络的演化快慢，而不表示单位时间内的变化率。

2.2网络演化模型

为研究网络演化快慢对传播的影响，即研究传播阈值或传播范围与网络演化速度指标1-C之间是否存在同向或反向变化，需要建立一个可以控制网络演化速度的模型。许多的实证研究[11]表明，网络中节点的激活时间是异质分布的，具有典型的阵发性。

龙源期刊网 http://www.qikan.com.cn

本模型是基于时变网络的活动驱动模型[17]。设任意节点i的激活概率ai服从幂律分布F（a）。

其中：amin是节点激活的最小概率，γ是幂律分布的指数。那么在时间窗口Δt内，节点i的激活概率为aiΔt。

在每一个时间步，当一个节点i激活，它以概率r从网络节点中随机选择一个节点，以概率1-r从节点i在上一快照的邻居中随机选择一个节点，并在节点i和所选节点之间建立连边。具体的算法如下：程序前

输入网络节点总数N，总的时间步T，节点激活的概率分布F（a），激活节点随机连边概率r。

输出时序网络快照序列{G0，G1，…，GT-1}。 1）时间变量t赋初值为0。

2）将网络置成由N个孤立节点构成的没有连边的图，节点编号变量i赋初值为0。 3）取区间[0，1）内的一个随机数RndNum1。

4）如果RndNum1大于或等于节点i的激活概率aiΔt（不妨设Δt=1），转到步骤8）。 5）取区间[0，1）内的一个随机数RndNum2。

6）如果RndNum2小于r或节点i在上一快照中的度k为零，则执行步骤①；否则执行步骤②：

①在网络中随机选择一个节点j，若j等于i或边eij已存在，则重新执行步骤①。 ②在节点i的上一快照的邻居节点中随机选择一个节点j，若边eij已存在并且步骤②重复执行的次数小于k，则重新执行步骤②。

7）若边eij不存在，则在节点i和节点j之间建立连边。 8） i ← i+1，若i 9）保存快照Gt。 10）t ← t+1，若t

龙源期刊网 http://www.qikan.com.cn

由于快照图是稀疏图，许多节点的度很小，甚至是0 或1。在执行步骤②时，若节点i和它在上一快照中的所有邻居均已存在连边时，那么只判断边eij是否已存在，会陷入死循环。因此，需要加上一个条件，以限制其循环的次数。例如限制循环次数的上限是该节点在上一快照中的度，即在步骤②重复执行k次后，放弃重新选择要连边的节点，结束步骤②。也意味着在步骤②执行结束时，将要建立的边eij仍然有可能是已存在的边，所以在步骤7）中仍需再次判断，以避免产生重边。

给定不同的网络模型参数r的值，可以生成不同的时序网络，并按照方法2计算每个生成的时序网络的时序相关系数C的值。其中网络的规模（节点总数）N=1×105，最小激活概率amin=10-2，幂律分布指数γ=1.5，时间分辨率Δt=1，时间T=103，模拟结果取重复执行100次的均值。如图2所示，网络模型参数r与网络演化速度指标1-C之间有单调增的关系，可以通过设置r的值来控制所生成的时序网络的演化快慢。 3实验与分析

经典的传播模型是易感感染恢复（SusceptibleInfectedRecovered，SIR）模型和易感感染易感（SusceptibleInfectedSusceptible，SIS）模型。在SIR传播模型中，网络中的每个个体在任意一个时刻必然处于易感（S）、感染（I）或恢复（R）三种状态之一。易感者是健康但易于被感染的个体；感染者已经被感染并且具有传染性；免疫者曾经被感染，现在已经被治愈，并且获得了免疫能力，不会再被感染。在SIS传播模型中，网络中的个体可以在易感态（S）和感染态（I）之间转换。

在SIR传播模型中，在每一个时间步，当一个感染节点接触一个易感节点时，以概率θ感染这个易感节点；在每一个时间步，每一个感染节点以概率β转化成恢复态。在SIS传播模型中，在每一个时间步，当一个感染节点接触一个易感节点时，以概率θ感染这个易感节点；在每一个时间步，每一个感染节点以概率β恢复成易感态。θ与β的比值，被称为模型的有效传播率，用λ表示。

在所执行的模拟中，网络模型的各参数值，包括网络的规模（节点总数）、最小激活概率、幂律分布指数以及时间分辨率的值与上节所述相同。传播模型的恢复概率β=0.1，传播率θ={0.1，0.2，…，1.0}，对应的有效传播率λ={1，2，…，10}（见图3的横坐标）。模拟的初始时刻，随机选取1%的节点作为初始感染节点。在SIR传播中，当网络不再有I态节点时，本次模拟结束，传播最终结果为R态节点数量占节点总数的比值，即曾经被感染过的节点的比例，用R∞来表示。在SIS传播中，总的时间步T设为1000，传播最终结果为最后时刻I态节点数量占节点总数的比值，用I∞来表示。以上模拟均重复执行100次，所采用的R∞和I∞的值为重复执行所得到的R∞和I∞的平均值。 图片图3时序网络参数r取不同值时的传播结果 与有记忆（r

龙源期刊网 http://www.qikan.com.cn

图片图4网络演化速度与网络传播结果 4结语

本文利用时序相关系数的定义，避开不同时序网络时间分辨率的差异性问题，提出了一个描述时序网络演化速度的指标。基于时序网络的阵发性以及节点连边的非马尔可夫性，建立了一个可以调节网络演化速度的时序网络演化模型。模拟表明，网络演化速度与传播过程的传播范围大小是同向变化的。一个现实的例子是，通过WiFi传播的手机病毒，在人员流动特别频繁且提供免费WiFi服务的地铁、公交车及其车站等公共场所，其传播速度会比其他环境下的传播速度更快。一个重要因素是每个用户的WiFi邻居（连接到同一WiFi路由器的用户）在快速地改变，这增加了感染者接触更多易感者的机会，也增加了病毒传播的机会。因此，网络拓扑结构的快速变化有利于信息的快速传播，但不利于抑制病毒传播。探索时序网络的动力学特性及规律，已成为重要的研究方向。对时序网络的研究仅仅处于开始阶段，许多的概念、理论、建模方法以及如何应用到各种真实网络上都需要大量而细致的研究 参考文献：

[1]BOCCALETTI S， LATORA V， MORENO Y， et al. Complex networks： structure and dynamics[J]. Physics Reports， 2006， 424（4）： 175-308.

[2]NEWMAN M. Networks： an introduction[M]. London： Oxford University Press， 2009. [3]HOLME P. Network reachability of realworld contact sequences[J]. Physical Review E， 2005， 71（4）： 046119.1-046119.8.

[4]BARABASI AL. The origin of bursts and heavy tails in human dynamics[J]. Nature， 2005， 435（7039）： 207-211.

[5]VZQUEZ A， OLIVEIRA J G， DEZS Z， et al. Modeling bursts and heavy tails in human dynamics[J]. Physical Review E， 2006， 73（3）： 036127.1-036127.19.

[6]STEHL J， BARRAT A， BIANCONI G. Dynamical and bursty interactions in social networks[J]. Physical Review E， 2010， 81（3）： 035101.1-035101.4.

[7]KARSAI M， KASKI K， BARABASI AL， et al. Universal features of correlated bursty behaviour[J]. Scientific Reports，2012（2）：397.1-397.7.

[8]MIRITELLO G， MORO E， LARA R. Dynamical strength of social ties in information spreading[J]. Physical Review E， 2011， 83（4）： 045102.1-045102.4.

[9]HOLME P， SARAMKI J. Temporal networks[M]. Berlin： SpringerVerlag， 2013.

龙源期刊网 http://www.qikan.com.cn

[10]GAUTREAU A， BARRAT A， BARTHLEMY M. Microdynamics in stationary complex networks[J]. Proceedings of the National Academy of Sciences， 2009， 106（22）： 8847-8852. [11]ZHOU T， HAN X， YAN X， et al. Statistical mechanics on temporal and spatial activities of human[J]. Journal of University of Electronic Science and Technology of China， 2013， 42（4）： 481-540.（周涛， 韩筱璞， 闫小勇， 等. 人类行为时空特性的统计力学[J]. 电子科技大学学报， 2013， 42（4）： 481-540.）

[12]ROCHA L E， BLONDEL V D. Bursts of vertex activation and epidemics in evolving networks[J]. PLoS Computational Biology， 2013， 9（3）： e1002974.1-e1002974.9. [13]VAJNA S， T TH B， KERT SZ J. Modelling bursty time series[J]. New Journal of Physics， 2013， 15（10）： 103023.1-103023.16.

[14]MASUDA N， KLEMM K， EGUILUZ V M. Temporal networks： slowing down diffusion by long lasting interactions[J]. Physical Review Letters， 2013， 111（18）： 188701.1-188701.5.

[15]RIBEIRO B， PERRA N， BARONCHELLI A. Quantifying the effect of temporal resolution on timevarying networks[J]. Scientific Reports， 2013（3）：3006.1-3006.5. [16]TANG J， SCELLATO S， MUSOLESI M， et al. Smallworld behavior in timevarying graphs[J]. Physical Review E， 2010， 81（5）： 055101.1-055101.4.

[17]PERRA N， GONCALVES B， PASTORSATORRAS R， et al. Activity driven modeling of time varying networks[J]. Scientific Reports， 2012（2）：469.1-469.7.