动态复杂网络的同步拓扑演化

摘 要:

同步问题在信息通信、自动化控制、生物节律等诸多领域扮演着至关重要的角色，而复杂网络这一门新兴学科为同步问题的拓扑分析提供了新视角。

在定性讨论复杂网络模型的同步性能后，仿真分析了较大网络尺寸的情况，通过数据分析比对、网络拓扑的可视化和拓扑的模拟退火演化，寻找到了同步优化的一定规律，即度分布和平均距离均匀化、集中化；簇系数的适当调节对同步性能影响不大，但能减少网络连接等。结合未来智能电力网发展的实际情况，制定了同步稳定性优化策略，并在美国西部电力网数据上进行实验，探索从拓扑角度优化实际网络的应用价值，满足实时性、稳定性、分布式等要求。通过特征值比这一评价指标的对比证明优化有效。

关键词:

同步;复杂网络;特征值比;模拟退火;电力网

中图分类号:

TP393.02

文献标志码:A



Topological evolution on synchronization of dynamic complex networks



ZHU Liang, HAN Dingding*



School of Information Science and Technology, East China Normal University, Shanghai 200241, China

Abstract:

After qualitative discussion of the synchronization performance in complex network models, simulation analysis of the networks with relatively larger size was presented. Through data analysis, network topology visualization, and topology evolution with simulated annealing algorithm, some rules of synchronization optimization were found, that is, making the degree distribution and average distance uniform and centralized, and proper clustering coefficient can reduce network connection without influencing synchronization. Considering the situation of future power grid, optimization strategies for the stability of synchronization were developed and tested on the data of the actual power grid, exploring the application value of optimizing practical networks from the angle of topology and satisfying the requirement of realtime quality, stability and distribution. The optimization is proved to be effective.

Key words:

synchronization; complex network; eigeatio; Simulated Annealing (SA); power grid



0 引言

自然科学和社会科学中普遍存在着各种网络，如计算机网络、神经网络、社会网络、电力网络等。在网络特性指标中，同步性能与其他指标之间有着较为密切的联系，是研究的一个重要方向。同步在信息通信、自动化控制、生物节律等诸多领域扮演着至关重要的角色，相关理论有着广泛的应用。近几年来，同步稳定性以及它和网络拓扑之间的关系受到了尤其多的关注。由于实际网络往往处于动态变化之中，网络模型涵盖的范围须由静态拓展至动态。如何优化拓扑才能构建一个稳定同步的系统，或反之避免如信息网络拥塞、电力网级联故障等有害同步，这需要研究不同种类的网络拓扑，结合节点动力学系统及网络同步稳定性评价标准等多方面因素进行考虑。以网络的视角分析和解决问题已成为复杂系统和其他众多领域的有力工具之一。

关于同步稳定性的一个基础性结论由Pecora等提出，即主稳定函数(Master Stability Function)法［1］。在后续的工作中，小世界网络被证明比规则网络和随机网络更容易实现同步［2］。另有研究将无标度网络加入对比，在节点数小于30的网络尺寸下得到了一种同步性能近似最优的网络类型［3］。此外，还有以序参数作为同步性能评价标准对网络进行优化的尝试，发现在耦合强度为0.7时，此优化策略会产生两种不同的拓扑结构双稳态；但相比以特征值比作为评价指标的演化结果，后者能实现稳定同步的范围更广、程度更高［4］。

本文结合动态网络的同步模型和复杂网络模型分析了动态复杂网络同步模型的理论，重点关注同步问题中的拓扑因素，比较并选取了特征值比作为同步稳定性评价标准。通过对四种网络模型的模拟退火(Simulated Annealing, SA)演化，展示了度、平均距离、簇系数等基本特性与网络同步稳定性的较为规律性的结果。在增大网络尺寸的基础上，研究提升同步稳定性的动态拓扑演化，制定了优化策略应用于美国西部电力网数据，通过实证的方法证明优化策略的正确性与实用性。

1 动态复杂网络同步模型的理论分析

1．1 动态网络的同步模型



本文采用研究同步问题通常使用的动力学模型［1］，即由n个m维振子组成的系统，表达式为

i=F(xi)+σ∑nj=1LijHxj; i=1,2,…,n

(1)

其中：xi∈Rm代表第i个振子的状态向量;F代表节点自身的动力学影响;σ代表节点间耦合强度;Lij代表拉普拉斯矩阵对应元素，满足

(4)

本文主要关注网络拓扑，即耦合方程中L所包含的信息，故振子部分不再详述。

1．2 复杂网络模型的同步性能分析

本文采用了四种常用的网络模型：二维格子网络、随机网络、无标度网络和小世界网络。网络各个节点均放置相同的振子，所生成的模型用以模拟网络拓扑优化。早期的网络模型以规则网络和随机网络为主，对于真实世界中复杂网络的描述存在局限性。无标度网络和小世界网络模型是复杂网络理论的重要内容，能更好地吻合多种真实世界的网络。

网络除了点与边的简单关系外，还有诸如边的方向、点和边的权重、连通性等性质，本文考虑无向无权连通网络。另外还有以下几个重要的基本特性指标与同步性能密切相关。

1．2．1 度与度分布

度的概念是对于节点而言的。与一个节点相连的其他节点的个数即该节点i的度ki。度值大的节点往往承载更多的通信流量，重要性较高。但节点度值大可能导致信息拥塞，会对同步性能造成影响。

度分布描述网络宏观统计特性，即各种度值的概率分布。规则网络的度值比较单一，度分布很窄。随机网络和小世界网络的度分布多服从泊松分布；而无标度网络的度分布服从幂律分布，即P(k)~k－α。许多真实世界的网络是无标度的，一般α∈[2,3]。另外，所有节点的平均度也是网络宏观统计特性的另一个指标。

1．2．2 平均最短路径与直径

网络中任意两个节点i和节点j之间的最短路径为节点i到节点j所需经过的最少边数，定义为dij。对于整个网络来说，所有dij中最大的值即网络直径D。考察更多的特性是平均最短路径L，也称为平均距离。在真实世界的网络中，L相对于网络节点数n往往比较小，且随着n增大，L以n的对数甚至更慢的速度增大，显示出不同于规则网络和随机网络的特点。小的最短路径显然更容易实现同步。

1．2．3 簇系数

对于每个度值ki≥2的节点，若与该节点邻接的ki个节点之间存在E条边，而最大可能边数为12ki(ki-1)，则节点簇系数Cij定义为两者之比。在社会网络中，簇系数可以简单地理解为一个人的朋友之间相互也是朋友的比例。簇系数与同步性能也有关系。平均簇系数是对于整个网络而言的，真实世界网络的平均簇系数往往大于随机网络。

另外还有度—度相关性、簇—度相关性、最大连通子图、介数等其他网络特征量，以及拓扑和动力学之间的关系［5］，本文不再详述。一定条件下，小的平均距离和均匀的度分布是高同步性能的前提［6］，这一结论将在下文中进行检验。

1．3 同步性能评价指标

1．3．1 李雅普诺夫指数与序参数

李雅普诺夫指数是衡量系统动力学特性的一个重要指标。当指数大于零时，相空间中系统两个相邻轨道的初值即使非常接近，它们的差别都会随时间而按指数关系增加，这也是混沌系统的基本特点；反之则相邻轨道合并，对应于稳定的不动点和周期运动。该指数为负是评价网络同步稳定性的最弱判据，适用范围广，但无法保证同步状态中没有不稳定的数值集合，或吸引子中没有局部不稳定区域。两种情况都会导致系统不稳定，因而不是充分条件。

其中：Θ代表单位阶跃函数，dij代表t时刻两个节点的欧几里得距离，δ代表自行设定的阈值。在演化网络的同时可持续计算序参数值，同步性能以Q=1－μ(t∞)评价，其中t∞表征网络已稳定，μ(t)∈[0,1]。该指标适用于各种网络动力学的计算，但运算量很大［4］。

1．3．2 拉普拉斯矩阵特征值比

最为广泛使用且高效的同步稳定性评价指标是网络拉普拉斯矩阵的最大特征值与次小特征值的比值，本文也同样采用这个指标。如前文所述，连通网络的拉普拉斯矩阵性质下，可以得到特征值关系λmax>…>λ2>λ1=0，且均为实数。根据主稳定函数法［1］，上文所述耦合方程(式(1))可转化为

i=[DF(s)－σλiH]•ηi

(6)

其中DF(•)代表函数F的m阶Jacobian矩阵。在Rssler振子的条件下，解得所有λ须满足σλ∈(α1,α2)。因而有

特征值比越低，网络稳定性越高。本文在每次对拓扑进行动态演化时均计算网络拉普拉斯特征值比，以寻找最优拓扑及相关规律。

2 动态复杂网络同步模型的构建与实现

2．1 模型的构建

首先考察网络尺寸为100个节点的情况，其次增加为1024个节点。为便于对比，100个节点下的网络平均度均设定为4左右，使得总边数基本相等，网络的差别集中在拓扑上。

2．1．1 二维格子网络

规则网络的节点一般只与相近的节点邻接，即近邻耦合，有较大的簇系数和较长的平均距离。二维格子网络属于规则网络。例如在100个节点时，拓扑表现为10×10的方格，节点度分布集中在ki∈{2,3,4}。

2．1．2 随机网络

随机网络有较小的簇系数和较短的平均距离。为构建平均度为〈k〉的随机网络，对于n个节点，需要连接〈k〉n/2条边。而最大可连接边数为n(n－1)/2,故连边的概率为〈k〉/(n－1)。

2．1．3 无标度网络

无标度网络具有较大的簇系数和较短的平均距离。根据Barabási和Albert提出的模型［7］，设初始节点数为5，连接概率为0.8，产生一个随机网络，然后逐个添加节点。为使平均度约为4，令每个新加入的节点连接2条边，每次连接一个已有的节点的概率正比于该节点的度。以此进行的网络增长模式模拟了真实世界网络的形成，期间新节点择优连接到度值更大的节点。无标度网络同规则网络一样，无需考虑连通性的问题。

2．1．4 小世界网络

小世界网络介于规则与随机之间，同样具有较大的簇系数和较短的平均距离。按照Watts等［8］提出的小世界网络生成方法，首先构建一个度为4的环状规则网络，每个节点只和与它最近的4个节点相连。之后进行重连——对于每一条边，以0.5的概率决定是否重连这条边；原先均为短程连接的拓扑将变为混合有中程连边和长边的情形。在真实世界网络中往往也是这样，一个节点主要与附近的节点有连接，另外有少量远处的节点与之有直接关系，大大减少了通信传递次数。

例如社会关系网就是一个很好的例子，有实验证明世界上任

何两个人之间平均只要经过5个人就能联系上。



2．2 模型的实现与特性分析

构建二维格子网络、随机网络、无标度网络、小世界网络四种网络模型。考虑到含随机因素的网络存在涨落，四种网络的各种基本性质指标均通过程序进行200次计算取平均，例举在表1和表2内，作为后续研究参考。从簇系数、平均距离等比较来看，生成的模型符合上文所述基本特性，正确可用。拓扑的可视化以100个节点为例，如图1。

3 拓扑演化与结果分析

生成网络后，按照拉普拉斯矩阵特征值比这一同步稳定性评价指标，运用模拟退火算法寻找近似最优拓扑，观察网络基本性质指标的变化以及拓扑外观的改变规律。演化过程采用随机重连边的方法，每次重连边数的数量级为n,按［1,n］的-1次幂概率分布产生重连边数。重连过程中保证节点间最多仅有一条连边，也不产生自环，且整个网络保持连通。

3．1 模拟退火算法

动态复杂网络的演化是寻找同步稳定性最优拓扑的过程，其中“解”指代拓扑。初始解即初始拓扑；当前解为当前最优拓扑，存放当前接受的解;新解即最新接受的最优拓扑。初始温度等于4ΔQmax,其中热能Q即拉普拉斯矩阵特征值比，ΔQmax为100次预演化结果中Q的最大值与最小值之差。模拟退火过程中，新解在当前解的基础上产生，每次演化所得新解的Q与当前解的Q进行比较,差值为dQ。若新解的热量低于当前解的热量，则接受新解;反之，则以概率exp(－dQ/T)接受新解，不接受时维持当前解。一般在每个温度值上演化满5000次或连续接受500次作为当前温度演化的结束，降温10%。当总演化次数达到500000或温度低于10－7时，退火结束，认为找到了近似最优解。

模拟退火算法虽然是一种贪心算法，但它根据物理系统倾向于往能量较低状态变化的规律，以概率p(dE)选择对降温有更好效果的状态，加速其准确落到最低态，并减少热运动的妨碍。同时，算法会以一定的概率接受比当前解差的解，提供跳出局部最优解的机会，增加找到全局最优解的可能。此概率不断减小以保证结果趋向稳定。其中，温度范围、产生解的次数上限等参数的选取以问题规模以及经验值为参考，并根据结果收敛程度和算法耗时进行评价。改变参数会对模拟退火的准确性和速度等产生影响，如退火时间过短造成只能得到局部最优解，或降温过慢导致退火耗时增加等。

3．2 网络特征值比演化结果

根据100个节点网络的小尺寸等特点，结合经验值并通过多次实验对比，得到了较优的参数配置：统一选择演化上限为100000次，初始温度和结束温度分别为100和10－15,每个温度下演化上限为500次或连续50次接受。演化结果如图2所示。横坐标没有绘制所有100000次演化，而仅绘制了接受的演化，但由于接受次数仍然较多，故横坐标采用对数形式。

图片

从演化结果可以看到，四种网络最终都基本达到了收敛，特征值比均降低到了较低的程度。值得注意的是，初始拓扑下随机网络的同步稳定性要优于无标度网络，小世界网络性能最优;无标度网络和小世界网络虽然在初值上存在较大差异，但最终展示了相似的演化特征。

3．3 网络基本指标

3．3．1 度分布变化

如图3所示，尺寸均为100个节点的四种网络演化前后度分布对比十分明显，优化后的度分布有明显的分布规律，即都基本在平均度值周围形成钟形分布。可见，同步稳定的网络倾向于均匀且较窄的度分布。

3．3．2 其他基本性质指标

如表3所示，数据中斜杠前后分别为演化前后各网络基本性质指标的变化。可以明确地看出，模拟退火算法有效地找到

了特征值比相当低的拓扑，使得各网络特征值比大大降低。

对于平均距离而言，似乎并非越小越好，而是落在3.5附近;

网络直径也基本下降为5~6。总体而言，与度分布的情形类

似，指标的值分布在较窄的一个范围内。最特别的结

果是簇系数，几乎全部降为0，说明三个节点的小环对同步稳

定性有反作用。

3．3．3 演化结果的拓扑外观

如图4所示，演化后，四种网络拓扑外观趋于一致。结合度值、平均距离的均匀化、分布窄化的情况，网络拓扑趋于球状，节点趋于等价。与演化前的对比参见图1。

3．4 无标度网络特征值比与平均度的关系

如图5，在同样的100个节点的网络尺寸下，对无标度网络分别以平均度为4、8、16三种情况进行演化，演化策略同上文。可以发现，同步稳定性显然随着平均度的增大而增大；但同时也可以认为，只要对拓扑进行足够的优化，少量的边也可以近似实现大量边的同步稳定性效果，从而节约网络建设成本。

4 美国西部电力网分析与优化

4．1 电力网研究分析

结合网络同步理论对电力网进行研究的动机来源于最近几年信息物理融合系统(CyberPhysical System, CPS)概念的提出。信息物理融合系统是网络信息技术与物理世界相连接的系统，旨在使大规模分布式系统更高效地进行监视、控制与数据采集等工作，实时可靠地与物理世界交互，并且有一定的抗干扰甚至抗破坏的能力［9］。

电力网自诞生以来基本保持着单向输电模式。级联故障导致大规模停电事故等问题不容忽视。早期的研究方法主要以经典的基尔霍夫方程和规则拓扑结构为基础；随着复杂网络理论的发展，近十多年来已有不少交叉研究，如将发电站、变电站、负荷等设施作为节点，输电线作为边，揭示其小世界特性。后续的工作主要集中在网络鲁棒性问题上，关注电力网的级联故障和抗毁性能。近期有研究等考虑了电流方程和隐蔽故障等电网因素，建立了一个更贴近实际的模型［10］。未来智能电网是CPS的一项重要内容，为了加入风能、太阳能等分布式能源，并继续提高网络可靠性，监控和通信的需求越来越多，电力通信网融合进电力网的程度不断加深。网络上能量和信息的传递变得更为复杂，拓扑也由单一电力线网络变得更为多样，同步问题显得至关重要。

本文采用含有4941个节点的美国西部电力网数据作为研究对象，为小世界网络。如图6所示，其度分布符合指数分布。

4．2 大尺寸网络的演化

首先分别在平均度为2和4的条件下对1024个节点的小世界网络进行优化仿真，使网络尺寸与真实电力网数据具有可比性。平均度值过低可导致网络特征值比大幅提高，不利于稳定同步。在大尺寸网络的演化过程中，为降低运算量，将演化时间缩短到可行的范围，模拟退火的次数进行了适当缩减。但相比小尺寸网络，大尺寸网络展现了同样的度值(如图7(b)和图8(b))、簇系数等基本特性变化趋势。平均度为2的网络由于太过稀疏，演化前后簇系数基本都为0，平均度为4的网络簇系数由0.0634降低至0.0021。网络尺寸扩大后的演化结果与小尺寸网络的情形类似。

4．3 电力网优化策略与实施

由上述所有结果，归纳网络优化规律如下：以平均度值为中心对称，使度分布均匀化；尽量降低簇系数；适当增加连边，降低平均距离。考虑到实际电力网改造的限制，模拟退火的演化方式改动过于随机，且幅度较大，故结合电力网数据，制定具体策略如下：第一步，对于度值大于10的节点，每个节点分裂为4个节点，原有的连边均匀分配给各分裂节点，例如度为20的节点，变为每个分裂节点连接5条边；4个分裂节点再连成四方的环状，因而不增加簇系数，最终每个分裂节点度为7。第二步，对于大量度值为1的节点，随机选取10%的点连接到度为2的节点；度值为2的节点，随机选取10%的点连接到度为4的节点。第三步，查找3个节点形成的簇，均随机断开一条边，使簇系数为0。

在此优化策略下，第一步利用分裂节点的方法在减少高度值节点的同时提高了网络鲁棒性，分裂节点的关键在于减少重要节点失效造成的影响；第二步通过连边减少低度值节点；第三步降低簇系数的同时又减少了连边。优化过程的度分布变化如图9，遵循了优化规律。电力网特征值比初始为26487，随演化步骤分别变为17002，713.64，759.23，得到了相当大的降幅。节点数从4941增加到5019，边数从13188降低到13144；平均度由2.67降低到2.61。可见在网络尺寸略微增大的情况下，反而减少了连边，并获得了更好的同步稳定性。

图9 电力网优化过程的度分布变化

就实际电力网而言，由于其本身具有小世界网络特性，保证了优化策略实施的有效性与可行性。分裂高度值节点(如在主电站周围建设分布式发电站)在使度分布均匀化的同时也提高了网络的鲁棒性，恰恰顺应了未来电力网发展的“去中心化”趋势，满足CPS概念下实时性、可靠性和分布式等要求；对电网进行小比例的输电线或拓扑改造将产生一定的成本开销，但总体减少的连边数意味着电网整体建设成本的降低，因此优化具有实际意义，类似的设计与优化是研究的有益方向。

值得注意的是，簇系数的主动降低并未提高同步性能，反而小幅增大了特征值比，值得进一步研究。度分布的均匀化的确与同步稳定性正相关，与此前研究观点一致。

5 结语

本文从动态复杂网络模型着眼，分析了同步稳定性与网络拓扑之间的关系，选择了合适的动力学模型以及拉普拉斯矩阵特征值比这一同步稳定性评价标准。通过定性的分析和定量的计算，研究了四种常用复杂网络模型中与同步相关的特性。相似初始条件下，小世界网络有着最好的同步稳定性。运用模拟退火算法对四种模型进行了同步拓扑演化，显示提高同步性能较为普适的优化规律是使网络均匀化，即度分布和平均距离都需均匀化、集中化；簇系数的降低可能是同步性能提高的必要非充分条件，但可以减少连边数和平均度。

在扩大网络尺寸进行仿真的基础上，本文验证了上述优化规律。通过实证方法，根据规律制定优化策略，应用到了美国西部电力网真实数据中，面向CPS分布式、实时性、鲁棒性等要求，提出了未来电力网的可能拓扑，即通过增加低度值节点的连边数和分裂高度值节点实现度分布均匀化，同时降低簇系数以减少网络建设成本。

(下转第339页)

推荐访问:拓扑 演化 同步 动态 网络