基于混合模式的BA无标度网络同步研究

李 云，宋运忠

(河南理工大学电气工程与自动化学院，河南 焦作 454000)

0 引言

复杂网络广泛存在于自然界和社会中，物流网络、交通运输网、电力传输网、基因网络、互联网以及通信网络等都属于复杂网络[1-6]。现实中，许多复杂系统可以看作是由多个相互作用的节点构成的网络。复杂网络是复杂系统的一种抽象，以抽象的复杂网络来研究复杂系统，不仅可以深入了解复杂系统的拓扑结构，还可以深入研究复杂系统的集体动力学行为，这对认识以及研究社会和自然界中的各种复杂系统具有非常重要的意义。同步现象作为复杂系统集体动力学行为中一种特殊的表现形式，广泛存在于各类复杂系统中[7-8]，而且系统不同，同步的意义也会有所不同，有的同步对系统产生积极的影响，而有的同步则对系统产生消极的影响。网络的拓扑结构对同步特性有很大的影响[9-16]，所以复杂网络的同步特性与拓扑结构关系的研究也引起了广大学者的关注。

研究发现许多实际网络的节点度分布函数具有幂律形式，这类网络被称为无标度网络。因为BA无标度网络的泛在性，它的同步现象引起学者们极大的兴趣[17-23]。文献[24]基于同步判据研究了BBV加权网络的度分布异质性、连接密度和网络同步能力之间的关系，给出了复杂网络新的测度——连接密度。文献[25]运用非线性系统理论、稳定性理论等研究了无标度网络的同步过程，在网络的每个节点上引入非线性动态方程，从而判断节点是否能同步，研究结果表明，度的不均匀分布性不仅导致无标度网络的同步性能下降，而且使得它的同步过程具有分层过渡的特点。文献[26]研究了连续时间动态无标度网络的同步问题，提出了最优同步的拓扑模型。

复杂网络的同步研究和多智能体系统一致性研究几乎同步开展，两者相互促进。文献[27]引入了一个新的概念，以统一的方式解决了多智能体系统的一致性和复杂网络的同步问题。文献[28]研究了集群网络的一致性问题，运用图论，线性矩阵不等式，李雅普诺夫函数讨论了系统的线性一致协议，给出了系统达到一致的充要条件，并分析了系统的稳定性，收敛速度，衰减率。文献[29]研究了一类多智能体系统在牵制控制下的群一致性问题，提出了融合群内信息交互、群间信息交互和牵制控制器的一致性协议。对固定拓扑下的二群组智能体系统和切换拓扑下的多群组智能体系统，利用稳定性理论和图论分别给出了适用于任意拓扑结构的充要条件，使得智能体系统在所提协议和牵制控制器的联合作用下实现预期的群一致。受以上文献的启发，本文拟将文献[28]中多智能体的复位算法用于BA无标度网络的同步研究。在本文中把BA无标度网络中的节点分成多个集群，每个集群中都有一个特殊的节点，被称作领导节点，其它节点均为跟随节点。定义第一个集群内有且仅有一个节点，且只与其它集群的领导节点进行群间信息交互，故称其为虚拟领导节点，命名为0号虚拟领导节点；除第一个集群外，其它集群内均包含多个节点，每个集群的领导节点不仅与其它集群的领导节点进行群间信息交互还与该集群的跟随节点进行群内信息交互，故称之为实体领导节点。也就是说，我们设计了混合模式的领导节点来共同解决BA无标度网络的同步问题。假设该BA无标度网络的拓扑结构是固定不变的(至少BA无标度网络会在一个确定的时间段内保持一定的拓扑结构，进而对应确定的功能，故该种假设是有意义的)，用实数值表示每个节点的状态，每个集群内部的节点之间以相同的权重相互作用，每个节点的状态值连续不断地变化，设计准周期的离散控制器对所有的领导节点进行复位，并假设复位行为发生在特殊的时刻，多个时刻则构成了准周期复位序列。在复位时刻，由领导节点完成群间信息交互，并更新各领导节点的状态值；在非复位时刻，同一个集群内的节点进行群内信息交互，并逐渐达到集群内部的同步，不断重复这个过程，最终BA无标度网络中所有节点达到同步，且网络中各节点同步后的状态值只与各个节点的初始状态值和网络拓扑结构有关。本文中的准周期离散控制器与文献[29]中的牵制控制器是不同的，本文中对领导者的复位作用只发生在复位时刻瞬间，该作用是准周期离散的，而文献[29]中对部分节点施加的控制作用持续在整个一致性过程中。相较于文献[29]，本文中控制器的优点在于：可以更加节约网络资源以及能量；同时，由于减少了一部分节点之间的通讯量，所以在一定程度上提高了网络的安全性。

BA无标度网络广泛存在于社会和自然界中，其拓扑结构的严重不均匀分布性影响着整个网络的集体动力学行为。有很多实际的网络背景与BA无标度网络相对应，因此对它的研究具有重要的理论意义和现实意义。

1 问题描述

用有向图G=(V,E)描述BA无标度网络的拓扑结构，顶点集V表示一组节点，边集E⊂V×V表示它们之间的相互作用关系。如果图G中任意两个节点之间至少存在一条路径，那么就称该图是强连通图。

本文主要研究基于混合模式的BA无标度网络的同步问题。把BA无标度网络中的节点分成m+1个强连通集群β0,β1，…βm，并假设集群β0中有且仅有一个节点，且定义为0号领导节点l0。每个集群都有一个特殊的节点，被称作领导节点，在下文中用li∈βi,∀i∈{0,1,…,m}表示，剩余的节点称作跟随节点，用fj表示。领导节点的集合为L={l0,l1,…,lm}，其中l0只与其它的领导节点之间有信息交互，故称其为虚拟领导节点；tk,k≥1不仅与集群的领导节点之间有信息交互，还与该集群的跟随节点有信息交互，故称之为实体领导节点；即运用了混合模式的领导节点研究了无标度网络的同步问题。在规定的时刻瞬间tk,k≥1(称之为复位时刻)，多个领导节点按照预先设定的相互关系图El⊂L×L相互作用。为了表达简洁清晰，我们认为领导节点是集群的第一个元素，具体表示方法如下：

β0={l0}

βi={li,fmi-1+2,…,fmi},∀i∈{1,…,m}

(1)

其中，m0=0,mm=n。上述的表示方法可以简洁明了地看出该网络中节点总数为n+1。

例1 举例说明式(1)，一个简单BA无标度网络有4个节点，其网络拓扑图如图1所示，从图中可以看出β0中有且只有一个节点，β1中有3个节点，表示为：β0={l0},β1={l1,f2,f3}。其中l0、l1为领导节点，f2、f3为跟随节点，具体分类如表1所示。由图1可看出群内信息交互和群间信息交互的方式是不同的，在非复位时刻，集群β1，…βm内的节点在拉普拉斯矩阵L的作用下进行群内信息交互，并逐渐达到集群内部的同步，在复位时刻，随机矩阵Pl对所有的领导节点复位，以此来完成群间信息交互。

图1 示例网络拓扑图

虚拟领导节点实体领导节点跟随节点l0l1f2 f3

用线性复位系统描述全部的网络动态：

(2)

(3)

(4)

其中，L(i,j)用来表示集群内部的节点之间相互作用时，节点i状态修正过程中对节点j的状态作用的权重。Pl (i,j)用来表示所有的领导节点之间相互作用时，节点i状态修正过程中对节点j的状态作用的权重。

而且拉普拉斯矩阵L具有以下对角矩阵的结构：

(5)

其中，Li1(n+1)i=0(n+1)i且Pl1m+1=1m+1。由于βi,i=0,1,…,m和Gl是强连通的，0和1分别是每一个Li和Pl的简单特征值。

2 同步行为

假设该类BA无标度网络中拓扑结构固定不变，且集群内部的节点之间相互作用的权值固定为1，用一个实数值表示网络中每个节点的状态，设计合理的控制法则，使BA网络中所有节点状态都达到同步。

介绍以下两个向量：

(6)

(7)

其中，x*(t)是时变的阶跃函数，x*(t)=x*(k) ∀t∈(tk,tk+1)。

命题1系统(2)的L和pl分别由(3)(4)定义，故：

uTx*(t)=uTx*(0)， ∀t∈R+

(8)

说明：

x*(t)=Wx(t) ∀t∈R+Τ。

(9)

既然wi=(wil,wif)，在此定义一个置换矩阵T,且WTT=U=(U1,U2)。矩阵U1是相当于领导者wi,l的对角矩阵，矩阵U2是相当于跟随节点wi,f的块对角矩阵，即：

(10)

(11)

故式(9)可以写成

x*(t)=WTTx(t)=U·(xl(t),xf(t))

(12)

故

(13)

公式(13)左右两边同时乘t∈(tk,tk+1)，由uTU1=vT和vTPl=vT得到：

(14)

由注释1可知对∀t∈(tk,tk+1)，x*(t)都保持稳定，有：

uTx*(t)=uTx*(0) ∀t∈R+

(15)

推论1系统(2)的L和Pl分别由(3)、(4)定义，假设BA网络中所有节点的状态都达到同步，且所有节点同步后的最终状态是：

(16)

注释2网络中节点同步后的最终状态仅与系统矩阵的L，Pl相关，与复位序列Τ无关。

3 仿真结果与分析

假设一个BA无标度网络，共有11个节点，分为两个集群β0、β1，集群β0内有且仅有一个节点，集群β1中有十个节点。根据节点的度，可以把集群β1中的节点分为4类：度为1的节点：①；度为3的节点：⑧、⑨、⑩；度为4的节点：②、③、⑥、⑦；度为8的节点：④、⑤。其网络拓扑图如图2所示，其中图a中假设①号节点为集群β1的领导节点且其度为1；图b中假设⑧号节点为集群β1的领导节点且其度为3；图c中假设②号节点为集群β1的领导节点且其度为4；图d中假设④号节点为集群β1的领导节点且其度为8。图2中四种情况对应的节点分类如表2所示。

复位序列由δ= 0.5,δ'k在Δ=[0,0.2]上任意选取给定。网络系统的初始条件为x(0)=[2,5,6,7,8,9,10,11,12,13,14]。

图2 11个节点的BA无标度网络拓扑图

虚拟领导节点实体领导节点跟随节点012 3 4 5 6 7 8 9 10

b 实体领导节点为⑧号节点

c 实体领导节点为②号节点

d 实体领导节点为④号节点

由于BA无标度网络中拓扑结构固定不变，且集群内部节点之间相互作用的权值相同，所以定义系统(2)中的L、Pl为以下值：

(17)

图3 BA无标度网络同步过程图

网络中所有节点的同步过程如图3所示，领导节点分为虚拟领导节点(Virtual Leader)和实体领导节点(Entity Leader)，由图中可以看出在复位时刻，虚拟领导节点和实体领导节点进行群间信息交互，领导节点的状态均发生了状态转移即进行了复位，且该行为是间断的；当不在复位时刻时，集群内部节点进行群内信息交互，且该行为是持续的。其中图3a中①号节点为集群β1的实体领导节点，该节点的度为1；图3b中⑧号节点为集群β1的实体领导节点，该节点的度为3；图3c中②号节点为集群β1的实体领导节点，该节点的度为4；图3d中④号节点为集群β1的实体领导节点，该节点的度为8；对比以上4张图可以看出，BA无标度网络的同步速度与实体领导节点的度有关，从仿真结果来看，实体领导节点的度越高其同步速度越快。

4 结论

本文根据代数图论和控制理论研究了基于混合模式的BA无标度网络的同步问题。首先，用集群网络表示BA无标度网络，把BA无标度网络划分成几个相互之间不连通的集群，每个集群内部都有一个受外界控制的节点，被称为领导节点，领导节点从形式上分为虚拟领导节点和实体领导节点，提出了混合模式领导节点的概念。然后，运用图论中的有向图描述了BA无标度网络的拓扑结构，用实数值表示网络中每个节点的状态，并给出了网络系统的一阶动力学模型，设计了准周期的离散控制器，控制BA无标度网络的同步过程。最后，用11个节点组成的BA无标度网络进行计算机仿真，阐释了同步理论的正确性，并分析了网络的同步速度与实体领导节点度之间的关系，从仿真结果来看，实体领导节点的度越高其同步速度越快。

[1]李靖,张永安. 复杂网络理论在物流网络研究中的应用[J]. 中国流通经济,2011,25(5):38-42.

Li Jing, Zhang Yongan. The Consideration on quantitative positioning of performance evaluation and the choice [J]. China Business and Market, 2011, 25(5):38-42.

[2]徐凤,朱金福,杨文东. 复杂网络在交通运输网络中的应用研究综述[J]. 复杂系统与复杂性科学,2013,2(1):18-25.

Xu Feng, Zhu Jinfu, Yang Wendong. The complex networks application in transportation networks: a survey [J]. Complex Systems and Complexity Science, 2013, 2(1):18-25.

[3]蔡泽祥,王星华,任晓娜. 复杂网络理论及其在电力系统中的应用研究综述[J]. 电网技术,2012,36(11):114-121.

Cai Zexiang, Wang Xinghua, Ren Xiaona. A review of complex network theory and its application in power systems [J]. Power System Technology, 2012, 36(11):114-121.

[4]王欢. 复杂网络理论在疾病研究中的应用[J]. 高教学刊,2015,(20):36-38.

Wang Huan. The complex networks application in disease research [J].Journal of Higher Education, 2015, (20):36-38.

[5]许丹,李翔,汪小帆. 复杂网络理论在互联网病毒传播研究中的应用[J]. 复杂系统与复杂性科学,2004,1(3):10-26.

Xu Dan, Li Xiang, Wang Xiaofan. Application of complex network theory to the study of virus spreading on the internet [J]. Complex Systems and Complexity Science, 2004, 1(3):10-26.

[6]徐玉章,朱磊,张力. 基于复杂网络理论的军事通信网信息传播模型[J]. 军事通信技术,2015,8(2):40-44.

Xu Yuzhang, Zhu Lei, Zhang Li. Information diffusion model of military communication network based on complex network theory [J]. Journal of Military Communications Technology, 2015, 8(2):40-44.

[7]丰俊妍,李文学,王克. 网络上复杂耦合系统的同步[J]. 黑龙江大学自然科学学报,2014,31(3):281-286.

Feng Junyan, Li Wenxue, Wang Ke. The synchronization of complex coupled systems on networks [J]. Journal of Natural Science of Hei long jiang University, 2014, 31(3):281-286.

[8]蒋国平,樊春霞,宋玉蓉,等. 复杂动态网络同步控制及其在信息物理系统中的应用[J]. 南京邮电大学学报(自然科学版),2010,30(4):41-51.

Jiang Guoping, Fan Chunxia, Song Yurong, et al. Synchronization and control of complex dynamical networks with applications in cyber-phy-sical systems [J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science), 2010, 30(4):41-51.

[9]陈姚, 吕金虎. 复杂动态网络的有限时间同步[J]. 系统科学与数学, 2009, 29(10):1419-1430.

Chen Yao, Lv Jinhu. Finite time synchronization of complex dynamical networks [J]. Journal of Systems Science and Mathematical Sciences, 2009, 29(10):1419-1430.

[10] Xu Y H, Zhou W N, Zhang J C, et al. Topology identification of complex delayed dynamical networks with multiple response systems [J]. Nonlinear Dynamics, 2017, 88(4):2969-2981.

[11] Khanzadeh A, Pourgholi M. Fixed-time sliding mode controller design for synchronization of complex dynamical networks [J]. Nonlinear Dynamics, 2017, 88(4):2637-2649.

[12] Dai H, Chen W, Jia J, et al. Exponential synchronization of complex dynamical networks with time-varying inner coupling via event-triggered communication[J]. Neurocomputing, 2017, 245(5):124-132.

[13] 张峥,朱炫颖. 复杂网络同步控制的研究进展[J]. 信息与控制,2017,46(1):103-112.

Zhang Zheng, Zhu Xuanying. Recent progress in the synchronous control of complex networks [J]. Information and Control, 2017, 46(1):103-112.

[14] 刘洲洲,王福豹. 一种能耗均衡的无线传感器网络加权无标度拓扑研究[J]. 物理学报, 2014, 63(19):51-58.

Liu Zhouzhou, Wang Fubao. Research on weighted scale-free topology with balancing energy consumption characteristics in wireless sensor networks [J]. Acta Phys Sin, 2014, 63(19):51-58.

[15] 邓宏钟,吴俊,李勇,等. 复杂网络拓扑结构对系统抗毁性影响研究[J]. 系统工程与电子技术,2008,30(12):2425-2428.

Deng Hongzhong, Wu Jun, Li Yong, et al. Influence of complex network topologic structure on system invulnerability [J]. Systems Engineering and Electronics, 2008, 30(12):2425-2428.

[16] 赵永毅, 史定华. 复杂网络的特征谱及其应用[J]. 复杂系统与复杂性科学, 2006, 3(1):1-12.

Zhao Yongyi, Shi Dinghua. Spectra of complex networks and its applications [J]. Complex Systems and Complexity Science, 2006, 3(1):1-12.

[17] 章忠志,周水庚,方锦清. 复杂网络确定性模型研究的最新进展[J]. 复杂系统与复杂性科学,2008,5(4):29-46.

Zhang Zhongzhi, Zhou Shuigeng, Fang Jinqing. Recent progress of deterministic models for complex networks [J]. Complex Systems and Complexity Science, 2008, 5(4):29-46.

[18] 王筱莉,赵来军,谢婉林. 无标度网络中遗忘率变化的谣言传播模型研究[J]. 系统工程理论与实践,2015,35(2):458-465.

Wang Xiaoli, Zhao Laijun, Xie Wanlin. Rumor spreading model with variable forgetting rate in scale-free network [J]. Systems Engineering Theory & Practice, 2015, 35(2):458-465.

[19] 何敏华,张端明,王海艳,等. 基于无标度网络拓扑结构变化的舆论演化模型[J]. 物理学报,2010,59(8):5175-5181.

He Minhua, Zhang Ruiming, Wang Haiyan, et al. Public opinion evolution model with the variable topology structure based on scale free network [J]. Acta Phys Sin, 2010, 59(8):5175-5181.

[20] 焦长义,穆华平,李静. 基于高聚集性无标度网络模型的微粒群算法[J]. 复杂系统与复杂性科学,2010,07(1):82-87.

Jiao Changyi, Mu Huaping, Li Jing. Particle swarm optimization with highly-clustered scale-free network model [J]. Complex Systems and Complexity Science, 2010, 07(1):82-87.

[21] 潘灶烽,汪小帆. 一种可大范围调节聚类系数的加权无标度网络模型[J]. 物理学报,2006,55(8):4058-4064.

Pan Zhaofeng, Wang Xiaofan. A weighted scale-free network model with large-scale tunable clustering [J]. Acta Phys. Sin, 2006, 55(8):4058-4064.

[22] 李增扬,韩秀萍,陆君安,等. 内部演化的BA无标度网络模型[J]. 复杂系统与复杂性科学,2005,2(2):1-6.

Li Zengyang, Han Xiuping, Lu Junan, et al. A BA scale free network model with inner evolving [J]. Complex Systems and Complexity Science, 2005, 2(2):1-6.

[23] 陈禹,宗骁,郝杰,等. BA模型的三种扩展[J]. 系统工程学报, 2005, 20(2):120-127.

Chen Yu, Zong Xiao, Hao Jie, et al. Three extensions for BA model [J]. Journal of Systems Engineering, 2005, 20(2):120-127.

[24] 郝彬彬,井元伟, 张嗣瀛. 加权无标度网络中连接密度与同步能力的关系[J]. 系统工程学报, 2010, 25(3):6-11.

Hao Binbin, Jing Yuanwei, Zhang Siying. Relations between link density and synchronizability in weighted scale-free networks [J]. Journal of Systems Engineering, 2010, 25(3):6-11.

[25] 孙宗海, 李德裕. 无标度网络同步过程研究[J]. 计算机与数字工程, 2013, 41(7):1137-1138.

Sun Zonghai, Li Deyu. Synchronization process in scale-free networks [J]. Computer Digital Engineering, 2013, 41(7):1137-1138.

[26] Fan J, Wang X F. Synchronization in scale-free dynamical networks [J]. Physica A Statistical Mechanics & Its Applications, 2001, 349(3):443-451.

[27] Li Z K, Duan Z S, Chen G R, et al. Consensus of multi-agent systems and synchronization of complex networks: a unified viewpoint [J]. IEEE Transactions on Circuits & Systems Part I Regular Papers, 2010, 57(1):213-224.

[28] Bragagnolo M C, Rescu I C, Daafouz J, et al. Reset strategy for consensus in networks of clusters [J]. Automatica, 2016, 65(3):53-63.

[29] 宋海裕, 俞立, 胡鸿翔. 牵制控制下的多智能体系统群一致性[J]. 控制理论与应用, 2012, 29(6):765-772.

Song Haiyu, Yu Li, Hu Hongxiang. Group consensus in multi-agent systems via pinning control [J]. Control Theory & Applications, 2012, 29(6):765-772.