Convergence speed of consensus problems over undirected scale-free networks

doi:10.1088/1674-1056/19/12/120513

Abstract Scale-free networks and consensus behaviour among multiple agents have both attracted much attention. To investigate the consensus speed over scale-free networks is the major topic of the present work. A novel method is developed to construct scale-free networks due to their remarkable power-law degree distributions, while preserving the diversity of network topologies. The time cost or iterations for networks to reach a certain level of consensus is discussed, considering the influence from power-law parameters. They are both demonstrated to be reversed power-law functions of the algebraic connectivity, which is viewed as a measurement on convergence speed of the consensus behaviour. The attempts of tuning power-law parameters may speed up the consensus procedure, but it could also make the network less robust over time delay at the same time. Large scale of simulations are supportive to the conclusions.

Keywords: scale-free networks consensus power-law distribution

Received: 09 March 2010
Revised: 08 August 2010
Accepted manuscript online:

PACS:	02.40.Pc	(General topology)
	89.75.Hc	(Networks and genealogical trees)

Fund: Project supported by the National Natural Science Foundation for Distinguished Young Scholars of China (Grant No. 60925011).

Cite this article:

Sun Wei(孙巍) and Dou Li-Hua(窦丽华) Convergence speed of consensus problems over undirected scale-free networks 2010 Chin. Phys. B 19 120513

[1]	Barabasi A L and Albert R 1999 Science 286 509
[2]	Barabasi A L 2009 Science 325 412
[3]	Li L, Alderson D, Doyle J C and Willinger W 2005 Internet Mathematics 2 431
[4]	Wang Y and Zheng Z G 2009 Acta Phys. Sin. 58 4221 (in Chinese)
[5]	Pan Z F and Wang X F 2006 Acta Phys. Sin. 55 4058 (in Chinese)
[6]	Mitzenmacher M 2005 Internet Mathematics 2 525
[7]	Kumar R, Raghavan P, Rajagopalan S, Sivakumar D, Tomkins A and Upfal E 2000 Proceedings of the 41st Annual Symposium on Foundations of Computer Science Washington DC, USA, November 12–14, 2000 pp. 57–65
[8]	Dangalchev C 2004 Physica A 338 659
[9]	Han X P and Xie Y B 2007 Physica A 381 525
[10]	Wang W X, Wang B H, Hu B, Yan G and Ou Q 2005 Phys. Rev. Lett. 94 188702
[11]	Ree S 2006 Physica A 376 692
[12]	Ravi K, Prabhakar R, Sridhar R and Andrew T 1999 Computer Networks 31 1481
[13]	Liu X, Liu T Q, Wang H and Li X Y 2010 Chin. Phys. B 19 070204
[14]	Farkas I, Derenyi I, Jeong H, Neda Z, Oltvai Z N, Ravasz E, Schubert A, Barabasi A L and Vicsek T 2002 Physica A 314 25
[15]	Gallos L K, Argyrakis P, Bunde A, Cohen R and Havlin S 2004 Physica A 344 504
[16]	Fan J and Wang X F 2005 Physica A 349 443
[17]	Nicolau M and Schoenauer M 2009 Biosystems 98 137
[18]	Guo J L 2008 Acta Phys. Sin. 57 756 (in Chinese)
[19]	Romualdo P S and Alessandro V 2000 Phys. Rev. Lett. 86 3200
[20]	Guo Q, Liu J G, Wang B H and Zhou T 2008 Chin. Phys. Lett. 25 773
[21]	Yamir M and Alexei V 2003 Euro. Phys. J. B 31 265
[22]	Wu J J, Gao Z Y and Sun H J 2006 Phys. Rev. E 74 066111
[23]	Zhao L, Kwangho P and Lai Y C 2004 Phys. Rev. E 70 035101
[24]	Zhao L, Kwangho P, Lai Y C and Nong Y 2005 Phys. Rev. E 72 023104
[25]	Fan W and Yeung K H 2009 Proceedings of the 7th Asian Control Conference Hong Kong, China, August 27–29, 2009 pp. 1143–1146
[26]	Wang W X and Chen G R 2008 Phys. Rev. E 77 026101
[27]	Yang R, Wang W X, Lai Y C and Chen G R 2009 Phys. Rev. E 79 026112
[28]	Yang R, Huang L and Lai Y C 2009 Phys. Rev. E 79 046101
[29]	Kim D H and Adilson E M 2007 Phys. Rev. Lett. 98 248701
[30]	Fatihcan A, Turker B and Jurgen J 2006 Physica D 224 35
[31]	Alessandro M, Lai Y C and Adilson M 2003 Phys. Rev. E 68 017102
[32]	Olfati-Saber R and Murray R 2004 IEEE Trans. Automat. Control 49 1520
[33]	Xiao F and Wang L 2008 IEEE Trans. Automat. Control 53 1804
[34]	Wang H and Guo Y 2008 Proceedings of the 27th American Control Conference Seattle, USA, June 11–13, 2008 pp. 748–752
[35]	Zhang L P, Jiang H B and Bi Q S 2010 Chin. Phys. B 19 010507
[36]	Li R H, Chen W S and Li S 2010 Chin. Phys. B 19 010508
[37]	Xiao Y Z, Xu W, Li X C and Tang S F 2008 Chin. Phys. B 17 80
[38]	Cao Y, Li Y, Ren W and Chen Y 2008 Proceedings of the 47th IEEE Conference of Decision and Control Cancun, Mexicao, December 9–11, 2008 pp. 2920–2925
[39]	Chao H, Chen Y and Ren W 2007 Proceedings of the 46th IEEE Conference of Decision and Control New Orleans, USA, December 12–14, 2007 pp. 1441–1446
[40]	Ren W, Chao H, Bourgeous W, Sorensen N and Chen Y 2008 IEEE Trans. Control Systems Technology 16 745
[41]	Olfati-Saber R Fax J and Murray R 2007 Proceedings of the IEEE 95 215
[42]	Arenas A, Diaz-Guilera A, Kurths J, Moreno Y and Zhou C 2008 Phys. Rep. 469 93
[43]	Xiao L and Boyd S 2004 Systems and Control Letters 53 65
[44]	Jin Z and Murray R 2007 The 46th IEEE Conference of Decision and Control New Orleans, USA, December 12–14, 2007 pp. 4227–4232
[45]	Zhou J and Wang Q 2009 Automatica 45 1455
[46]	Patterson S, Bamieh B and El Abbadi A 2007 Proceedings of the 46th IEEE Conference of Decision and Control New Orleans, USA, December 12–14, 2007 pp. 4215–4220
[47]	Qi W, Xu X J and Wang Y H 2009 Chin. Phys. B 18 4217
[48]	Olshevsky A and Tsitsiklis J 2006 Proceedings of the 45th IEEE Conference of Decision and Control San Diego, USA, December 11–15, 2006 pp. 3387–3392
[49]	Olfati-Saber R 2005 Proceedings of the 24th American Control Conference Portland, USA, June 8–10, 2005 pp. 2371–2378
[50]	Miroslav Fiedler P 1973 Czech. Math. J. 23 298
[51]	Hatano Y and Mesbahi M 2005 IEEE Trans. Automat. Control 50 1867
[52]	Olfati-Saber R 2007 Proceedings of the 26th American Control Conference New York City, USA, July 11–13, 2007 pp. 4619–4624
[53]	AAron C, Cosma R S and Mark N 2009 SIAM Rev. 51 661

[1]	Fault-tolerant finite-time dynamical consensus of double-integrator multi-agent systems with partial agents subject to synchronous self-sensing function failure Zhi-Hai Wu(吴治海) and Lin-Bo Xie(谢林柏). Chin. Phys. B, 2022, 31(12): 128902.
[2]	Consensus problems on networks with free protocol Xiaodong Liu(柳晓东) and Lipo Mo(莫立坡). Chin. Phys. B, 2021, 30(7): 070701.
[3]	Finite density scaling laws of condensation phase transition in zero-range processes on scale-free networks Guifeng Su(苏桂锋), Xiaowen Li(李晓温), Xiaobing Zhang(张小兵), Yi Zhang(张一). Chin. Phys. B, 2020, 29(8): 088904.
[4]	Hybrid-triggered consensus for multi-agent systems with time-delays, uncertain switching topologies, and stochastic cyber-attacks Xia Chen(陈侠), Li-Yuan Yin(尹立远), Yong-Tai Liu(刘永泰), Hao Liu(刘皓). Chin. Phys. B, 2019, 28(9): 090701.
[5]	Group consensus of multi-agent systems subjected to cyber-attacks Hai-Yun Gao(高海云), Ai-Hua Hu(胡爱花), Wan-Qiang Shen(沈莞蔷), Zheng-Xian Jiang(江正仙). Chin. Phys. B, 2019, 28(6): 060501.
[6]	Successive lag cluster consensus on multi-agent systems via delay-dependent impulsive control Xiao-Fen Qiu(邱小芬), Yin-Xing Zhang(张银星), Ke-Zan Li(李科赞). Chin. Phys. B, 2019, 28(5): 050501.
[7]	Energy-optimal problem of multiple nonholonomic wheeled mobile robots via distributed event-triggered optimization algorithm Ying-Wen Zhang(张潆文), Jin-Huan Wang(王金环), Yong Xu(徐勇), De-Dong Yang(杨德东). Chin. Phys. B, 2019, 28(3): 030501.
[8]	H_∞ couple-group consensus of stochastic multi-agent systems with fixed and Markovian switching communication topologies Muyun Fang(方木云), Cancan Zhou(周灿灿), Xin Huang(黄鑫), Xiao Li(李晓), Jianping Zhou(周建平). Chin. Phys. B, 2019, 28(1): 010703.
[9]	Mean-square composite-rotating consensus of second-order systems with communication noises Li-po Mo(莫立坡), Shao-yan Guo(郭少岩), Yong-guang Yu(于永光). Chin. Phys. B, 2018, 27(7): 070504.
[10]	Leader-following consensus of discrete-time fractional-order multi-agent systems Erfan Shahamatkhah, Mohammad Tabatabaei. Chin. Phys. B, 2018, 27(1): 010701.
[11]	Tracking consensus for nonlinear heterogeneous multi-agent systems subject to unknown disturbances via sliding mode control Xiang Zhang(张翔), Jin-Huan Wang(王金环), De-Dong Yang(杨德东), Yong Xu(徐勇). Chin. Phys. B, 2017, 26(7): 070501.
[12]	Consensus of multiple autonomous underwater vehicles with double independent Markovian switching topologies and timevarying delays Zhe-Ping Yan(严浙平), Yi-Bo Liu(刘一博), Jia-Jia Zhou(周佳加), Wei Zhang(张伟), Lu Wang(王璐). Chin. Phys. B, 2017, 26(4): 040203.
[13]	Multiple-predators-based capture process on complex networks Rajput Ramiz Sharafat, Cunlai Pu(濮存来), Jie Li(李杰), Rongbin Chen(陈荣斌), Zhongqi Xu(许忠奇). Chin. Phys. B, 2017, 26(3): 038901.
[14]	Stochastic bounded consensus of second-order multi-agent systems in noisy environment Hong-Wei Ren(任红卫), Fei-Qi Deng(邓飞其). Chin. Phys. B, 2017, 26(10): 100506.
[15]	Asymptotic bounded consensus tracking of double-integratormulti-agent systems with bounded-jerk target based onsampled-data without velocity measurements Shuang-Shuang Wu(吴爽爽), Zhi-Hai Wu(吴治海), Li Peng(彭力), Lin-Bo Xie(谢林柏). Chin. Phys. B, 2017, 26(1): 018903.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Convergence speed of consensus problems over undirected scale-free networks

Cite this article:

Online attention