Convergence speed of consensus problems over undirected scale-free networks

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

中国物理B ›› 2010, Vol. 19 ›› Issue (12): 120513-120513.doi: 10.1088/1674-1056/19/12/120513

Convergence speed of consensus problems over undirected scale-free networks

孙巍, 窦丽华

School of Automation, Beijing Institute of Technology, Beijing 100081, China

收稿日期:2010-03-09 修回日期:2010-08-08 出版日期:2010-12-15 发布日期:2010-12-15
基金资助:
Project supported by the National Natural Science Foundation for Distinguished Young Scholars of China (Grant No. 60925011).

Convergence speed of consensus problems over undirected scale-free networks

Sun Wei(孙巍)^†ger and Dou Li-Hua(窦丽华)

School of Automation, Beijing Institute of Technology, Beijing 100081, China

Received:2010-03-09 Revised:2010-08-08 Online:2010-12-15 Published:2010-12-15
Supported by:
Project supported by the National Natural Science Foundation for Distinguished Young Scholars of China (Grant No. 60925011).

摘要/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.

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.

Key words: scale-free networks, consensus, power-law distribution

中图分类号: (General topology)

02.40.Pc

89.75.Hc (Networks and genealogical trees)

孙巍, 窦丽华. Convergence speed of consensus problems over undirected scale-free networks[J]. 中国物理B, 2010, 19(12): 120513-120513.

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

参考文献 53

[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

Convergence speed of consensus problems over undirected scale-free networks

Convergence speed of consensus problems over undirected scale-free networks

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 53

相关文章 13

Metrics

本文评价

推荐阅读 0

[1]	Shao-Yong Huo(霍绍勇), Long-Chao Yao(姚龙超), Kuan-Hong Hsieh(谢冠宏), Chun-Ming Fu(符纯明), Shih-Chia Chiu(邱士嘉), Xiao-Chao Gong(龚小超), and Jian Deng(邓健). Tunable topological interface states and resonance states of surface waves based on the shape memory alloy[J]. 中国物理B, 2023, 32(3): 34303-034303.
[2]	Hong-Yong Mao(毛鸿勇), Fu-Jia Chen(陈福家), Kai Guo(郭凯), and Zhong-Yi Guo(郭忠义). Broadband topological valley-projected edge-states transport in composite structure phononic crystal[J]. 中国物理B, 2021, 30(8): 84302-084302.
[3]	吴召艳, 弓晓利. Identifying the interactions in a colored dynamical network[J]. 中国物理B, 2015, 24(11): 110202-110202.
[4]	赵力, 杨捷, 谢群英, 田苗. Topological aspect of vortex lines in two-dimensional Gross–Pitaevskii theory[J]. 中国物理B, 2012, 21(9): 90304-090304.
[5]	赵力, 杨捷, 谢群英, 田苗, 段一士. Vortex lines in a ferromagnetic spin-triplet superconductor[J]. 中国物理B, 2012, 21(5): 57401-057401.
[6]	樊庆菊. Topological horseshoe in nonlinear Bloch system[J]. 中国物理B, 2010, 19(12): 120508-120508.
[7]	李莹, 刘曾荣. Synchronization between different motifs[J]. 中国物理B, 2010, 19(11): 110501-110507.
[8]	任继荣, 戎树军, 朱涛. A novel approach to topological defects in a vector order parameter system[J]. 中国物理B, 2009, 18(7): 2901-2904.
[9]	任继荣, 墨淑凡, 朱涛. Knot solitons in AFZ model[J]. 中国物理B, 2009, 18(5): 1814-1820.
[10]	孟庆芳, 彭玉华, 薛佩军. A new method of determining the optimal embedding dimension based on nonlinear prediction[J]. 中国物理B, 2007, 16(5): 1252-1257.
[11]	李德权. Hybrid TS fuzzy modelling and simulation for chaotic Lorenz system[J]. 中国物理B, 2006, 15(11): 2541-2548.
[12]	李思昊, 王宏利, 欧阳颀. Frequency sensitivity of sub-excitable systems coupled with different topology[J]. 中国物理B, 2004, 13(4): 448-453.
[13]	杨国宏, 张慧, 段一士. Topological quantization of disclination points in three-dimensional liquid crystals[J]. 中国物理B, 2002, 11(5): 415-418.