|
|
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 |
|
|
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.
|
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
|
No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|