时变网络上零模型的构造算法及应用

于咏平

摘 要：时变网络体现了拓扑结构与动力学相结合的网络特性，准确测量时变网络的性能在预测、控制信息传播等方面有重要的研究价值。零模型的引入使得对于时变网络具有的阵发性、周期性以及因果特性等研究更加全面。文章首先介绍了零模型在生物学等领域的研究背景，接着利用各类网络所适用的置乱算法，构造不同参数要求的零模型。针对不同情况对于构造要求的不同，提出并分析了时变网络零模型在构造过程中计算量的概念，并利用计算模型和理论解析验证对比了所提出算法与随机变动方法在变动过程中的计算量优势，最后讨论了在双层耦合网络中零模型的应用。

关键词：时变网络；零模型；社交网络；置乱算法

伴随着互联网飞速发展，如今人们更倾向于通过在线社交网络获取传播信息。而现有网络特性的统计量如度分布、平均路径长度、聚类系数等往往不能准确刻画原网络的非平凡特性。零模型是一个与实际网络具有某些相同性质的随机网络，也称该实际网络的随机化副本。

1981年，Strong等[1]提出零模型一词。Maslov和Sneppen[2]将零模型利用到生物学，得出蛋白倾向于异配连接。Barrat等[3]介绍了ER随机图模型等作为网络参照模型的方法。Newman等[4]提出任意度分布的随机图理论。Mahadevan等[5]提出了分析网络拓扑关系的方法，对比网络拓扑结构对于网络重要特性的影响。Milo等[6]提出了基于复杂网络中较小子图的显著性剖面（Significant Profile，SP）与随机网络比较的方法，发现了超级家族。由于许多配置模型仅在构造一阶零模型的层面，Newman创建了一个可解析的网络模型，展示了将标准的随机图形模型一般化，保持了聚类系数不变，完善了配置模型的应用[7]。

胡华全等[8]按照保持意象图的手段进行技术分类， 总结时变网络可视化研究的思想方法。不同阶次零模型成功置乱概率存在差异，难以准确判断零模型何时能够趋于稳定，李欢等[9]定义了“成功置乱次数”的概念，李欢等[10]针对生成大尺度网络的零模型时间效率较低的问题，利用数据分组思想，提供了一种高效的解决方案。2017年吴睿等[11]提出了dK-目标保持重连算法，降低了计算复杂度。从零模型的提出到如今各种理论与算法的逐步完善，使零模型在研究各种网络特别是社交网络中起到越来越重的作用，包括多层耦合网络上的应用也日臻灵活。

1 社交网络上的置乱算法

社交网络也是一种时变网络，在社交网络上加上时间戳能更具体地描述社交行为，对社交网络的分析也可以说是对时变网络的分析。

在保持原始网络连接的条件下，置乱算法可以随机化某些因素，将原始网络参数与新得到的网络参数进行对比，进而得知网络的非平凡特性。这种方法的应用更加普遍，在对比的过程中也更加灵活。尚可可等[12]整理了各种网络中基于置乱算法的零模型构造过程和它们的实际应用。

1.1 断边重连

断边重连算法表示了原始网络度分布，不会产生自环或重边现象，操作简便，计算量小。Maslov等[2]利用随机断边重连方法，判断生物蛋白质大分子更倾向于异配连接。在双层网络中也可以利用到随机断边重连算法，崔丽艳和许小可[13]提出了以多种双层网络零模型作参照物，通过假设检验方法来量化双层网络间结构相关性，分析了这种结构相关性存在的内在机理。Newman等[14]利用随机断边重连方式测量网络的混合模式，分析数据发现在分类混合网络模型中网络鲁棒性更好。局部断边重连算法是断边重连的一种，Zhou和Mondrag[15]提出富人俱乐部系数的概念并利用局部断边重连算法证明Internet网络也具有富人俱乐部属性。

1.2 权重置乱

节点间连边强度的异质性也是网络具有不同属性的重要因素。在加权网络中，主要表现的是连边上的权重因素。Opsahl等[16]利用权重置乱等方法对社交网络提出了一种通用框架来研究网络中资源流向性的趋势，發现大部分资源可以共享，形成了控制系统资源的俱乐部。Barrat等[17]采用权重置乱算法研究了航空运输等网络的连接权重与拓扑相关性。其中等权置乱算法改变了网络的拓扑结构，且不破坏连边权重分布。

1.3 时间置乱

在社交网络中，测量节点的动态变化是十分必要的，相比于传统的网络，时变网络增添了时间维度，刻画出网络事件发生顺序及事件相关性等动力学特性。在社交网络中，传染病的扩散、信息的传播等问题是此领域很热点的研究问题，Barabási[18]研究了在实际生活中，人类的动态行为在时变网络中的统计特性。

1.3.1 时间置乱算法

通过置乱网络中各连边事件发生的时间，时间置乱算法达到了随机化相关时间参数的目的，不会改变网络的拓扑结构与每条连边上事件发生的次数。随机选取一个事件发生的时间戳，与另一时间戳置换，并重复操作，直到满足要求。或将所有时间戳打乱，随机分布在各连边上，并保持每条连边的权重不变。Holme[19]根据实际接触网络事件发生的时间序列，对比由时间置乱算法构造的零模型，发现所测得信息可达性时间取决于路径长度与交流频率。

1.3.2 时权置乱算法

时权置乱算法破坏了网络的权重特性，保留了连边上事件发生的时间顺序，没有破坏时间阵发性，可以研究时变网络权重的影响。为了研究导致小世界网络中信息传播速度缓慢的因素，Karsai等[20]置乱了事件发生的序列以跟踪信息传播，发现主要是由于繁复的拓扑关系以及个体的活动模式引起的。

接触置乱是在时权置乱算法基础上，随机化破坏网络连边上事件的阵发性。置乱过程中，保证拓扑结构不变，将所有事件随机重新分布在每条连边上。

1.3.3 时间倒转算法

在有向时变网络中，事件的发生顺序可以反映事件的因果特性，时间倒转算法，打乱了事件发生的先后次序，可以研究事件的相关性与因果性。

1.3.4 区间图上的置乱算法

在实际的社交网络中，许多事件是在一个时间段内发生的，其发生时间长短对于结果有明显影响。例如一个传染病患者在接触其他人群时，接触时间长短会影响其他人是否被感染病毒的概率结果。由此可见，一些情况下要关注事件所持续的时间段长度，区间图就可以很好地体现事件发生的持续特性。Candia等[21]利用移动电话数据，借助区间图表示，描述了个体的某些平均行为导致重尾现象发生，时空异常。

2 时变网络零模型的计算量优化

在时变网络中，前面几种算法约束条件浅显，试错较少或不需试错，而根据时间倒转算法要求，要破坏原网络事件发生的相关性与因果性。如图1所示，在原网络中信息可以从A经由B传至C。为了破坏传播的因果性，就要改变原来的传播路径。需破坏两条路径，即改变时间戳来影响事件传播，使后一步传播的时间戳排在前一步信息传播之前。要破坏ABC这条路径，将后一步最后出现的时间戳与前一步第一次出现的时间戳互换，则AB边上的时间戳为7、11，BC边上的时间戳为2、3，这样就保证了信息不能再从A通过B传至C，再变化过程中有可能致使其他路径构成因果关系，用上述方法调整时间戳，直至图1中不存在事件间的因果性，构造结束。

3 双层网络上的节点置乱算法及应用

在不同的时间段用户与其他用户建立或解除友好关系的情况构成了网络的拓扑结构。在社交网络中，不同的时间段内用户的各种社交行为，是用户社交功能在网络上的体现，形成了社交功能网络，两层数据的网络之间存在明显的耦合关系。比较有代表性的是有倾向性节点置乱算法，倾向性指的是有一定目的的对一层节点重排。如果要得到同配网络，置换节点使得一层度值大的节点连接另一层度值大的节点即可，称为有倾向性的构造正匹配效应的零模型网络，负匹配效应相反。

4 结语

时变网络是社交网络的一部分，保持着社交网络在各方面的特点，时变网络与多层网络应用更加普遍，要更深层次地挖掘网络属性或微观结构，需要借助类似零模型这类推断工具来对比网络中影响传播的对象。在构造零模型的过程中，对于不同的阶数与算法要求，计算量较大，本文从计算模型和理论解析验证了提出算法的优化特性，并在计算相关系数方面有待进一步优化。

[参考文献]

[1]STRONG D R，SIMBERLOFF D，ABELE L G，et al.Ecological communities： conceptual issues and the evidence[M].New Jersey：Princeton University Press，2014.

[2]MASLOV S，SNEPPEN K.Specificity and stability in topology of protein networks[J].Science，2002（5569）：910-913.

[3]BARRAT A，BARTH?LEMY M，VESPIGNANI A.Dynamical processes on complex networks[M].England：Cambridge University Press，2008.

[4]NEWMAN M E J，STROGATZ S H H，WATTS D J J.Random graphs with arbitrary degree distributions and their applications[J]. Physical Review E，2001（2）：26118.

[5]MAHADEVAN P，KRIOUKOV D，FALL K，et al.Systematic topology analysis and generation using degree correlations[J].ACM SIGCOMM Computer Communication Review，2006（4）：135-146.

[6]MILO R，ITZKOVITZ S，KASHTAN N，et al.Super families of evolved and designed networks[J].Science，2004（5663）：1538-1542.

[7]NEWMAN M E J.Random graphs with clustering[J].Physical Review Letters，2009（5）：58701.

[8]胡華全，吴玲达，杨超，等.时变网络可视化研究综述[J].系统仿真学报，2013（9）：1975-1980，1989.

[9]李欢，卢罡，郭俊霞，等.复杂网络零模型的量化评估[J].计算机应用，2015（6）：1560-1563.

[10]李欢，卢罡，郭俊霞.基于GPU的大尺度网络零模型分组生成并行算法[J].计算机工程与设计，2016（1）：93-99.

[11]吴睿，宋玉蓉.2.25阶/2.5阶网络零模型模拟退火优化算法[J/OL].计算机技术与发展，2017（12）：1-5[2018-01-12].http：//kns.cnki.net/kcms/detail/61.1450.TP.20170927.0957.006.html.

[12]尚可可，许小可.基于置乱算法的复杂网络零模型构造及其应用[J].电子科技大学学报，2014（1）：7-20.

[13]崔丽艳，许小可.参照零模型的双层网络结构相关性检测[J].科技导报，2017（14）：63-74.

[14]NEWMAN M E J.Assortative mixing in networks[J].Physical Review Letters，2002（20）：208701.

[15]ZHOU S，MONDRAGON R J.The rich-club phenomenon in the Internet topology[J].IEEE Communications Letters，2004（3）：180-182.

[16]OPSAHL T，COLIZZA V，PANZARASA P，et al.Prominence and control： The weighted rich-club effect[J].Physical Review Letters，2008（16）：168702.

[17]BARRAT A，BARTHELEMY M，PASTOR-SATORRAS R，et al.The architecture of complex weighted networks[J].Proceedings of the National Academy of Sciences of the United States of America，2004（11）：3747-3752.

[18]BARAB?SI A L.The origin of bursts and heavy tails in human dynamics[J].Nature，2005（7039）：207-211.

[19]HOLME P.Network reachability of real-world contact sequences[J].Physical Review E，2005（4）：046119.

[20]KARSAI M，KIVEL? M，PAN R K，et al.Small but slow world： how network topology and burstiness slow down spreading[J].Physical Review E，2011（2）：25102.

[21]CANDIA J，GONZ?LEZ M C，WANG P.Uncovering individual and collective human dynamics from mobile phone records[J].Journal of Physics A： Mathematical and Theoretical，2008（22）：224015.