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

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