相振子网络中集聚系数和度分布对复杂度的影响

李珏璇，赵 明(.广西师范大学物理科学与技术学院,广西 桂林 54004； 2.广西科技师范学院机械与电气工程学院，广西 柳州 545004)

相振子网络中集聚系数和度分布对复杂度的影响

李珏璇1,2，赵 明1
(1.广西师范大学物理科学与技术学院,广西 桂林 541004； 2.广西科技师范学院机械与电气工程学院，广西 柳州 545004)

分析了复杂网络的集聚系数和度分布的异质性这两个重要的描述复杂网络结构特点的特征量对复杂度的影响。研究发现，增大集聚系数能增大复杂度的最大值以及增大复杂度钟形曲线的宽度，而增大度分布的异质性不能增大复杂度的最大值却可以明显增大复杂度在上升段和下降段的取值。对于小世界网络集聚系数对复杂度的影响更明显，而对于无标度网络，度分布的异质性更能显著的改变复杂度的取值。进一步加深了人们对描述网络部分同步状态的复杂度的认识，为设计合理的网络结构提供了理论基础。

复杂度；集聚系数；度分布

0 引言

经过十余年的发展，人们对复杂网络[1-2]的结构、动力学等性质已经有了比较深刻的了解，目前人们的研究目标已经转移到更符合实际背景的动力学行为[3-4]上，探讨其具体过程及内在结构对动力学行为的影响。就复杂网络上动力系统的同步现象来说，最初的研究主要考察了复杂网络的整体同步性质、分析了网络的各种结构特征量对网络整体同步能力或稳定性的影响[5-7]，而目前的研究更多集中在网络的中尺度结构对复杂网络同步状态的影响[8-13]上。中尺度结构包括网络的群落结构、层次结构等，而此时的同步状态更多的是部分同步而非之前研究的完全同步。以中尺度结构和部分同步状态为研究目标是因为中尺度结构是一种广泛存在的复杂网络结构，并且部分同步而不是完全同步才是更常见的同步现象[14]。

很长时间以来，物理领域对部分同步的研究几乎是空白的，为了解决这样的问题，在之前的工作中，我们定义了复杂度的概念[13]：当网络处于完全的不同步或者接近完全同步状态时，网络的同步状态很简单，复杂度的值很小；当网络介于两者之间处于部分同步状态时，网络的同步状态很复杂，复杂度的值很大。具体说来，随着耦合强度从0开始增加，网络中的节点慢慢开始同步到部分同步状态、再到完全同步状态的过程中，复杂度的取值从0开始增加到一个小于1的最大值之后再降低到0。这样，网络的部分同步状态就被定量刻画出来。复杂度的取值与网络结构和节点间的耦合强度都有关系，我们以猫的脑神经网络[15]和线虫的神经网络[16]为例证明真实的神经网络处于复杂度最大的结构状态。在上述工作中，我们只研究了群落结构对复杂度的影响，实际上影响复杂度的网络结构因素还有很多，本文就探讨网络的团簇结构和度分布对部分同步状态的影响。本文以小世界网络[1]和具有初始吸引度的无标度网络[17-18]为模型，通过能够保持节点度不变的随机交叉换边方法[19-20]讨论网络的聚类系数和度分布的异质性对网络复杂度[13]的影响。

1 复杂度、随机交叉换边方法

1.1 复杂度

本文采用相振子作为节点上的动力系统：

(1)

其中，φi、ωi分别为第i个节点的位相和固有频率，σ为节点间的耦合强度，N为网络规模，〈k〉为网络中节点的平均度，aij为邻接矩阵的矩阵元，也就是说当节点i和节点j之间有边相连时aij取值为1，当两节点间没有边相连时aij取值为0。网络的部分同步状态用复杂度[13]来描述，为了获得复杂度，首先就要计算所有节点对之间的平均位相差，注意这个位相差是要经过不同的固有频率分布、初始位相分布和长时间演化的平均获得的。本文中固有频率ω∈(0,1)，节点的位相φ的取值在0到2π之间均匀且随机分布。由于没有反相同步现象的存在，平均位相差的取值介于0(同步)到π/2(完全不同步)之间。将0到π/2之间的空间均匀划分m个，平均位相差落在第l个空间的节点对概率为Pl，那么利用式(2)就可以计算出复杂度：

(2)

其中，Sm为复杂度的最大可能取值，用于归一化，这时所有的平均位相差均匀地落在m个区间里，即Sm=lnm。本文取m=50。

1.2 随机交叉换边算法

我们的工作研究集聚系数和度分布对复杂度的影响，这就需要调节这两个网络结构参数，为了在调节的过程中这两者不互相干扰，采用随机交叉换边的方法[19-20]调节网络结构，在调节的过程中节点的度分布保持不变，而集聚系数却发生了改变。具体的操作过程是：随机找到两条边并断开，将这两个边交叉重新连接起来，如果经过这个操作网络的集聚系数变大(小)该操作就保留，否则撤销。重连过程要保证节点之间没有重复连边也不会连接到自身。重复上述操作直到获得足够大(小)的集聚系数。

2 集聚系数和度分布对复杂度的影响

由于WS型小世界网络和具有初始吸引度的无标度网络具有比较大的集聚系数，因此本文以这两种网络模型为研究对象，通过随机交叉换边的方法在保证度分布异质性不变的同时逐步降低网络的集聚系数。

2.1 小世界网络中的情况

在我们的工作中，取WS型小世界网络的规模为1 000，平均度为6，重连概率分别为0.001、0.01、0.1，保证网络具有小世界属性，这时对应的网络的平均集聚系数分别为0.68、0.66、0.50，平均度分布的方差μ分别为0.11、0.35、1.07。以这些网络为初始网络，对它们进行断边重连操作，只保留能使得集聚系数变小的操作，在重连的过程中记录下来一些典型的集聚系数下的网络结构，比如当集聚系数降到0.55，0.45，0.35，0.20，0.05时就记录下网络结构，并计算其复杂度S随耦合强度σ的变化关系，如图1所示。注意在同一幅图中，例如图1a，虽然这些网络的集聚系数不同，但是度分布是保持不变的，也就保证度分布的方差相同。图1a、b、c分别对应于重连概率为0.001，0.01，0.1的3类初始网络。可以看到在同一幅图中即使度分布的方差相同，不同的集聚系数也会使得复杂度曲线截然不同：集聚系数越大曲线越右移、上升段与下降段之间的宽度越大，并且集聚系数越大该现象越明显；同时注意到：集聚系数越大复杂度的最大值也越大，其所对应的耦合强度也是单调递增的，两者之间存在一一对应关系。产生该现象的物理机制如下：通过交叉换边网络的集聚系数逐渐减小，在此过程中网络的平均距离也逐渐降低，网络中节点之间的连边也越来越随机，使得网络的整体同步能力显著提高，在小的耦合强度下网络就能开始同步(复杂度增大)并迅速接近完全同步(复杂度减小)状态，网络中不会出现很复杂的同步状态(最大复杂度比较小)，这就使得网络的复杂度曲线表现出在小的耦合强度下就能提升并在达到峰值后迅速下降，上升和下降段之间的宽度不宽；但当集聚系数比较大时，网络中除了少量的长程连边外绝大多数的边还局限在小范围内，网络的平均距离还是比较大，耦合强度要比较大时网络才开始出现同步现象(复杂度曲线上升段右移)，增加耦合强度的取值只能使得团簇内部的同步状态变好却不能促进整体的同步，网络中出现复杂的同步状态(最大复杂度比较大)，耦合强度的持续增加也难以实现网络的完全同步(复杂度的取值依然较大)，这就是在大的集聚系数时复杂度曲线整体右移、峰值升高并且宽度变大的原因。上述结果表明在小世界网络中集聚系数对复杂度有很大的影响，大的集聚系数意味着更紧密的局部连接，更有利于网络中形成同步团簇，进而造成网络在很大的耦合强度范围内都能处在比较复杂的同步状态。

经过仔细观察还可以发现由于大的集聚系数所造成的复杂度曲线整体右移导致了在耦合强度比较小的区域在相同的耦合强度下集聚系数越大复杂度越小(如图1中的区域I所示)，在耦合强度很大的区域集聚系数越大复杂度越大(如图1中的区域III所示)，而当耦合强度介于两者之间时复杂度随集聚系数先上升后下降(如图1中的区域II所示)，复杂度存在最大值。区域I、II的分界线位于最小的集聚系数对应的复杂度曲线的最大值位置σ1，区域II、III的分界线位于最大的集聚系数对应的复杂度曲线的最大值位置σ2。为了更仔细地分析集聚系数对复杂度的影响，将两者的关系用曲线表示出来，如图2所示。图中明显表现出了对于3个不同的度分布方差，当耦合强度的取值小于σ1时复杂度随集聚系数的增加单调递减(所有的点都取在复杂度曲线的上升段)，当耦合强度的取值大于σ2时复杂度随集聚系数的增加单调递增(所有的点都取在复杂度曲线的下降段)，而当耦合强度的取值介于两者之间时复杂度的值表现为先升高(下降段)后降低(上升段)，由于复杂度的最大值与耦合强度之间存在一一对应关系，该曲线的最大值就是对应耦合强度的复杂度最大值。

为了分析度分布的异质性对复杂度的影响，重新排布了图1中的曲线，将集聚系数相同而度分布的方差不同的曲线画到了同一幅图里，如图3所示。有趣的是，即使度分布方差不同，只要集聚系数相同，同一幅图中的曲线都非常接近。分析造成这一现象的原因可能是度分布的方差差别不大，比如模拟中3条曲线的度分布方差分别为0.11、0.35和1.07，所有节点的度都非常接近。在后面的结果中可以证明本文分析的正确性。

2.2 具有初始吸引度的无标度网络中的情况

除了小世界网络，本文还研究了具有初始吸引度的无标度网络的情况，该网络的生成过程与经典的BA无标度网络类似，都是从初始的m个全连通的节点出发，只不过引入一个初始吸引度k0，即新加入的节点连接到已有节点的概率正比于已有节点的度与初始吸引度的和ki+k0，这样，通过调节k0的大小就可以获得具有不同幂指数的无标度网络。值得注意的是要求k0>-m+1，使得ki+k0>0。在模拟中同样采用网络的规模为1 000，平均度为6，而初始吸引度分别取-5.0，-4.0，-3.0，这时对应的网络的集聚系数分别为0.33、0.17、0.11，对应的网络的度分布方差分别为29.77、21.78、17.65。与具有相同的网络规模和平均度的WS小世界网络比较，此时集聚系数要小一些而度分布方差要远远大于小世界网络的度分布方差。图4给出了在度分布的异质性相同而集聚系数不同时网络的复杂度与耦合强度的变化关系，图4a、4b、4c分别对应初始吸引度为-5.0，-4.0，-3.0的网络。从图4可以看出：与小世界网络的情况不同，相同的度分布情况下集聚系数的不同没有造成复杂度曲线的明显差异。仔细观察就可以发现这是由于在该网络模型中集聚系数可调节的范围不是很大，以至于集聚系数的影响难以体现出来。

为了分析度分布的异质性对该网络的影响，在图5a-c中给出了集聚系数相同而度分布方差不同的情况下复杂度随耦合强度的变化曲线，从图5可以看出在相同的集聚系数下不同的度分布异质性使得不同的网络具有相接近的复杂度最大值，并且最大值对应的耦合强度也是重合的，但是当耦合强度偏离该最大值附近，复杂度处于上升和下降段时度分布的异质性更大的网络具有更大的复杂度。为了解释这一现象，计算了描述系统同步状态的序参量，序参量的定义如下：

(3)

其中，i为虚数单位，φj为第j个振子的相位，括号〈〉表示对时间取平均。当网络中各振子振荡的相位不相关时R=0，当所有振子达到同步时R=1，因此R越大，网络同步状态越好。在图5d中给出了集聚系数为0.11，而度分布方差分别为29.77和17.65的两个网络的序参量随耦合强度的变化关系。有趣的是耦合强度使得复杂度曲线差异比较大时对应的序参量曲线差异也比较大，而复杂度曲线差异比较小时对应的序参量曲线差异也比较小。但这两种曲线在耦合强度比较大和比较小的时候的排布顺序是不同的：对于复杂度曲线，大的度分布异质性总是对应着大的复杂度，但是对于序参量曲线，在耦合强度比较小时度分布异质性大的网络的序参量相对大，但不十分明显，而在耦合强度比较大时度分布异质性大的网络的序参量反而明显小。通过分析不难理解这种现象：当耦合强度比较小时，在度比较大的节点周围会形成同步团簇，并且度分布的异质性越大这种同步团簇越容易形成，这使得度分布异质性大的网络的序参量比较大并且复杂度也较大；当耦合强度比较大时，在不同大度节点周围形成的同步团簇不容易融合起来，并且度分布异质性越大越不容易融合，这就造成度分布异质性大的网络的同步状态更差但复杂度依然较大。

3 结论

本文以小世界网络和具有初始吸引度的无标度网络为模型，分析了集聚系数和度分布的异质性对复杂度的影响，研究发现：集聚系数能增大复杂度的最大值以及增大复杂度曲线中峰的宽度，而度分布的异质性不能增大复杂度的最大值却可以增大复杂度在上升段和下降段的值。在小世界网络中由于集聚系数取值范围比较大因此该参数对复杂度的影响比较明显；在无标度网络中，由于度分布的异质性有很大的调节空间因此该参数对复杂度的影响比较明显。我们的工作加深了人们对于网络结构对复杂度影响的理解，为设计合理有效的网络结构提供了新的理论基础。我们的工作目前仅考虑了网络的度分布的异质性和集聚系数对复杂度的影响，而刻画复杂网络结构的参数还有很多，比如度相关性、平均距离、网络的层次结构等，这些参数对复杂度的影响情况还不清楚，有待于进一步研究。

[1]Watts D J, Strogatz S H. Collective dy-namics of “small-world” networks[J]. Nature, 1998,393:440-442.

[2]Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science,1999, 286: 509-512.

[3]Buldyrev S V, Parshani R, Paul G, et al. Catastrophic cascade of failures in interdependent networks [J]. Nature, 2010, 464 (7291): 1025-1028.

[4]Petter H, Jari S. Temporal networks[J]. Physics Reports,2012, 519: 97-125.

[5]Barahona M，Pecora L M. Synchronization in small-world systems[J]. Phys Rev Lett， 2002，89(5)：054101.

[6]Nishikawa T, Motter A E, Lai Y C, et al. Heterogeneity in oscillator networks: are smaller worlds easier to synchronize?[J]. Phys Rev Lett，2003, 91(1): 014101.

[7]Arenas A, Diaz-Guilera A, Kurths J, et al. Synchronization in complex networks[J]. Phys Rep， 2008,469(3):93-153.

[8]Arenas A, Diaz-Guilera A, Perez-Vicente C J. Synchronization processes in complex networks[J]. Physica D， 2006,224:27-34.

[9]Gomez-Gardenes J , Moreno Y , Arenas A. Paths to synchronization on complex networks[J]. Phys Rev Lett，2007, 98(3):034101.

[10] Chen J, Lu J A, Wu X, et al. Generalized synchronization of complex dynamical networks via impulsive control[J]. Chaos,2009,19(4):043119.

[11] Liu H, Chen J , Lu J A , et al. Generalized synchronization in complex dynamical networks via adaptive couplings[J]. Physica A,2010, 389:1759-1770.

[12] Zhang J , Zhou C , Xu X , et al. Mapping from structure to dynamics: a unified view of dynamical processes on networks [J]. Phys Rev E,2010, 82(2):026116.

[13] Zhao M , Zhou C , Chen Y , et al. Complexity versus modularity and heterogeneity in oscillatory networks: combining segregation and integration in neural systems[J]. Phys Rev E,2010, 82(4):046225.

[14] Stam C J. Nonlinear dynamical analysis of EEG and MEG: review of an emerging field[J]. Clin Neurophysiol 116:2266.

[15] Scannell J W, Burns G A P C, Hilgetag C C, The connectional organization of the cortico-thalamic system of the cat[J]. Cereb Cortex，1999, 9:277-299.

[16] White J G, Southgate E, Thompson J N, et al. The structure of the nervous system of the nematode Caenorhabditis elegans[J].Philosphical Transactions of the Royal Society B Biological Sciences,2011,118(314):1-340.

[17] Dorogovtsev S N , Mendes J F F , Samukhin A N. Structure of growing networks with preferential linking[J]. Phys Rev Lett,2000, 85:4633-4636.

[18] Krapivsky P L , Redner S. Organization of growing random networks[J]. Phys Rev E,2001, 63(6):066123.

[19] Maslov S , Sneppen K. Specificity and stability in topology of protein networks[J]. Science,2002, 296:910-913.

[20] Kim B J. Coherent potential approximation and projection operators for interacting electrons[J]. Phys Rev E,2004, 69(4):045101.

(责任编辑 耿金花)

Effects of Clustering Coefficient and Degree Distribution on Complexity in Oscillator Networks)

LI Juexuan1,2，ZHAO Ming1)

(1.College of Physics and Technology, Guangxi Normal University, Guilin 541004, China； 2.Department of Physics and Information Science, Liuzhou Teachers College, Liuzhou 545004, China)

Complexity is defined to describe the partial synchronization state in complex networks, which is sensitive to the network structure, however, how the structure affects the complexity is still unclear. Clustering coefficient and degree distribution are two typical parameters in complex networks. In this paper, the effects of these two parameters on complexity are studied. After careful study it is found that increasing clustering coefficient would increase the maximal complexity and broaden the width of the complexity curves, and increasing the heterogeneity of the degree distribution will increase the value of rising and falling part of complexity curve but have no effect on the maximal complexity. Furthermore, complexity is sensitive to clustering coefficient in small-world networks and sensitive to heterogeneity of degree distribution in scale-free networks. Our work deepens the knowledge of complexity, and provide useful theory to design complex network structure.

complexity; clustering coefficient; degree distribution

10.13306/j.1672-3813.2016.04.005

2015-03-12；

2015-10-09

国家自然科学基金(11165003)；广西自然科学基金(2015GXNSFGA139009)；广西高校优秀人才资助计划项目

李珏璇(1964-),女,广西武宣人,高级实验师,主要研究方向为普通物理实验。

TP79

A