Network evolution driven by dynamics applied to graph coloring

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

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.

Keywords: network dynamics evolution of network evolutionary strategies graph coloring problem

Received: 31 August 2012
Revised: 22 October 2012
Accepted manuscript online:

PACS:	05.45.-a	(Nonlinear dynamics and chaos)
	02.10.Ox	(Combinatorics; graph theory)
	02.50.-r	(Probability theory, stochastic processes, and statistics)

Fund: Project supported by the National Natural Science Foundation of China (Grants Nos. 61072139, 61072106, 61203303, 61003198, 61272279, and 61003199).

Corresponding Authors: Wu Jian-She
E-mail: jianshewu@126.com

Cite this article:

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

[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/

[1]	Epidemic propagation on adaptive coevolutionary networks with preferential local-world reconnecting strategy Song Yu-Rong (宋玉蓉), Jiang Guo-Ping (蒋国平), Gong Yong-Wang (巩永旺). Chin. Phys. B, 2013, 22(4): 040205.
[2]	The effects of degree correlations on network topologies and robustness Zhao Jing(赵静), Tao Lin(陶林), Yu Hong(俞鸿), Luo Jian-Hua(骆建华), Cao Zhi-Wei(曹志伟), and Li Yi-Xue(李亦学). Chin. Phys. B, 2007, 16(12): 3571-3580.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Network evolution driven by dynamics applied to graph coloring

Cite this article:

Online attention