Performance and Robustness of Cellular Automata Computation on Irregular Networks

We investigate the performances of collective task-solving capabilities and the robustness of complex networks of automata using the density and synchronization problems as typical cases. We show by computer simulations that evolved Watts--Strogatz small-world networks have superior performance with respect to several kinds of scale-free graphs. Besides, we show that Watts--Strogatz networks are as robust in the face of random perturbations, both transient and permanent, as configuration scale-free networks, while being widely superior to Barabàsi--Albert networks. This result differs from information diffusion on scale-free networks, where random faults are highly tolerated by similar topologies.