基于随机交叉机制的同步优化网络模型

王 丹，李彦平，郝彬彬

（1.沈阳大学装备制造综合自动化重点实验室，辽宁沈阳 110044；2.东北大学信息科学与工程学院，辽宁沈阳 110004）

基于随机交叉机制的同步优化网络模型

王 丹1，李彦平1，郝彬彬2

（1.沈阳大学装备制造综合自动化重点实验室，辽宁沈阳 110044；2.东北大学信息科学与工程学院，辽宁沈阳 110004）

在不改变网络度分布的前提下，采用随机交叉机制对网络的同步能力进行优化，提出了一种无标度网络的同步优化网络模型.在同步能力提高的过程中，观察网络匹配特性、聚类系数、特征路径长度和最大介数的变化趋势.仿真结果表明，对于类型Ⅰ无标度网络，最大介数与同步能力没有相关性，而对于类型Ⅱ无标度网络，最大介数随着同步能力的增加而减小.无论哪一种类型的无标度网络，网络同步能力增加时同配特性均降低.

复杂网络；同步优化；网络模型

目前研究网络结构特性与同步能力之间的关系是复杂网络同步问题研究的前提和热点之一.早期的关于同步能力的研究主要集中在具有完全规则拓扑结构的网络，其中的两个典型例子是耦合映象格子和细胞神经网络.随着小世界和无标度特性的提出，人们注意到复杂网络的拓扑结构对网络同步特性起着重要的作用，使得人们开始关注网络的拓扑结构与网络的同步化行为之间的关系，希望得到同步最优的网络结构.目前也有许多文献通过改变网络的拓扑结构来提高网络的同步能力［1-6］.Fan和Wang给出了演化网络的同步最优演化模型和同步优先演化网络模型，在同步最优演化模型中，每条新边的加入都选择使网络的同步化性能达到最优的节点相连.而在同步优化网络模型中，在每条新边加入时优先选取同步能力强的连接方式.同步最优演化模型和同步优化网络模型与BA无标度网络相比更容易实现同步.Fan等人提出的这两种模型，网络的规模是不断的增长的演化模型.

现有的研究表明，许多真实的网络都具有无标度特性，大部分的工作也都是针对无标度网络的结构特性对网络同步能力的影响进行的研究.基于随机重连，在网络的度分布固定不变的情况下，是否存在一种同步最优的网络结构呢？这种同步能力强的网络的结构特性如何？因此，本文在度分布不变的前提下，提出了基于随机重连的同步优化无标度网络模型.分别研究在提高网络的同步能力的同时，两种同步类型网络的结构特性与同步能力的关系.发现同配特性、聚类系数、最大介数和网络的特征路径长度等参数在网络同步能力增强的过程中不是单独的一个量发生了改变，而是整体都发生变化.

1 无标度网络的同步优化网络模型

目前有很多文献研究了各种特征参数与网络同步能力的关系.大部分真实网络都具有无标度特性，因此，这些研究工作主要集中在无标度网络特性的研究.通常都是改变网络的一个参数，研究对网络同步能力带来的影响.例如文献［7］基于随机重连调节聚类系数，研究聚类系数对网络同步能力的影响.文献［8］基于随机重连调节度相关特性，研究同配参数对网络同步能力的影响.受以上这几篇文献的启发，提出基于交叉重连机制的同步优化算法，而在整个交叉重连的过程中保证网络度的分布是固定不变的，得到的网络仍然是无标度网络.研究在网络同步能力逐渐增强的过程中，网络同步能力与网络匹配参数、聚类系数、特征路径长度和网络最大中心介数的关系.

无标度网络的同步优化算法如下：

（1）随机选择网络中存在的两条边e1＝x1x2和e2＝x3x4，使得x1≠x2≠x3≠x4，并且x1与x4之间、x2与x3之间不存在连接.

（2）交叉互换两条边，得到x1x4和x2x3，同时移除边e1，e2.

（3）对于类型Ⅰ网络而言，如果边的交叉互换能降低网络的第二大特征值λ2，则网络的同步能力得到增强，保留此次交叉连接.对于类型Ⅱ网络而言，如果边的交叉互换能降低网络的特征值比值R，则网络的同步能力得到增强，保留此次交叉连接.

重复以上的过程，就可以在保证网络度分布不变的前提下，提高网络同步能力，得到无标度网络的同步优化网络结构，在网络同步能力提高的同时，研究网络结构特性的变化.研究同配参数、聚类系数、特征路径长度、最大介数等对网络同步能力的影响.其中同配参数r是描述网络度分布的相关特性的参数，r＞0网络中度数大的节点更倾向于与度数大的节点相连时，网络是同配的.反之，r＜0表示整个网络呈现异配性，网络中度数大的节点更倾向于与度数小的节点相连，那么该网络是异配的；r＝0表示网络结构不存在相关性.r按照式（1）计算［9］.

聚类系数C主要用来衡量网络集团化程度，在网络特性中是一个比较重要的度量参数.网络的平均最短路径l，也称为网络的特征路径长度.目前对网络特征路径长度与网络同步能力的研究结果显示，大多数的作者指出网络的特征路径长度越短，网络的同步能力越强.另外，文献［10］指出网络的最大介数Bmax是衡量网络同步能力的标准.指出网络的最大介数越大，网络中单个节点的负载就越大，网络容易发生拥塞，使得整个网络的全局同步能力受到抑制，甚至不能实现同步.但是文献［11］指出，单独用一个最大介数Bmax来描述网络的同步能力是不确切的.文献［12］调节无标度网络的聚类系数，指出聚类系数越大网络的同步能力越差.而文献［8］研究了匹配参数对网络同步能力的影响，给出网络度相关的同配性增加时类型Ⅱ网络的同步能力降低，类型Ⅰ网络的同步能力增加.以上文献在研究网络结构和同步能力的关系时，通过改变网络的结构特性，观察对同步能力的影响.而这里我们关心的是度在分布固定的条件下，同步优化的无标度网络所具有的结构特性.

2 仿真分析

小世界网络就是指具有大的聚类系数和小的特征路径长度的网络，例如WS小世界网络模型和NW小世界网络模型.小世界现象是自然界普遍存在的特性，真实网络中还存在着另外一种特性，就是网络的无标度特性.例如BA无标度网络.但是BA无标度网络不具备高的聚类系数.现实生活中的网络很多同时具有无标度特性和小世界特性，因此，这里我们研究比较符合真实网络特性的高聚类系数的无标度网络.Holme-Kim（HK）模型是在BA无标度网络模型的基础上，引入了三角结构，提高了网络的聚类系数［13］.HK模型不仅具备与BA模型同样的度分布，同时又具有较高的聚类系数.HK模型可以通过参数0≤p≤1来调节网络的聚类系数.以HK模型为初始的网络模型，调节聚类系数的参数p选为0.5.网络的规模为N＝1 000，每个时间步加入到网络中的节点具有的边数为m＝3.采用本文所提出的无标度同步优化网络的算法.如果某一次的随机交叉连接提高了网络的同步能力，那么网络的结构进行一次更新.对网络的各个特征参数进行一次计算.不断的重复这个过程.仿真中采用t＝100 000次的交叉连接作为程序结束的判定标准.类型Ⅰ网络，采用降低耦合矩阵第二大特征值作为网络结构更新的判定标准.类型Ⅱ网络，采用降低耦合矩阵特征值比值作为网络结构更新的判定标准.

图1给出了类型Ⅰ网络结构特性与同步能力比较.图中，横坐标cv表示网络的结构更新次数.在程序运行过程中要符合第2节中所提出的三条标准，确保网络中的节点不能与自身相连，节点对之间也不存在重边，并且提高了网络的同步能力，才能更新网络结构，进行结构特性的统计.在网络结构不断变化的过程中，λ2越来越小，网络的全局同步能力增强.随着λ2减小的过程，观察网络其他特性的变化趋势.图1前四个子图分别表示网络的同配参数r，网络的聚类系数C，网络的最大介数Bmax以及网络的特征路径长度l.对于类型Ⅰ网络而言，在网络的同步能力不断增加时，网络的同配参数r越来越小，网络度数大的节点更倾向于与度数小的节点相连.网络的聚类系数和网络的平均最短路径都在不断的减小.网络同步能力增强时，网络明显的表现出聚类系数的降低和最短路径的减小.但是网络的最大介数Bmax与网络同步能力不存在明确的关系.甚至在第400～800次更新矩阵时，网络的最大介数时而增大，时而减小.而在这个过程中网络的同步能力是不断的增加的.

图1 类型Ⅰ网络结构特性与同步能力比较Fig.1 Relations between structure characteristics and synchronizability for TypeⅠnetwork

图2 类型Ⅱ网络结构特性与同步能力比较Fig.2 Relations between structure characteristics and synchronizability for TypeⅡnetwork

图2给出了类型Ⅱ网络结构特性与同步能力比较.网络以HK模型为初始状态，网络保持度分布不变，调节网络的连接结构，使得网络的特征值比值R不断减小.图2中，横坐标表示网络的迭代次数.确保网络中的节点不能与自身相连，节点对之间也不存在重边，并且降低了网络的特征值比值，才能更新网络结构，统计网络特征参数.在网络结构不断变化的过程中，R越来越小，网络的全局同步能力增强.随着R减小的过程，我们观察网络其他特性的变化.图2前四个子图分别表示网络的同配参数r，网络的聚类系数C，网络的最大介数Bmax以及网络的特征路径长度l.对于类型Ⅱ网络而言，在度分布不变的前提下，网络同步能力增强时，匹配参数、聚类系数、平均最短路径和网络的最大介数Bmax减小.

在度分布不变的前提下，两种同步类型网络的同步能力增加时，网络的匹配参数不断的减小.表面上看，我们的结论和文献［8］得到的结论并不一致，实际上两者的结论并不矛盾.文献［8］是单独调节匹配特性，研究其与同步能力的关系.而我们是研究同步优化网络结构具有的特性，网络的整体特性，包括聚类系数、最短路径等都发生了变化.整体的结构参数变化带来的同步能力的变化，网络同步能力的增加是网络整体结构特性共同作用产生的结果.研究网络整体结构特性对网络同步能力的影响，尤其是定量的给出公式化的描述，仍然是一个亟待解决的难点问题.

3 结 论

本文提出了一种基于交叉重连机制的同步优化模型.在网络度分布不变的前提下，采用随机交叉重连的机制对网络的同步能力进行优化，得到了无标度网络的同步优化网络模型.对于类型Ⅰ网络和类型Ⅱ网络，网络在同步能力增强时网络的非匹配特性增加，网络中度数大的节点更倾向于与度数小的节点相连.无论是哪一种同步类型网络，网络的同步能力越强，网络聚类系数和平均最短路径越小.类型I网络的最大介数与网络同步能力关系不明显，类型II网络随同步能力增强，网络的最大介数减小.

［1］Fan J，Wang X F.On synchronization in scale-free dynamical networks［J］.Physica A，2005，349：443-451.

［2］Fan J，Li X，Wang X F.On synchronous preference of complex dynamical networks［J］.Physica A，2005，355：657-666.

［3］Zeng A，Son S W，Yeung C H，et al.Enhancing synchronization by directionality in complex networks［J］.Physical Review E，2011，83（4）：045101.

［4］Yuan W J，Zhou C S.Interplay between structure and dynamics in adaptive complex networks：Emergence and amplification of modularity by adaptive dynamics［J］.

Physical Review E，2011，84（1）：016116.

［5］Watanabe T，Masuda N.Enhancing the spectral gap of networks by node removal［J］.Physical Review E，2010，82（4）：046102.

［6］Boccaletti S，Hwang D H，Chavez M，et al.Synchronization in dynamical networks：Evolution along commutative graphs［J］.Physical Review E，2006，74（1）：016102.

［7］McGraw P N，Menzinger M.Clustering and the synchronization of oscillator networks［J］.Physical Review E，2005，72（1）：015101.

［8］Di Bernardo M，Garofalo F，Sorrentino F.Effects of degree correlation on the synchronization of networks of oscillators［J］.International Journal Bifurcation and Chaos，2007，17，3499-3506.

［9］Newman M E J.Mixing patterns in networks［J］.Physical Review E，2003，67（2）：026126.

［10］Hong H，Kim B J，Choi M Y，et al.Factors that predict better synchronizability on complex networks［J］.Physical Review E，2004，69（6）：067105.

［11］Zhao M，Zhou T，Wang B H，et al.Relations between average distance，heterogeneity and network synchronizability［J］.Physica A，2006，371：773-780.

［12］Wu X，Wang B H，Zhou T，et al.Synchronizability of Highly Clustered Scale-Free Networks［J］.Chinese Physics Letters，2006，23（4）：1046-1049.

［13］Holme P，Kim B J.Growing scale-free networks with tunable clustering［J］.Physical Review E，2002，65（2）：026107.

Synchronization-optimal Network Model based on Random Interchanging Mechanism

WANG Dan1，LI Yanping1，HAO Binbin2

（1.Key Laboratory of Manufacturing Industrial Integrated Automation，Shenyang University，Shenyang 110004，China；2.College of Information Science and Engineering，Northeastern University，Shenyang 110004，China）

Based on random interchanging mechanism and restricting the degree distribution of network，the synchronization-optimal scale-free network model was proposed.During the course of enhancing synchronizability of network，the changing of assortative coefficient，clustering coefficients，characteristic path length and maximal betweenness were investigated.Simulations showed，there was no relativity between maximal betweenness and synchronizability of Type I network.However，maximal betweenness decreased as the increase of synchronizability of Type II network.Simulations indicated that the disassortative increased as the increase of synchronizability for both Types network.

complex network；synchronization-optimal；network model

N 94

A

1008-9225（2012）03-0043-04

2012-01-11

国家自然科学基金资助项目（61104029）.

王 丹（1979-），女，辽宁沈阳人，沈阳大学讲师，博士；李彦平（1958-），男，辽宁沈阳人，沈阳大学教授，博士.

王 颖】