复杂网络谱粗粒化方法的改进算法∗

周建 贾贞†李科赞

1)(桂林理工大学理学院,桂林 541004)

2)(桂林电子科技大学数学与计算科学学院,桂林 541004)

(2016年10月2日收到;2016年11月21日收到修改稿)

复杂网络谱粗粒化方法的改进算法∗

周建1)贾贞1)†李科赞2)

1)(桂林理工大学理学院,桂林 541004)

2)(桂林电子科技大学数学与计算科学学院,桂林 541004)

(2016年10月2日收到;2016年11月21日收到修改稿)

大规模网络的同步问题是网络科学的重要研究课题之一.粗粒化方法提供了一种将大规模网络转化为小规模网络,同时又能较好地保持原始网络的拓扑性质或动态特性的研究途径,其中比较有代表性的谱粗粒化方法能较好地保持初始网络的同步能力.然而,谱粗粒化方法在实际计算中计算量大、对实际大规模网络可执行性差.本文提出一种改进的谱粗粒化算法,能大幅减少计算量,同时获得更好的谱粗粒化效果.通过理论分析和大量的数值仿真实验验证了所提改进算法的粗粒化效果和计算量都明显优于原谱粗粒化方法.

复杂网络,同步,谱粗粒化,改进算法

1 引 言

同步是自然界、人类社会和工程技术领域中一种常见的集合运动现象,如蛙声齐鸣、有节律的鼓掌等.近二十多年来,研究人员对复杂动态网络的同步进行了大量研究,特别是对于中尺度网络的同步研究取得了丰富的研究成果[1−11].然而,许多实际网络是拥有成千上万甚至上亿节点的大规模网络,研究大规模耦合复杂动态网络同步常常会产生大量的耦合微分方程,给计算和仿真实验都带来巨大困难,许多中尺度网络同步算法在大规模网络研究中难以实现,因此人们提出了一些粗粒化方法试图将大规模网络转化为中尺度网络来研究[12−17].粗粒化方法通过合并相似节点将大规模网络缩减为中尺度网络,同时尽量保持原始网络的某些重要性质,如拓扑特性或动力学性质等.近年来,在粗粒化的研究方面也取得了一些重要进展.例如, K im[18]提出了一种粗粒化方法能保持原始网络的度分布、聚类系数、同配系数等性质;Chen等[19]提出了一种基于网络度的粗粒化方法,能保持原始网络平衡态统计分布的一致性.在这些粗粒化方法中,比较典型的是由G feller和Rios[20,21]在2008年提出的谱粗粒化(spectral coarse graining,SCG)方法,通过分析网络结构矩阵的特征值谱,合并网络中结构相同和相似的节点,从而有效地将大规模网络缩减为小规模网络同时又能较好地保持初始网络的同步能力.Chen等[15]进一步研究了SCG方法在聚类网络中的应用效果,Zeng和Lü[16]进一步提出了基于有向网络的SCG方法,能很好地保持粗粒化网络的同步能力.

SCG方法在保持网络同步能力方面独占优势,然而在确定网络中的哪些节点被合并时需要反复判断,这样会产生非常巨大的计算量,其计算复杂度为O(N3)[16].对于现实中少则成千上万节点的网络,多则上百万甚至上亿节点的大规模网络,其巨大的计算量致使SCG方法在实际中难以执行.为了克服SCG方法计算量大的缺陷,本文提出了一种改进的SCG方法,记为ISCG(improved spectral coarse graining)算法,将计算复杂度从O(N3)降到O(N2),同时还改善了粗粒化效果,所得粗粒化网络能够更好地保持初始网络的同步能力.

2 网络同步能力的刻画

考虑N个节点的复杂网络,其动力学方程为

其中xi∈Rm表示第i个节点的m维状态变量;是第i个节点的动态方程;δ＞0为耦合强度;H(·):Rm→Rm是节点内部耦合函数; Laplacian矩阵L=(Lij)N×N∈RN×N为外部耦合矩阵,刻画了网络的耦合拓扑结构.若网络节点j和i(i=j)相连,则Lij=1,否则Lij=0;Laplacian矩阵L的对角线元素满足,即矩阵L满足耗散耦合条件:.当网络是无向无权的连通网络时,对应的矩阵L是对称不可约的正半定矩阵,具有非负特征值且满足0=λ1＜ λ2≤ ···≤ λN.网络(1)同步状态x1(t)=x2(t)=···=xN(t)=s(t)的同步流形s(t)满足=F(s(t)),它可以是孤立节点的平衡点、周期轨道或混沌轨道.将方程(1)线性化,令ξi为第i个节点状态的变分,得到变分方程

其中D F(s)和D H(s)分别是F(s)和H(s)关于s(t)的Jacobi矩阵.将方程(2)对角化可得到

ηk是矩阵L关于特征值λk的特征模式.将方程(3)一般化,得到主稳定方程:

该方程的最大Lyapunov指数Lmax是实变量α的函数,称之为网络(1)的主稳定函数,记为Lmax(α).网络(1)的同步化区域是指使Lmax(α)＜ 0的实数α的取值范围,记为SR,它是由孤立节点动力学函数F(xi(t))和内连函数确定的,只要网络的耦合强度δ与耦合矩阵L的特征值之积全部落入同步区域即δλk∈SR(k=2,3,···,N),网络(1)就能达到完全同步[22].网络的同步区域主要分为以下4种类型:1)有界区域(α1,α2); 2)无界区域(α1,+∞);3)若干个有界区域的并集∪(α1i,α2i);4)空集.一般地,3)和4)的情形下网络很难或完全无法达到同步,幸运的是大多数网络都是1)和2)两种情形,此时只有当L的特征值满足λN/λ2＜ α2/α1或者λ2＞ α1/δ时网络才能达到同步稳定状态(其中λ2和λN分别为Lap lacian矩阵的最小非零特征值和最大特征值).这意味着当λN/λ2越小或者λ2越大时网络更容易达到同步,因此在同步研究中,常常用特征值比λN/λ2和最小非零特征值λ2两个指标来刻画网络的同步能力[23].

3 基于网络同步的SCG方法

3.1 SCG方法

由于网络的同步能力可用λ2或λN/λ2来刻画,因此要使粗粒化后的网络仍保持原始网络的同步能力,就应使粗粒化前后网络的λ2或λN/λ2尽可能接近或不变.2008年,Gfeller和Rios[20,21]提出的SCG方法就是依此设计的,在缩减网络规模的同时,尽可能地保持网络的同步能力.该方法主要解决了两个关键问题:一是如何合并节点和更新边;二是确定哪些节点可以被合并.

首先,对于如何合并节点和更新边,SCG方法将初始网络的N个节点标记为i=1,2,···,N,粗粒化后网络节点标记为C=1,2,···,˜N,˜N为粗粒化后的网络规模,C也表示初始网络中的 ˜N个团,每个团的节点将被合并为粗粒化网络中的一个节点.粗粒化后网络的边(对应新的Lap lacian矩阵可通过下面的矩阵乘积进行更新:

这里,|C|是团C中包含节点的个数;Ci是节点i所在团C的标号,ψ是常用的K ronecker函数.

其次,对于哪些节点被合并,分别考虑λ2和λN/λ2两个指标.若考虑指标λ2(网络(1)的Lap lacian矩阵L的最小非零特征值),记λ2对应的特征向量为p2,将p2中相同或相近的分量对应的节点进行合并,此时˜L的最小非零特征值与λ2相同或相近. 理论上,特征向量p2的两个分量和相同或相近,可表示为,其中和分别为p2的N个分量中的最大值和最小值.实际计算时,把区间划分为I个等分区间,对落入同一等分区间的p2分量对应的节点进行合并.一般地,I越小对应的 ˜N越小,因此可通过控制I值的大小来大致控制粗粒化网络的规模.相同或相似节点的合并过程及λ2的保持情况如图1所示.

同理,当考虑指标λN/λ2(网络(1)的Laplacian矩阵L中最大与最小非零特征值之比)时,合并节点需同时满足条件和.实际计算时分别把区间,划分为I个等分区间(其中pN为最大特征值λN对应的特征向量),找出p2和pN中同时落入等分区间内的分量,将其对应的节点进行合并.此时˜L的特征值比与λN/λ2相同或相近,即能保持粗粒化网络的同步能力.

图1显示,把结构相同或相似的节点进行合并,网络的最小非零特征值λ2变化不大,即网络的同步能力能够很好地被保持.

图1 (网刊彩色)合并节点过程[21]Fig.1.(color on line)Processing ofm erging nodes[21].

3.2 SCG方法的局限

我们通过大量仿真实验发现,很多网络的特征向量分量分布极不均匀,大多数分量分布相对集中、间距较小,极少数分量分布特别分散且间距很大.以节点N=100的NW小世界网络为例,根据特征值λ2对应的特征向量p2,将区间划分为I=15的等分区间,p2的分量落入等分区间内的分布情况如图2所示,图2中菱形对应p2的所有分量,16条竖线将区间划分为15个等分区间.从图2可看出,p2的分量分布极不均匀.因此等区间划分节点时可能造成有些距离特别近的两个分量(对应极相似的节点,如图2中蓝色菱形对应分量和锰紫色菱形对应分量)被分割到两个相邻区间中,而与间距更大的分量(对应不太相似的节点)划分到同一区间而合并相应节点,这会影响粗粒化效果.另一方面,计算中需要将每一个p2分量与等分区间所有的端点值进行比较,依此判断落在哪个等分区间内,这会造成较大的计算量,特别是对规模巨大的网络更为明显,其计算复杂度为O(N3)[16].例如,当网络节点N=1000时,SCG方法的计算量达到10亿次.此外,由于p2的分量分布极不均匀,一些等分区间内没有分量落入,导致合并后的网络规模随I变化不大.例如,节点N=1000的NW小世界网络,当划分等区间数I为102,103,104,105,106时,分别为14,69, 381,871,991,因此I值对网络规模的控制效果并不理想,也在一定程度上会影响粗粒化效果.综上所述,SCG化方法存在两方面的缺陷.一是计算量过大,对于大规模网络实际计算难以实现;二是对某些网络粗粒化效果并不十分理想.

图2 (网刊彩色)特征向量p2的分量分布情况Fig.2.(color on line)Distribution of com ponentsof eigenvector p2.

4 改进的SCG算法

本节我们在原方法的基础上提出一种改进的SCG算法,不仅降低了计算复杂度,还改善了粗粒化效果,使粗粒化后的网络更好地保持初始网络的同步能力.

与SCG方法采取等分区间确定合并节点的做法不同,ISCG算法依特征向量分量的分布情况采取分裂聚类方法来确定合并节点.具体做法是:先将特征向量分量由小到大排序,计算两两相邻分量间的距离,根据相邻分量之间的间距大小将分量分裂成若干个聚类,然后将每个聚类中对应的节点合并为一个节点.选择间距的大小将决定同一聚类中节点的相似程度和粗粒化网络的规模.例如,选择较大的前−1个间距将所有分量分裂成个聚类,这个聚类对应节点合并为个节点,从而可以精确控制网络的规模,越大,相邻分量的间距越小,合并节点的相似度越高,粗粒化效果越好.

下面我们以保持λ2为例进一步说明ISCG算法的步骤. 首先假设λ2的特征向量p2的分量由小到大排序为相邻分量之间的间距为i=1,···,N−1),假设选择最大的前3个间距,分别记为这3个间距将分裂成4个聚类,分别为,其中间距分裂区间时对应的左右端点分别为和和和,再将这4个聚类中对应的节点进行合并,即得到 ˜N=4的粗粒化网络.由此可见,ISCG算法可以根据需要,选择一定的间距将原始网络N个节点合并到任何指定规模 ˜N的粗粒化网络,并且合理区分不同节点间的相似程度,从而能确保被合并节点之间的相似程度高于不同聚类之间节点的相似程度,因此粗粒化效果较SCG方法更好.在计算量方面,由于ISCG算法只需计算分量之间的间距,而不需判断比较每一个特征向量分量落入等区间的情况,只要确定了粗粒化网络模型,便可一次完成所有节点的合并,因此大幅减少了计算量,其计算复杂度为O(N2).此外,ISCG算法能精确控制粗粒化网络规模,这点优于SCG算法对粗粒化网络规模的控制.

类似地,对于保持特征值比λN/λ2的情况,可根据λ2和λN的特征向量p2和pN的分量之间的间距将各分量分裂成不同的聚类,将同时分裂在同一聚类中对应节点合并为一个节点,计算过程与上述保持λ2的情形类似,这里不再赘述.

5 数值仿真

本节将分别对连续时间动态网络和耦合相振子网络模型进行数值仿真,分别应用ISCG算法和SCG方法对网络进行粗粒化,比较两种不同粗粒化算法对几种典型网络同步能力的保持效果.

5.1 连续时间动态网络的同步效果

下面对连续时间动态网络模型(1)进行数值仿真.分别选取四种典型的复杂网络,即NW小世界网络、ER随机网络、BA无标度网络和一类复杂聚类网络[15],分别应用ISCG和SCG算法粗粒化网络,观察并比较粗粒化效果.原始网络规模均为N=1000.

图3和图4展示了分别采用ISCG和SCG两种算法对四种典型网络进行粗粒化的结果和网络同步能力的保持情况.无论对哪种网络,采取ISCG算法获得的粗粒化网络与原始网络的λ2和λN/λ2的近似程度都明显优于SCG方法获得的粗粒化网络,说明ISCG算法的粗粒化效果和同步能力保持情况优于SCG方法.从运算时间上看,在实验中获得相同规模的粗粒化网络,ISCG算法比SCG方法所用的时间大大减少.以上述N=1000的NW小世界网络为例,在保持λ2的情形,获得 ˜N=600的粗粒化网络,采用ISCG算法和SCG方法在MATLAB软件试验中的运行时间分别是2.94 s和18.4 s.实际上,由于后者需要经过多次反复实验才能获得规模 ˜N=600的粗粒化网络,故实际获得结果时间远不止18.4 s,而ISCG算法可以精确控制粗粒化网络规模,一次完成实验,故运行时间只需要2.94 s,可见ISCG算法的运算速度大幅提高.此外, ISCG算法可以精确获得任意规模的粗粒化网络,从而能够更精细地展示网络的粗粒化演变过程,而SCG方法却做不到这点.当然,粗粒化网络规模越小,合并的节点就越多,对原始网络同步能力的保持效果越差,但对于同等规模的粗粒化网络,显然ISCG算法的同步能力的保持效果更好.

图3 (网刊彩色)分别采用ISCG和SCG算法获得粗粒化网络对λ2的保持情况 (a)NW小世界网络;(b)ER随机网络;(c)BA无标度网络;(d)聚类网络Fig.3.(color on line)Them aintaining ofλ2obtained by using ISCG and SCG algorithm s in coarse graining network:(a)NW network;(b)ER network;(c)BA network;(d)clustered network.

图4 (网刊彩色)分别采用ISCG和SCG算法获得粗粒化网络对λN/λ2的保持情况 (a)NW 小世界网络; (b)ER随机网络;(c)BA无标度网络;(d)聚类网络Fig.4.(color on line)The m aintaining ofλN/λ2obtained by using ISCG and SCG algorithm s in coarse graining network:(a)NW network;(b)ER network;(c)BA network;(d)clustered network.

5.2 耦合K u ram oto相振子网络的同步效果

下面对耦合Kuramoto网络[24,25]模型进行数值仿真,进一步比较ISCG和SCG算法对保持相振子同步的效果.耦合Kuramoto网络模型方程为

其中,ωi表示第i个振子的固有频率,σ表示全局振子耦合强度,Aij为邻接矩阵,θi表示第i个振子的相位,N表示振子的个数.全局振子的相同步程度可用序参量r(t)刻画:

其中序参量r(t)(∈[0,1])为0时表示全局振子以各自的固有频率运动,即完全不同步状态,为1时表示全局振子以相同频率运动,即达到完全同步状态;ϕ(t)表示全局振子的平均相位.因此可通过序参量r(t)来研究粗粒化网络的同步保持情况.

以上文N=1000的NW小世界网络、ER随机网络、BA无标度网络、聚类网络为例,采用ISCG和SCG算法粗粒化网络,得到网络规模 ˜N均为200的ISCG网络和SCG网络,ωi在(−0.5,0.5)中随机选择,初始相位θi在(−π,π)中随机选择,σ分别为0.2,0.2,1.5,0.5.其序参量r(t)保持情况如图5所示.

图5展示了分别采用ISCG和SCG两种算法对振子相同步的保持情况,可见ISCG获得网络的序参量r(t)收敛性与原始网络基本一致,且ISCG算法获得的粗粒化网络同步能力保持情况优于SCG方法.

图5 (网刊彩色)分别采用ISCG和SCG算法保持序参量r(t)的情况 (a)NW小世界网络;(b)ER随机网络; (c)BA无标度网络;(d)聚类网络Fig.5.(color on line)The m aintaining of the order param eter r(t)obtained by using ISCG and SCG algorithm s in coarse graining network:(a)NW network;(b)ER network;(c)BA network;(d)clustered network.

6 结 论

复杂动态网络的耦合拓扑结构直接影响网络的动力学性质.一般来说,两个节点的外部连接相同或相近,意味着它们接收外部的信息和作用也相同或相近,因而具有相近的动力学性质,SCG方法的基本思想正是基于这一点,把网络中外部链接相同或相近似的节点进行合并,从而把大规模网络缩减为中尺度网络,这是研究大规模网络的重要途径之一.本文提出的ISCG算法,以特征向量分量之间的间距大小来划分相似节点,从而自适应地对聚类节点进行分组,能够确保网络中越相近的节点越被优先合并,避免了SCG方法对节点进行硬性分组而导致某些情况下相似节点被拆分而与不相近节点合并的缺陷.仿真实验也验证了ISCG算法既能很好地改善粗粒化效果,又大幅降低了运算的时间复杂度.

从算法分析和仿真结果看,在粗粒化过程中应该存在一个最优的聚类个数,即存在一个既能很好地保持原始网络同步能力又能最大程度地缩减原始网络规模的聚类个数,例如,用λ2来刻画网络的同步能力,可以满足(ε比较小,可设定)的对应的最小 ˜N即为最优聚类个数.以上文中所列举的四种典型即NW小世界网络、ER随机网络、BA无标度网络和聚类网络为例,可求得最优聚类个数 ˜N分别为915,805,795,768.然而,对于最优的聚类个数问题,还有更多的未知需要我们去探索,例如衡量最优粗粒化聚类个数的指标函数如何确定?各种不同结构的网络的最优指标有何差异?且有待我们进行更深入的探索研究,也是我们今后的努力方向.

本文提出的ISCG算法具有误差更小、效果更优、运算量大幅降低等诸多优点,能极大地改善原粗粒化效果,提高了网络同步能力的保持状况,同时为实现大规模网络的同步研究提供了一种更简单、高效和可操作的有效方法.

[1]Pecora L M,Carroll T L 1998 Phys.Rev.Lett.80 2109

[2]Jost J,Joy M P 2001 Phys.Rev.E 65 016201

[3]W ang X F,Chen G R 2002 IEEE Trans.Circuits-I 49 54

[4]Barahona M,Pecora L M 2002 Phys.Rev.Lett.89 054101

[5]W ang X F,Chen G R 2002 In t.J.Bifurcat.Chaos 12 187

[6]M otter A E,Zhou C S,Kurths J 2005 Phys.Rev.E 71 016116

[7]N ishikawa T,M otter A E 2006 Physica D 224 77

[8]Zhou J,Lu JA,Lu JH 2006 IEEE Trans.Au to.Con trol 51 652

[9]A renas A,Díaz-Guilera A,Kurths J,M oreno Y,Zhou C S 2008 Phys.Rep.469 93

[10]Zhu T X,W u Y,X iao J H 2012 Acta Phys.Sin.61 040502(in Chinese)[朱廷祥,吴晔,肖井华2012物理学报61 040502]

[11]Xu M M,Lu JA,Zhou J 2016 Acta Phys.Sin.65 028902 (in Chinese)[徐明明,陆君安,周进 2016物理学报 65 028902]

[12]K urkcuoglu O,Jernigan R L,Doruker P 2004 Polym er 45 649

[13]M arrink S J,Vries A H D,M ark A E 2004 J.Phys. Chem.B 108 750

[14]Bornhold t S 2005 Science 310 449

[15]Chen J,Lu J A,Lu X F,W u X Q,Chen G R 2013 Comm un.Non linear Sci.18 3036

[16]Zeng A,LüL Y 2011 Phys.Rev.E 83 056123

[17]Saunders M G,Voth G A 2013 Annu.Rev.Biophys.42 73

[18]K im B J 2004 Phys.Rev.Lett.93 168701

[19]Chen H S,Hou Z H,Xin HW,Yan Y J 2010 Phys.Rev. E 82 011107

[20]G feller D,Rios P D L 2007 Phys.Rev.Lett.99 038701

[21]G feller D,Rios P D L 2008 Phys.Rev.Lett.100 174104

[22]Chen G R,W ang X F,Li X,LüJ H 2009 Som e Recen t Advances in Com plex Networks Synchronization(Heidelberg:Sp ringer)pp3–16

[23]Lu JA,Liu H,Chen J 2016 Synchronization in Com plex Dynam ical Networks(Beijing:Higher Education Press) pp120–125(in Chinese)[陆君安,刘慧,陈娟2016复杂动态网络的同步(北京:高等教育出版社)第120—125页]

[24]Kuram oto Y 1975 Lect.Notes Phys.39 420

[25]Aceb rón J A,Bonilla L L,Pérez V icente C J,Ritort F, Sp igler R 2005 Rev.M od.Phys.77 137

PACS:05.45.–a,05.45.X tDOI:10.7498/aps.66.060502

Im p roved algorithm of spectral coarse grain ing m ethod of com p lex netw ork∗

Zhou Jian1)Jia Zhen1)†Li Ke-Zan2)

1)(College of Science,Guilin University of Technology,Guilin 541004,China)
2)(School ofM athem atics and Com puting Science,Guilin University of E lectronic Technology,Guilin 541004,China)
(Received 2 O ctober 2016;revised m anuscrip t received 21 Novem ber 2016)

Com p lex network as a key app roach to understandingmany com p lex system s,such as biological,chem ical,physical, technological and social system s,is ubiquitous in nature and society.Synchronization of large-scale com p lex networks is one of the m ost im portant issues in network science.In the last two decades,much attention has been paid to the synchronization of com p lex dynam ic networks,especially themeso-scale networks.However,many real networks consist of even hundreds ofm illions of nodes.Analyzing the synchronization of such large-scale coup led com p lex dynam ic networks often generate a large number of coup led diff erentialequations,which m ay m akem any synchronization algorithm s inapp licable formeso-scale networks due to the com p lexities of simu lation experiments.Coarse grainingmethod canmap the large-scale networks into m eso-scale networks while preserving som e of topological p roperties or dynam ic characteristics of the original network.Especially,the spectral coarse-graining scheme,as a typical coarse grainingmethod,is proposed to reduce the network size while preserving the synchronization capacity of the initial network.Nevertheless, p lenty of studies dem onstrate that the com ponents of eigenvectors for the eigenvalue of the coup ling m atrix,which can depict the ability to synchronizing networks,distribute uneven ly.Most of the com ponents distribute concentrically and the intervals are sm all,while som e other com ponents distribute dispersed ly and the intervals are large,which renders the app lications of original spectral coarse graining m ethod unsatisfactory.Inspired by the adap tive clustering,we p ropose an im proved spectral coarse graining algorithm,which clusters the same or the sim ilar nodes in the network according to the distance between the com ponents of eigenvectors for the eigenvalue of network coup ling m atrices,so that the nodesw ith the sam e or the sim ilar dynam ic properties can be eff ectively clustered together.Com pared w ith the original spectral coarse graining algorithm,thismethod can im p rove the accuracy of the result of clustering.M eanwhile,our m ethod can greatly reduce algorithm com p lexity,and obtain better spectral coarse graining resu lt.Finally,num erical simulation experim ents are im p lem ented in four typical com p lex networks:NW network,ER network,BA scale-free network and clustering network.The com parison of results demonstrate that ourmethod outperform s the original spectral coarse graining approach under various criteria,and im proves the eff ect of coarse graining and the ability to synchronize networks.

comp lex network,synchronization,spectral coarse graining,im proved algorithm

10.7498/aps.66.060502

∗国家自然科学基金(批准号:61563013,61663006)资助的课题.

†通信作者.E-m ail:jjjzzz0@163.com

*Pro ject supported by the National Natural Science Foundation of China(G rant Nos.61563013,61663006).

†Corresponding author.E-m ail:jjjzzz0@163.com