Europhys. Lett.
Volume 73, Number 6, March 2006
Page(s) 969 - 975
Section Interdisciplinary physics and related areas of science and technology
Published online 10 February 2006
Europhys. Lett., 73 (6), pp. 969-975 (2006)
DOI: 10.1209/epl/i2005-10481-7

Agreement dynamics on small-world networks

L. Dall'Asta1, A. Baronchelli2, A. Barrat1 and V. Loreto2

1  Laboratoire de Physique Théorique (CNRS UMR8627), Bâtiment 210 Université Paris-Sud - 91405 Orsay cedex, France
2  Dipartimento di Fisica, Università "La Sapienza" and SMC-INFM P.le A. Moro 2, 00185 Roma, Italy

received 1 December 2005; accepted 26 January 2006
published online 10 February 2006

In this paper we analyze the effect of a non-trivial topology on the dynamics of the so-called Naming Game, a recently introduced model which addresses the issue of how shared conventions emerge spontaneously in a population of agents. We consider in particular the small-world topology and study the convergence towards the global agreement as a function of the population size N as well as of the parameter p which sets the rate of rewiring leading to the small-world network. As long as $p \gg 1/N$, there exists a crossover time scaling as N/p2 which separates an early one-dimensional-like dynamics from a late-stage mean-field-like behavior. At the beginning of the process, the local quasi-one-dimensional topology induces a coarsening dynamics which allows for a minimization of the cognitive effort (memory) required to the agents. In the late stages, on the other hand, the mean-field-like topology leads to a speed-up of the convergence process with respect to the one-dimensional case.

89.75.Fb - Structures and organization in complex systems.
05.65.+b - Self-organized systems.

© EDP Sciences 2006