Enhancing the synchronizability of networks by rewiring based on tabu search and a local greedy algorithm

doi:10.1088/1674-1056/20/12/128901

中国物理B ›› 2011, Vol. 20 ›› Issue (12): 128901-128901.doi: 10.1088/1674-1056/20/12/128901

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇下一篇

Enhancing the synchronizability of networks by rewiring based on tabu search and a local greedy algorithm

杨翠丽, 鄧榤生

Department of Electronic Engineering, City University of Hong Kong, Hong Kong, China

收稿日期:2011-04-08 修回日期:2011-07-19 出版日期:2011-12-15 发布日期:2011-12-15
基金资助:
Project supported by the grant from City University of Hong Kong (Grant No. 7008105).

Enhancing the synchronizability of networks by rewiring based on tabu search and a local greedy algorithm

Yang Cui-Li(杨翠丽)^† and Tang Kit-Sang(鄧榤生)

Department of Electronic Engineering, City University of Hong Kong, Hong Kong, China

Received:2011-04-08 Revised:2011-07-19 Online:2011-12-15 Published:2011-12-15
Supported by:
Project supported by the grant from City University of Hong Kong (Grant No. 7008105).

摘要/Abstract

摘要： By considering the eigenratio of the Laplacian matrix as the synchronizability measure, this paper presents an efficient method to enhance the synchronizability of undirected and unweighted networks via rewiring. The rewiring method combines the use of tabu search and a local greedy algorithm so that an effective search of solutions can be achieved. As demonstrated in the simulation results, the performance of the proposed approach outperforms the existing methods for a large variety of initial networks, both in terms of speed and quality of solutions.

Abstract: By considering the eigenratio of the Laplacian matrix as the synchronizability measure, this paper presents an efficient method to enhance the synchronizability of undirected and unweighted networks via rewiring. The rewiring method combines the use of tabu search and a local greedy algorithm so that an effective search of solutions can be achieved. As demonstrated in the simulation results, the performance of the proposed approach outperforms the existing methods for a large variety of initial networks, both in terms of speed and quality of solutions.

Key words: synchronizability, network rewiring, tabu search, local greedy, complex networks

中图分类号: (Complex systems)

89.75.-k

05.45.Xt (Synchronization; coupled oscillators)

杨翠丽, 鄧榤生. Enhancing the synchronizability of networks by rewiring based on tabu search and a local greedy algorithm[J]. 中国物理B, 2011, 20(12): 128901-128901.

Yang Cui-Li(杨翠丽) and Tang Kit-Sang(鄧榤生) . Enhancing the synchronizability of networks by rewiring based on tabu search and a local greedy algorithm[J]. Chin. Phys. B, 2011, 20(12): 128901-128901.

参考文献 34

[1]	Pastor S R and Vespignani A 2001 Phys. Rev. Lett. 86 3200
[2]	Klemm K, Eguiluz V M, Toral R and Miguel M S 2003 Phys. Rev. E 67 026120
[3]	Trpevski D, Tang W K S and Kocarev L 2010 Phys. Rev. E bf 81 056102
[4]	Tse C K, Liu J, Lau F C M and He K 2010 J. Empir. Finance 17 2099
[5]	Saber R O and Murray R M 2004 IEEE Trans. Autom. Control 49 1520
[6]	Arenas A, Guilera A D, Kurths J, Moreno Y and Zhou C S 2008 it Phys. Rep. 469 93
[7]	Li Z Q, Duan Z S and Chen G R 2009 Chin. Phys. B 18 1674
[8]	Zou Y L and Chen G R 2009 Chin. Phys. B 18 3337
[9]	Tu L L 2011 Chin. Phys. B 20 030504
[10]	Milanese A, Sun J and Nishikawa T 2010 Phys. Rev. E 81 046112
[11]	Zhao M, Chen G R, Zhou T and Wang B H 2007 Front. Phys. bf 2 460
[12]	Jalili M, Rad A A and Hasler M 2008 Phys. Rev. E 78 016105
[13]	Jalili M and Rad A A 2009 Chaos 19 028101
[14]	Feng C F, Xu X J, Wu Z X and Wang Y H 2008 Chin. Phys. B bf 17 1951
[15]	Ma X J, Wang Y and Zheng Z G 2009 Acta Phys. Sin. 58 4426 (in Chinese)
[16]	Duan Z S, Wang W X, Liu C and Chen G R 2009 Chin. Phys. B bf 18 3122
[17]	Korniss G, Novotny M A, Guclu H, Toroczkai Z and Rikvold P A 2003 Science 299 677
[18]	Pecora L M and Carroll T L 1998 Phys. Rev. Lett. 80 2109
[19]	Chavez M, Hwang D U, Amann A, Hentschel H G E and Boccaletti B 2005 Phys. Rev. Lett. 94 218701
[20]	Wang X, Lai Y C and Lai C H 2007 Phys. Rev. E 75 056205
[21]	Donetti L, Hurtado P I and Munoz M A 2005 Phys. Rev. E bf 95 188701
[22]	Donetti L, Neri F and Munoz M A 2006 J. Stat. Mech.: Theor. Exp. 8 P08007
[23]	Donetti L, Hurtado P I and Munoz M A 2008 J. Phys. A: Math. Theor. 41 224008
[24]	Rad A A, Jalili M and Haslerc M 2008 Chaos 18 037104
[25]	Hagberg A and Schult D A 2008 Chaos 18 037105
[26]	Wang L F, Wang Q L, Kong Z and Jing Y W 2010 Chin. Phys. B 19 080207
[27]	Wang B, Zhou T, Xiu Z L and Kim B J 2007 Phys. J. B 60 89
[28]	Mishkovski I, Righero M, Biey M and Kocarev L 2010 it Proceedings of 2010 IEEE International Symposium on Circuits and Systems Paris, May, p. 681
[29]	Watanabe T and Masuda N 2010 Phys. Rev. E 82 046102
[30]	Lu W 2007 Chaos 17 023122
[31]	Barabsi A L and Albert R 1999 Science 286 509
[32]	Watts D and Strogatz S 1998 Nature 393 440
[34]	Holme P and Kim B J 2002 Phys. Rev. E 65 026107

Enhancing the synchronizability of networks by rewiring based on tabu search and a local greedy algorithm

Enhancing the synchronizability of networks by rewiring based on tabu search and a local greedy algorithm

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 34

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Zonglin Li(李宗霖), Qiang Tian(田强), and Haiyan Hu(胡海岩). Resistance law of a rod penetrating a multilayer granular raft[J]. 中国物理B, 2023, 32(3): 34501-034501.
[2]	Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Analysis of cut vertex in the control of complex networks[J]. 中国物理B, 2023, 32(2): 28902-028902.
[3]	Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding[J]. 中国物理B, 2023, 32(1): 18903-018903.
[4]	Zhi-Hai Wu(吴治海) and Lin-Bo Xie(谢林柏). Fault-tolerant finite-time dynamical consensus of double-integrator multi-agent systems with partial agents subject to synchronous self-sensing function failure[J]. 中国物理B, 2022, 31(12): 128902-128902.
[5]	Pengli Lu(卢鹏丽), Yuntian Chen(陈云天), Teng Zhang(张腾), and Yonggang Liao(廖永刚). Biased random walk with restart for essential proteins prediction[J]. 中国物理B, 2022, 31(11): 118901-118901.
[6]	Chaoyi Shi(史朝义), Qi Zhang(张琦), and Tianguang Chu(楚天广). Effect of observation time on source identification of diffusion in complex networks[J]. 中国物理B, 2022, 31(7): 70203-070203.
[7]	Xiao-Xia Yang(杨晓霞), Hai-Long Jiang(蒋海龙), Yuan-Lei Kang(康元磊), Yi Yang(杨毅), Yong-Xing Li(李永行), and Chang Yu(蔚畅). Passenger management strategy and evacuation in subway station under Covid-19[J]. 中国物理B, 2022, 31(7): 78901-078901.
[8]	Dan-Dan Hu(胡淡淡), Xue-Jin Fang(方学进), and Xiao-Pu Han(韩筱璞). Advantage of populous countries in the trends of innovation efficiency[J]. 中国物理B, 2022, 31(6): 68903-068903.
[9]	Xian-Li Sun(孙先莉), You-Guo Wang(王友国), and Lin-Qing Cang(仓林青). Correlation and trust mechanism-based rumor propagation model in complex social networks[J]. 中国物理B, 2022, 31(5): 50202-050202.
[10]	Xiang Ling(凌翔), Bo Hua(华博), Ning Guo(郭宁), Kong-Jin Zhu(朱孔金), Jia-Jia Chen(陈佳佳), Chao-Yun Wu(吴超云), and Qing-Yi Hao(郝庆一). Synchronization in multilayer networks through different coupling mechanisms[J]. 中国物理B, 2022, 31(4): 48901-048901.
[11]	Alireza Bahramian, Sajjad Shaukat Jamal, Fatemeh Parastesh, Kartikeyan Rajagopal, and Sajad Jafari. Collective behavior of cortico-thalamic circuits: Logic gates as the thalamus and a dynamical neuronal network as the cortex[J]. 中国物理B, 2022, 31(2): 28901-028901.
[12]	Atiyeh Bayani, Sajad Jafari, and Hamed Azarnoush. Explosive synchronization: From synthetic to real-world networks[J]. 中国物理B, 2022, 31(2): 20504-020504.
[13]	Dong-Jie Qian(钱冬杰). Explosive synchronization in a mobile network in the presence of a positive feedback mechanism[J]. 中国物理B, 2022, 31(1): 10503-010503.
[14]	Yu-Wei Yan(严玉为), Yuan Jiang(蒋沅), Rong-Bin Yu(余荣斌), Song-Qing Yang(杨松青), and Cheng Hong(洪成). Cascading failures of overload behaviors using a new coupled network model between edges[J]. 中国物理B, 2022, 31(1): 18901-018901.
[15]	Xu Li(李旭), Tingting Xue(薛婷婷), Yu Sun(孙宇), Jingfang Fan(樊京芳), Hui Li(李辉), Maoxin Liu(刘卯鑫), Zhangang Han(韩战钢), Zengru Di(狄增如), and Xiaosong Chen(陈晓松). Discontinuous and continuous transitions of collective behaviors in living systems[J]. 中国物理B, 2021, 30(12): 128703-128703.