Network evolution driven by dynamics applied to graph coloring

doi:10.1088/1674-1056/22/6/060507

中国物理B ›› 2013, Vol. 22 ›› Issue (6): 60507-060507.doi: 10.1088/1674-1056/22/6/060507

Network evolution driven by dynamics applied to graph coloring

吴建设^a, 李力光^a, 王晓华^b, 于昕^a, 焦李成^a

a Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, 224# Xidian University,2# Taibai South Road, Xi'an 710071, China;
b Aeronautical Computing Technique Research Institute, Xi'an 710068, China

收稿日期:2012-08-31 修回日期:2012-10-22 出版日期:2013-05-01 发布日期:2013-05-01
基金资助:
Project supported by the National Natural Science Foundation of China (Grants Nos. 61072139, 61072106, 61203303, 61003198, 61272279, and 61003199).

Network evolution driven by dynamics applied to graph coloring

Wu Jian-She (吴建设)^a, Li Li-Guang (李力光)^a, Wang Xiao-Hua (王晓华)^b, Yu Xin (于昕)^a, Jiao Li-Cheng (焦李成)^a

a Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, 224# Xidian University,2# Taibai South Road, Xi'an 710071, China;
b Aeronautical Computing Technique Research Institute, Xi'an 710068, China

Received:2012-08-31 Revised:2012-10-22 Online:2013-05-01 Published:2013-05-01
Contact: Wu Jian-She E-mail:jianshewu@126.com
Supported by:
Project supported by the National Natural Science Foundation of China (Grants Nos. 61072139, 61072106, 61203303, 61003198, 61272279, and 61003199).

摘要/Abstract

摘要： An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics coevolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a coevolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.

关键词: network dynamics, evolution of network, evolutionary strategies, graph coloring problem

Abstract: An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics coevolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a coevolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.

Key words: network dynamics, evolution of network, evolutionary strategies, graph coloring problem

中图分类号: (Nonlinear dynamics and chaos)

05.45.-a

02.10.Ox (Combinatorics; graph theory) 02.50.-r (Probability theory, stochastic processes, and statistics)

吴建设, 李力光, 王晓华, 于昕, 焦李成. Network evolution driven by dynamics applied to graph coloring[J]. 中国物理B, 2013, 22(6): 60507-060507.

Wu Jian-She (吴建设), Li Li-Guang (李力光), Wang Xiao-Hua (王晓华), Yu Xin (于昕), Jiao Li-Cheng (焦李成). Network evolution driven by dynamics applied to graph coloring[J]. Chin. Phys. B, 2013, 22(6): 60507-060507.

参考文献 45

[1]	Strogatz S H 2001 Nature 410 268
[2]	Watts D J and Strogatz S H 1998 Nature 393 440
[3]	Yang X, Cao J and Lu J 2011 Nonlinear Analysis: Real World Applications 12 2252
[4]	Gómez-Gardeñes J, Moreno Y and Arenas A 2007 Phys. Rev. Lett. 98 034101
[5]	Newman M E J, Barabasi A and Watts D J 2006 The Structure and Dynamics of Networks (Princeton, NJ: Princeton University Press)
[6]	Arenas A, Díaz-Guilera A, Kurths J, Moreno Y and Zhou C 2008 Phys. Rep. 469 93
[7]	Duan Z S and Chen G R 2012 Chin. Phys. B 21 080506
[8]	Barahona M and Pecora L M 2002 Phys. Rev. Lett. 89 054101
[9]	Nishikawa T, Motter A E, Lai Y C and Hoppensteadt F C 2003 Phys. Rev. Lett. 91 014101
[10]	Wang X and Chen G 2002 Int. J. Bifurc. Chaos 12 187
[11]	Gómez-Gardeñes J, Góez S, Arenas A and Moreno Y 2011 Phys. Rev. Lett. 106 128701
[12]	Pereira T 2010 Phys. Rev. E 82 036201
[13]	Wang X F and Chen G R 2002 IEEE Trans. Circuit Syst. I 49 54
[14]	Wang X G, Lai Y C and Lai C H 2007 Phys. Rev. E 76 056113
[15]	Wu J, Wang X and Jiao L 2012 Physica A 391 508
[16]	Wang S G and Yao H X 2012 Chin. Phys. B 21 050508
[17]	Yang D S, Liu Z W, Zhao Y and Liu Z B 2012 Chin. Phys. B 21 040503
[18]	Kuperman M and Abramson G 2001 Phys. Rev. Lett. 86 2909
[19]	Pastor-Satorras R and Vespignani A 2001 Phys. Rev. Lett. 86 3200
[20]	Lu Y L, Jiang G P and Song Y R 2012 Chin. Phys. B 21 100207
[21]	Wanduku D and Ladde G S 2012 Nonlinear Analysis: Real World Applications 13 794
[22]	Zhou J, Xiao G, Cheong S A, Fu X, Wong L, Ma S and Cheng T H 2012 Phys. Rev. E 85 036107
[23]	Qian C, Cao J, Lu J and Kurths J 2011 Chaos 21 025116
[24]	Schmittmann B and Mukhopadhyay A 2010 Phys. Rev. E 82 066104
[25]	Iñiguez G, Kertész J, Kaski K K and Barrio R A 2009 Phys. Rev. E 80 066119
[26]	Gross T and Blasius B 2008 J. R. Soc. Interface 5 259
[27]	Leberknight C, Inaltekin H, Chiang M and Poor H V 2012 IEEE Signal Processing Magazine 41
[28]	Albert R and Barabási A L 2002 Rev. Mod. Phys. 74 47
[29]	Chen M, Shang Y, Zou Y and Kurths J 2008 Phys. Rev. E 77 027101
[30]	DeLellis P, diBernardo M and Garofalo F 2008 Chaos 18 037110
[31]	DeLellis P, diBernardo M, Gorochowski T E and Russo G 2010 IEEE Circuits and Systems Magazine 64
[32]	DeLellis P, diBernardo M, Garofalo F and Porfiri M 2010 IEEE Trans. Circuits Syst. I 57 2132
[33]	DeLellis P, diBernardo M and Porfiri M 2011 Chaos 21 033119
[34]	Li M, Wang X and Lai C H 2010 Chaos 20 045114
[35]	West D B 2001 Introduction to Graph Theory 2nd edn. (Upper Saddle River, NJ: Prentice-Hall, Inc)
[36]	Blöchliger I and Zufferey N 2008 Computers & Operations Research 35 960
[37]	Wu C W 1998 IEEE Trans.Circuits Syst. 45 974
[38]	Wu J, Jiao L, Li R and Chen W 2011 Physica D 240 1972
[39]	Kuramoto Y 1984 Chemical Oscillations, Wave and Turbulence (Berlin: Springer-Verlag)
[40]	Smith R D 2010 Chin. Phys. B 19 106401
[41]	Aeyels D and DeSmet F A 2008 Physica D 237 2517
[42]	Li X 2006 Physica D 223 242
[43]	Wu J, Jiao L, Jin C, Liu F, Gong M, Shang R and Chen W 2012 Phys. Rev. E 85 016115
[44]	Graph Coloring Instances, http://mat.gsia.cmu.edu/COLOR//instances.html
[45]	Graph Coloring and Its Generalizations,http://mat.gsia.cmu.edu/COLOR04/

Network evolution driven by dynamics applied to graph coloring

Network evolution driven by dynamics applied to graph coloring

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 45

相关文章 2

Metrics

本文评价

推荐阅读 0

[1]	宋玉蓉, 蒋国平, 巩永旺. Epidemic propagation on adaptive coevolutionary networks with preferential local-world reconnecting strategy[J]. Chin. Phys. B, 2013, 22(4): 40205-040205.
[2]	赵静, 陶林, 俞鸿, 骆建华, 曹志伟, 李亦学. The effects of degree correlations on network topologies and robustness[J]. 中国物理B, 2007, 16(12): 3571-3580.