文章快速检索 高级检索

Synchronization in complex 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
Abstract: For the tremendous amount of nodes in complex networks, no one can control all the vertices. Only by controlling minor 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 algorithm to achieve it and 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.
Key words: complex network     coupling     pinning control     spanning tree     synchronization

1 网络模型 1.1 模型示例

 图 1 网络示例 Fig. 1 A network example
 图 2 失效的传播 Fig. 2 A propagation of the failure

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

 图 4 全球排名前1 000网站的度分布及幂律分布[10] Fig. 4 Degree and power-law distribution of the 1 000 most-visited sites on the web[10]

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

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

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

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

1.2 复杂网络的牵制模型[13]

 $\dot x\left( t \right) = f\left( {t,x\left( t \right),u\left( t \right)} \right),x\left( t \right) \in {R^N}$ (1)

 \eqalign{ {{\dot x}_i}\left( t \right) = f\left( {{x_i}\left( t \right),t} \right) & + c\sum\limits_{j = 1,j \ne i}^N {{G_{ij}}\Gamma \left( {{x_j}\left( t \right) - {x_i}\left( t \right)} \right)} \cr i = 1,2, \cdots ,N \cr} (2)

 ${G_{ii}} = - \sum\limits_{j = 1,j \ne i}^N {{G_{ij}}}$ (3)

 $\sum\limits_{j = 1}^N {{G_{ij}}} = 0$ (4)

 ${\dot x_i}\left( t \right) = f\left( {{x_i}\left( t \right),t} \right) + c\sum\limits_{j = 1}^N {{G_{ij}}\Gamma {x_j}\left( t \right)} ,i = 1,2, \ldots ,N$

 $\dot s = f\left( {s,t} \right),s\left( {{t_0}} \right) = {s_0}$ (5)

 \eqalign{ & {{\dot x}_i}\left( t \right) = f\left( {{x_{qi}}\left( t \right),t} \right) + c\sum\limits_{j = 1}^N {{G_{qi,j}}\Gamma {x_j}\left( t \right)} + {u_{qi}} \cr & i = 1,2, \cdots ,l \cr} (6)
 \eqalign{ & {{\dot x}_i}\left( t \right) = f\left( {{x_{qi}}\left( t \right),t} \right) + c\sum\limits_{j = 1}^N {{G_{qi,j}}\Gamma {x_j}\left( t \right)} \cr & i = l + 1,l + 2, \cdots ,N \cr} (7)

 $\mathop {\lim }\limits_{t \to \infty } \left\| {{x_i}\left( t \right) - s\left( t \right)} \right\| = 0,i = 1,2, \cdots ,N$ (8)

1.2.1 一般复杂网络的同步化

 ${e_i}\left( t \right) = {x_i}\left( t \right) - s\left( t \right),i = 1,2, \cdots ,N$ (9)

i=1,2，…，l，如式(10)、(11) 所示。

 \eqalign{ & {{\dot e}_i}\left( t \right) = f\left( {{x_i}\left( t \right),t} \right) - f\left( {s\left( t \right),t} \right) + \cr & c\sum\limits_{j = 1}^N {{G_{ij}}\Gamma {e_j}\left( t \right) - c{d_i}\Gamma {e_i}\left( t \right)} \cr} (10)
 \eqalign{ & {{\dot e}_i}\left( t \right) = f\left( {{x_i}\left( t \right),t} \right) - f\left( {s\left( t \right),t} \right) + c\sum\limits_{j = 1}^N {{G_{ij}}\Gamma {e_j}\left( t \right)} \cr & i = l + 1,l + 2, \cdots ,N \cr} (11)

 $V\left( t \right) = \frac{1}{2}\sum\limits_{i = 1}^N {e_i^T{\xi _i}{e_i}\left( t \right)}$

 \eqalign{ & \dot V = \sum\limits_{i = 1}^N {e_i^{\text{T}}\left( t \right){\xi _i}} {{\dot e}_i}\left( t \right) = \cr & \sum\limits_{i = 1}^N {e_i^T\left( t \right){\xi _i}} \left[ {f\left( {{x_i}\left( t \right),t} \right) - f\left( {s\left( t \right),t} \right) + c\sum\limits_{j = 1}^N {{G_{ij}}\Gamma {e_j}\left( t \right)} } \right] - \cr & c\sum\limits_{i = 1}^l {{d_i}{\xi _i}e_{_i}^{\text{T}}\left( t \right)\Gamma {e_i}\left( t \right)} \leqslant \cr & \sum\limits_{i = 1}^N {e_i^{\text{T}}\left( t \right){\xi _i}} \left[ {K\Gamma {e_i}\left( t \right) + c\sum\limits_{j = 1}^N {{G_{ij}}\Gamma {e_j}\left( t \right)} } \right] - \cr & c\sum\limits_{i = 1}^l {{d_i}{\xi _i}e_{_i}^{\text{T}}\left( t \right)\Gamma {e_i}\left( t \right)} = \cr & {e^{\text{T}}}\left( t \right)\left[ {\Xi \otimes \left( {KT} \right) + c\left( {\hat G - \Xi D} \right) \otimes \Gamma } \right]e\left( t \right) \cr} (12)

 \begin{align} & e\left( t \right)=\left[ e_{1}^{\text{T}}\left( t \right)e_{2}^{\text{T}}\left( t \right)\cdots e_{N}^{\text{T}}\left( t \right) \right] \\ & \Xi =\text{diag}\left( {{\xi }_{1}},{{\xi }_{2}},\cdots ,{{\xi }_{N}} \right) \\ & D=\text{diag}\left( {{d}_{1}},\cdots {{d}_{l}},0,\cdots ,0 \right) \\ \end{align}

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

 $G = \left( {\Xi G + {G^{\text{T}}}\Xi } \right)/2$

θ=λmax(K+KT)/2 ，由于θK的可互换性得：

 \eqalign{ & {\left( {x - y} \right)^{\text{T}}}\left( {f\left( {x,t} \right) - f\left( {y,t} \right)} \right) \leqslant \cr & \theta {\left( {x - y} \right)^{\text{T}}}\Gamma \left( {x - y} \right)\forall x,y \in {R^n} \cr}

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

 $C = \theta \Xi + c\left( {\hat G - \Xi D} \right) < 0$ (13)

${C_{ij}} = \theta {\xi _i} - e{\xi _i}k_l^{in} - c{\xi _i}{d_i},\left( {1 \leqslant i \leqslant l} \right)$

${C_{ij}} = \theta {\xi _i} - e{\xi _i}k_l^{in},\left( {l + 1 \leqslant i \leqslant N} \right)$

 ${d_i} > \frac{\theta }{c} - k_i^{in},1 \leqslant i \leqslant l$ (14)
 $k_i^{in} > \frac{\theta }{c},l + 1 \leqslant i \leqslant N$ (15)
 $c > \frac{{{\lambda _{\max }}\left( {\theta \Xi } \right)}}{{\left| {{\lambda _{\max }}\left( {G - \Xi D} \right)} \right|}}$ (16)

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

 \eqalign{ & {{\dot y}_i}\left( t \right) = f\left( {{y_i}\left( t \right),t} \right) + c\sum\limits_{j = 1}^N {{{\tilde G}_{ij}}\Gamma {y_j}\left( t \right)} \cr & i = 1,l + 1,2, \cdots ,N + 1 \cr} (17)

 $\theta {\tilde \pi _j} + c\left( {{{\bar A}_j} - {{\tilde \pi }_j}{C_j}{{\bar D}_j}} \right) < 0,j = 2,3, \cdots ,m$

1.3 算法及系统运行界面

1) 系统初始化，设j=2，转到2)；

2) 根据式(17) 计算${\bar D_j}$，如果${\bar D_j}$=0，则网络无需控制便可同步，转到6)，否则转到3)；

3) 如果节点来自外部的入度为零，比如Cj=0，根据式(17)，节点必须通过${\bar D_j}$进行控制，转到4)，否则转到6)；

4) 对于通过j链路连接的i节点，根据式(15)，如果入度$k_{{r_{j - 1}} + i}^{in} \leqslant \theta /c$，则节点必须被控制，转到5)，否则转到6)

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

6) 如果j<m，则j=j+1，转到2)，否则终止。

 图 5 运行界面 Fig. 5 Running interface
2 实验结果及分析

 ${\bar A_3} = \left[ {\begin{array}{*{20}{c}} { - 24}&3&9&{12}\\ 3&{ - 6}&3&0\\ 9&3&{ - 24}&{12}\\ {12}&0&{12}&{ - 24} \end{array}} \right]$

 $\left[ {\begin{array}{*{20}{c}} { - 24 + 8\frac{\theta }{c}}&3&9&{12}\\ 3&{ - 6 + \frac{\theta }{c}}&3&0\\ 9&3&{ - 24 + 3\frac{\theta }{c}}&{12}\\ {12}&0&{12}&{ - 24 + 4\frac{\theta }{c}} \end{array}} \right] - {\tilde \pi _3}{\bar D_3} < 0$

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

 图 7 驱动节点比例与其入度的关系 Fig. 7 Relation between δ and in-degree
3 结束语

 [1] WATTS D J, STROGATZ S H. Collective dynamics of small-world networks[J]. Nature,1998, 393 (6684) : 440 –442. [2] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science,1999, 286 (5439) : 509 –512. [3] LIU Y Y, SLOTINE J J, BARABáS A L. Controllability of complex networks[J]. Nature,2011, 473 : 167 –173. [4] WANG W X, NI X, LAI Y C. Optimizing 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 complex 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. Oxford: Oxford University Press[M]. 2010 : 1 -20. [8] CHEN G R, WANG X F, LI X. Introduction to complex networks: models, structures and dynamics. Beijing: High Education Press[M]. 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, MESBAHI M. Dynamics and control of state-dependent networks for probing genomic organization[J]. PNAS,2011, 108 : 257 –262. [12] 汪小帆, 李翔, 陈关荣. 网络科学导论. 北京: 高等教育出版社[M]. 2012 : 1 -15. WANG Xiaofan, LI Xiang, CHEN Guanrong. Introduction of network science. Beijing: Higher Education Press[M]. 2012 : 1 -15. [13] CHEN G R, WANG X F, LI X. Introduction to complex networks: models, structures and dynamics. Beijing: High Education Press[M]. 2012 : 167 -256. [14] YU W, CAO J, LIU J. Global synchronization of linearly hybrid coupled networks with time-varying delay[J]. SIAM J Appl Dyn Syst,2008 (7) : 108 –133. [15] 柳亭, 楮衍东, 张建刚, 等. 复杂动态网络的牵制同步控制[J]. 燕山大学学报,2010, 34 (5) : 459 –470. LIU Ting, CHU Yandong, ZHANG Jiangang, et al. Pinning controlled synchronization of a complex dynamical network[J]. Journal of Yanshan University,2010, 34 (5) : 459 –470.
DOI: 10.3969/j.issn.1673-4785.201311014

0

#### 文章信息

QIU Jianping, CHEN Lichao, PAN Lihu

Synchronization in complex networks via pinning control

CAAI Transactions on Intelligent Systems, 2014, 9(6): 734-739
http://dx.doi.org/10.3969/j.issn.1673-4785.201311014