浅谈时序网络演化速度对传播影响

论文导读：
摘要：为分析时序网络演化速度对传播过程的影响，通过改善已有的时序相关系数定义，给出了一个网络演化速度指标；同时，提出了一个具有非马尔可夫性质的时序网络演化模型。在每个时间步，每一个给定的激活节点都以概率r在网络中随机选择一个节点，以概率1-r在该激活节点的原邻居中随机选择一个节点，并在该激活节点与所选节点间建立连边。模拟结果表明：网络模型参数r与网络演化速度指标之间有单调增的关系；同时，激活节点随机连边的概率r越大，网络传播范围就越广。由此可知：演化速度快的时序网络有利于网络传播；进一步地，网络拓扑结构的快速变化有利于信息的快速传播，但不利于抑制病毒传播。
关键词：复杂网络；时序网络；非马尔可夫过程；传播动力学；幂律分布
：A英文标题
0引言
传统上对网络的研究是基于静态网络结构[1-2]，它假设网络节点间的连接是持续不断、始终存在的，而这种假设往往与现实不符，是对现实系统基本元素之间相互作用关系的简化。智能手机、无线传感器、可穿戴设备等各种无线终端的广泛使用，使得人们可以获得各种系统的大量实时交互数据，这些数据包括个体间交互的时间、时长以及其他一些信息。对大量数据的分析表明，个体之间的交互往往是间歇性和复发性的，并且只能持续一个有限时间[3-7]，表现出典型的阵发性[4， 6， 8]。时间维度的加入使得网络模型变得比以往更加复杂，网络中原有的许多概念和指标都需要重新定义或修改[9-10]。网络中的个体交互活动是有记忆的，即网络节点的连边是一个非马尔可夫过程[4-7， 11-13]。包含时间信息的网络模型对于人们进一步认识系统的结构、特征，发现网络上的各种规律是极其重要的。静态网络的拓扑结构对网络上的传播过程有着至关重要的影响。然而，人们对时序网络的演化规律，尤其是网络演化快慢对传播动力学过程的影响[14]仍然知之甚少。如何描述、定义网络演化速度，网络演化快慢对传播过程（如病毒传播、信息传播）是否会产生影响，以及产生怎样的影响，这些理由的解决对了解、认识甚至是制约（抑制或推动）网络上的传播现象将产生积极的作用。
1时序相关系数

1.1时序网络的表示

网络是一个包含了大量个体以及个体间相互作用的系统。把个体视为节点，个体间的相互作用视作节点间的连边，任意复杂系统都可以用图来表示。图是对系统中基本单元（或称个体、节点）集合，以及基本单元间的关系（或称交互、边）集合的描述，即图可以定义为一个二元组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等同于策略1。事实上，在网络的整个演变过程中无法保证网络的连通性，在此情形下，按策略1计算的时序相关系数不能正确反映时序网络的变化情况。图1给出了一个具有7个节点的连续快照的简单示例。
由式（4），可以计算出各节点的邻居拓扑重叠系数，如表1所示。
如图1所示，时序网络在tm时刻和tm+1时刻的快照是完全相同的，这两个快照的邻居拓扑重叠系数Cm应该为1，策略1明显低估了这两个图的相关性，而策略2准确地表达了这两个快照是相同的。图1在tm+1时刻和tm+2时刻的快照之间只有一条边的区别，这两个快照的邻居拓扑重叠系数Cm+1应该接近1，策略1再次低估了这两个图的相关性，策略 2则合理地表达了这两个快照的相似关系。 全文地址：www.7ctime.com/xwxzlw/lw46383.html上一论文：试谈用镜头传播感动