牵制控制下复杂网络的同步性研究

仇建平，陈立潮，潘理虎（太原科技大学计算机科学与技术学院，山西太原030024）

牵制控制下复杂网络的同步性研究

仇建平，陈立潮，潘理虎
（太原科技大学计算机科学与技术学院，山西太原030024）

复杂网络是由数量巨大的节点组成，任何人都无法控制所有节点.只有通过控制少数节点，对复杂网络进行牵制控制，才能达到网络同步的目的.为此分析了一般网络和含有生成树的网络同步的条件，给出了实现算法及运行界面.仿真结果表明，随着网络规模的扩大，驱动节点的比例减小，驱动节点常常都是入度低的节点.

复杂网络；耦合；牵制；生成树；同步

社会系统本质上是一个复杂系统，特别是随着现代社会的飞速发展，对资源的需求也越来越大。单项资源已无法支撑整个社会的全面发展，且只有各单项资源互相耦合、互相牵制，才能形成强大的支撑合力。一旦某种或几种资源缺失或失效，社会系统的内在结构及功能会遭到极大的破坏。例如，2003年9月28日发生在意大利的大面积停电事件，最初由于一个供电站的失效致使众多供电站与整个供电网的脱离，随后又致使众多Internet网络节点失效，最终致使整个电力调度系统无法调控，导致了更大规模的停电［1⁃2］。

随着通信网、电力网、交通网、供水网等复杂动态网络的发展，以及大型高速计算机、巨型数据库以及GPS和基于大数据的社会计算的普及，复杂动态网络特别是多节点不规则连接的有向网络的牵制控制越来越受到关注。如刘彧［3］研究了复杂动态网络节点从任意初态控制到任意终态的完全能控性问题；王文旭［4］提出了一种减少控制节点的方法；Ne⁃pusz［5］研究了运用点边互换的思想对网络的边的状态进行控制的问题；严钢［6］研究了控制复杂网络的能量代价问题。

1 网络模型

1.1 模型示例

一个复杂动态网络是具有相互耦合和牵制关系的点或网络所组成的网络系统。一般用被线连接起来的点来代表网络。这些点被称为节点，是网络的参与者；线则被称为链路，代表参与者之间的联系。

如图1所示，电网互相传输电力，通信网之间互相传输数据，交通网之间互相运输，供水网之间互相供水，同时电网进行电力传输需要通信网进行控制，通信网之间互相通讯又依赖于电网的供电等。如果这些网络中的一个节点受到攻击而失效，这些牵制关系能使故障在网络之间传播。如图2所示，一个节点受到攻击后，最初有12个运行节点的网络最后只剩下4个有效节点。

图1 网络示例Fig.1 A network exam ple

图2 失效的传播Fig.2 A propagation of the failure

近年来，许多实证研究证明，社会系统中的许多网络，都满足幂律分布［7－9］，即少数主导节点具有非常大的连接数，大多数节点的连接数甚小，以互联网为例，如图3所示。

图3 全球排名前1 000网站Fig.3 The 1 000 most⁃visited sites on the web

图3 勾勒了全球排名前1 000的网站，这个网络一共有1 000个网站和2万条有向链接，全球的网站分成了两大阵营。左边这一块的核心是google、youtube、facebook等，右边的核心是百度、优酷、人人网等。

如图4所示，这1 000个网站度分布是个长尾分布，但有一个明显的截断。这是因为只考虑了排名靠前的网站，这个排名范围以外的网站数据是极度不全的。从分布来看，是一个类幂律分布，斜率大概是0.8，而Barabasi等［2］估计的互联网链接幂律分布指数是2.1。这有2种原因：1）近年来互联网变得更不平等；2）只监测了重大流量的链接结构，相当于互联网里的rich club，也就是说网络中的链接是更不平等的。

图4 全球排名前1 000网站的度分布及幂律分布［10］Fig.4 Degree and pow er⁃law distribution of the 1 000 most⁃visited sites on the web［10］

基于这些实证，牵制控制［11］的本质通过复杂网络中的少数节点影响网络中的其他节点，从而实现整个网络的同步，所需解决的问题包括：

1）可行性问题：当网络规模很大时，控制理论中已有的判据和算法的计算复杂度往往难以承受，因此需要寻找新的有效算法；

2）经济性问题：选取受控节点代价的最小化；

3）鲁棒性问题：大规模复杂网络往往面临由于随机故障或者有意攻击而导致的节点或链路失效。因此，有必要研究控制系统对于随机故障和有意攻击的鲁棒性。特别地，需要能够给出判别大规模网络控制系统中的关键节点和链路的有效算法；

4）演化性问题：很多实际网络的结构和参数往往是随时间演化的，这给系统的有效分析与控制带来新问题，需要有适合演化网络的判断依据与有效算法。

面对这些问题，很重要的一点就是对网络进行牵制［12］，使得其网络的最终状态满足一定要求。但对于大规模的网络，不可能控制其每个节点，仅能对网络中的少数关键节点进行控制，通过节点间的相互耦合，从而达到控制整个网络的目的。

1.2 复杂网络的牵制模型［13］

给定时间t和状态空间中的一点x（t），复杂网络动态变化过程可表示为

式中：输入u（t），t时刻的状态与输出惟一确定。

考虑一个由N个节点构成的连续动力系统，其中第i个状态节点的线性耦合常微分方程［14］如式（2）所示。

式中：N＞1为网络节点个数；xi（t）＝[xi1（t）xi2（t）…xin（t）]T∈Rn表示i节点的状态向量；常数c＞0表示耦合强度；Γ∈Rn×n表示外部耦合矩阵，由于f的线形性，Γ为正定；G＝（Gij）N×N表示网络的拓扑结构，其中若存在节点j到节点i（i≠j）的连接，则Gij＞0，若存在节点i到节点j（j≠i）的连接，则Gji＞0，否则Gij＝0。G对角元素定义为式（3）。

从而满足了耗散耦合条件，如式（4）所示。

此时，式（2）可简化为

设不动点s是系统的解，如式（5）所示。

式中：s（t）可以是一个平衡点、周期轨、拟周期轨、混沌轨道，或者是多agent动态网络的虚拟领袖。假设在网络中仅前面l个节点（q1，q2，…，ql）为驱动节点，网络能被描述为式（6）、（7）。

式中：l＝⌊δN」，0＜δ＜1，其中dqi＞0为反馈控制增益，uqi是n维线性反馈控制器。

牵制控制的目标是发现一些合适的uqi以使网络能够达到某个同步状态，其中同步可表示为式（8）。

1.2.1 一般复杂网络的同步化

为了获得式（10）、（11）的收敛条件，选择Lya⁃punov函数为

设存在K使得（x－y）T（f（x，t）－f（y，t））≤（x－y）TKΓ（x－y）∀x，y∈Rn［15］成立，即满足Lip⁃schitz条件。根据式（8）求导得

当D＝0，表明来自外部的入度很高，无需控制便能达到同步，⊗为kronecker积，

设θ＝λmax（K＋KT）／2，由于θ与K的可互换性得：

若V≤0，误差逐渐趋向于零，则网络同步，可得式（16）。

1.2.2 包含生成树的复杂网络的同步化

随着移动技术与社会化媒体的迅速发展，人们越来越多地参与到网络上丰富的社会活动中。人们在享受前所未有的便捷的同时，也拥有了网络这一公共话语平台，但同时个性会自觉的消失而群体的共性便随之显现出来，形成所谓的“网民群体”。网民群体常常表现为非常烦躁、多变和冲动，将选择、判断和处理的权利交给群体领袖。群体领袖对事件的倾向性解读，在暗示和相互传染的推波助澜下，立刻会被网民接受。

给合式（6）～（8），将群体领袖作为生成树的根节点，可得式（17）。

1.3 算法及系统运行界面

牵制控制算法具体步骤如下：

2）根据式（17）计算，如果j＝0，则网络无需控制便可同步，转到6），否则转到3）；

3）如果节点来自外部的入度为零，比如Cj＝0，

－根据式（17），节点必须通过Dj进行控制，转到4），否则转到6）；

4）对于通过j链路连接的i节点，根据式（15），如果入度kirnj－1＋i≤θ／c，则节点必须被控制，转到5），否则转到6）

5）筛选根节点，转到6）

6）如果j＜m，则j＝j＋1，转到2），否则终止。

系统运行界面如图5所示。

图5 运行界面Fig.5 Running interface

2 实验结果及分析

包含10个节点的网络拓扑如图5所示，可分解为5个部分，其中s为群体领袖，实心圆点为被驱动节点，用于牵制其余部分，空心圆点通过节点间的耦合连接关系被间接地控制。2，1），c＝12，N＝10，θ＝31。子网2和3子网的外部入度均为0，必须加以控制。

对于子网2，C2＝A－2＝0，根据式（17）如果d1＞≈2.583 3，子网2能同步；

对于子网3，C3＝0，＝diag（8，1，3，4）

根据式（17）如果d2＜18.266 7，控制子网3中的节点2，子网3能同步；

对于子网5，C5＝diag（2，0，3），＝diag（2，3，

2.665 ，控制子网5中的节点9，子网5能同步。

综上所述，实心节点1，2，9的d1＞2.583 3，d2＞18.266 7，d9＞2.665，图中的网络可同步。如图6所示，随着网络规模的扩大，驱动节点的比例减小，即越是稀疏的网络需要越多比例的驱动节点才能实现完全能控。

图6 驱动节点比例与网络规模N的关系Fig.6 Relation betweenδand N

如图7所示，分别以ER网络和Scale⁃free网络为例，驱动节点常常都是入度低的节点，这与式（14）、（15）一致，也与现实情况一致，即入度低的网络控制起来比较困难，入度高的网络可通过驱动少数节点来加以控制。

图7 驱动节点比例与其入度的关系Fig.7 Relation betweenδand in⁃degree

3 结束语

本文针对一般复杂网络和包含生成树的复杂网络的优化牵制控制，给出了此2种情况下复杂网络同步的条件，最后通过系统仿真，发现越是稀疏的网络需要越多比例的驱动节点才能实现完全能控，且入度低的节点应首先加以控制。

［1］WATTS D J，STROGATZ S H.Collective dynamics of small⁃world networks［J］.Nature，1998，393（6684）：440⁃442.

［2］BARABASIA L，ALBERT R.Emergence of scaling in ran⁃dom networks［J］.Science，1999，286（5439）：509⁃512.

［3］LIU Y Y，SLOTINE J J，BARABáSA L.Controllability of complex networks［J］.Nature，2011，473：167⁃173.

［4］WANGW X，NIX，LAIY C.Optim izing controllability of complex networks by minimum structural perturbations［J］.Phys Rev E，2012，85（026115）：1⁃5.

［5］NEPUSZ T，VICSEK T.Controlling edge dynamics in com⁃plex networks［J］.Nature Physics，2012（8）：568⁃573.

［6］YAN G，REN J，LAI Y C.Controlling complex networks：how much energy is needed？［J］.Phys Rev Lett，2012，108（218703）：1⁃9.

［7］NEWMAN M E J.Networks：an introduction［M］.Oxford：Oxford University Press，2010：1⁃20.

［8］CHEN G R，WANG X F，LI X.Introduction to complex networks：models，structures and dynam ics［M］.Beijing：High Education Press，2012：1⁃10.

［9］ZHOU T，WANG B H.Catastrophes in scale⁃free networks［J］.Chin Phys Lett，2005，22：1072⁃1075.

［10］Google.The 1000 most⁃visited sites on the web［EB／OL］.USA：Google（2011⁃07⁃19）［2012⁃10⁃25］.http：／／www.google.com／adplanner／static／top1000.

［11］RAJAPAKSE I，GROUDINE M，MESBAHIM.Dynamics and control of state⁃dependent networks for probing genom⁃ic organization［J］.PNAS，2011，108：257⁃262.

［12］汪小帆，李翔，陈关荣.网络科学导论［M］.北京：高等教育出版社，2012：1⁃15.WANG Xiaofan，LIXiang，CHEN Guanrong.Introduction of network science［M］.Beijing：Higher Education Press，2012：1⁃15.

［13］CHEN G R，WANG X F，LI X.Introduction to complex networks：models，structures and dynamics［M］.Beijing：High Education Press，2012：167⁃256.

［14］YUW，CAO J，LIU J.Global synchronization of linearly hybrid coup led networkswith time⁃varying delay［J］.SIAM JAppl Dyn Syst，2008（7）：108⁃133.

［15］柳亭，楮衍东，张建刚，等.复杂动态网络的牵制同步控制［J］.燕山大学学报，2010，34（5）：459⁃470.LIU Ting，CHU Yandong，ZHANG Jiangang，et al.Pin⁃ning controlled synchronization of a complex dynamical net⁃work［J］.Journal of Yanshan University，2010，34（5）：459⁃470.

仇建平，男，1973年生，讲师，主要研究方向为复杂网络、人工智能，承担山西省回国留学人员科研资助项目、山西省自然科学基金、山西省重大科技专项基金等项目多项。发表学术论文9篇，其中5篇被EI检索。

陈立潮，男，1961年生，教授，主要研究方向为人工智能，发表论文数十篇。

潘理虎，男，1974年生，副教授，博士，主要研究方向为煤矿安全、人工智能。

Synchronization in comp lex networks via pinning control

QIU Jianping，CHEN Lichao，PAN Lihu
（Institute of Computer Science and Technology，Taiyuan University of Science and Technology，Taiyuan 030024，China）

For the tremendous amount of nodes in complex networks，no one can control all the vertices.Only by controllingminor vertices and spinning the complex network can the synchronization of the network be achieved.The conditions for synchronization of common network and the network with spanning tree are analyzed.The algo⁃rithm to achieve itand the operation interface are given in this paper.The system simulation results showed that the percentage for the pinning controlled vertices becomes smaller as the network size becomes larger and the vertices with very small in⁃degrees should be pinned.

complex network；coupling；pinning control；spanning tree；synchronization

TP393.4

A

1673⁃4785（2014）06⁃0734⁃06

仇建平，陈立潮，潘理虎.牵制控制下复杂网络的同步性研究［J］.智能系统学报，2014，9（6）：734⁃739.

英文引用格式：QIU Jianping，CHEN Lichao，PAN Lihu.Synchronization in complex networks via pinning control［J］.CAAI Transactions on Intelligent Systems，2014，9（6）：734⁃739.

10.3969／j.issn.1673⁃4785.201311014

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1673⁃4785.201311014.htm l

2013⁃11⁃07.

日期：2014⁃09⁃30.

山西省回国留学人员科研基金资助项目（2013⁃097）.

仇建平.E⁃mail：920868329＠qq.com.