Scale-Free Automata Networks Are Not Robust in a Collective Computational Task

作者: Christian Darabos , Mario Giacobini , Marco Tomassini

DOI: 10.1007/11861201_59

关键词: AlgorithmComputer scienceComplex networkAverage path lengthRandom graphCellular automatonFace (geometry)Theoretical computer scienceGraphScale (descriptive set theory)Transient (computer programming)Automaton

摘要: We investigate the performances and collective task-solving capabilities of complex networks automata using density problem as a typical case show by computer simulations that evolved Watts–Strogatz small-world have superior performance with respect to scale-free graphs Albert–Barabasi type Besides, are much more robust in face transient uniformly random perturbations This result differs from information diffusion on networks, where faults highly tolerated.

参考文章(20)
Christian Darabos, Marco Tomassini, Mario Giacobini, Evolution and Dynamics of Small-World Cellular Automata. Complex Systems. ,vol. 15, ,(2005)
Peter Schuster, James P. Crutchfield, Evolutionary dynamics : exploring the interplay of selection, accident, neutrality, and function Oxford University Press. ,(2003)
Henryk Fuks-acute, Solution of the density classification problem with two cellular automata rules Physical Review E. ,vol. 55, pp. R2081- R2084 ,(1997) , 10.1103/PHYSREVE.55.R2081
Marco Tomassini, Mario Giacobini, Christian Darabos, Evolution of Small-World Networks of Automata for Computation parallel problem solving from nature. pp. 672- 681 ,(2004) , 10.1007/978-3-540-30217-9_68
Roberto Serra, Marco Villani, Perturbing the Regular Topology of Cellular Automata: Implications for the Dynamics cellular automata for research and industry. ,vol. 2493, pp. 168- 177 ,(2002) , 10.1007/3-540-45830-1_16
MOSHE SIPPER, MARCO TOMASSINI, OLIVIER BEURET, Studying Probabilistic Faults in Evolved Non-Uniform Cellular Automata International Journal of Modern Physics C. ,vol. 7, pp. 923- 939 ,(1996) , 10.1142/S0129183196000776
Mark Land, Richard K Belew, None, No perfect two-state cellular automata for density classification exists. Physical Review Letters. ,vol. 74, pp. 5148- 5150 ,(1995) , 10.1103/PHYSREVLETT.74.5148
Moshe Sipper, Co-evolving non-uniform cellular automata to perform computations Physica D: Nonlinear Phenomena. ,vol. 92, pp. 193- 208 ,(1996) , 10.1016/0167-2789(95)00286-3
Mathieu S. Capcarrere, Moshe Sipper, Marco Tomassini, Two-state, r=1 Cellular Automaton that Classifies Density. Physical Review Letters. ,vol. 77, pp. 4969- 4971 ,(1996) , 10.1103/PHYSREVLETT.77.4969