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