Naming games in two-dimensional and small-world-connected random geometric networks

We investigate a prototypical agent-based model, the naming game, on two-dimensional random geometric networks. The naming game [Baronchelli et al., J. Stat. Mech.: Theory Exp. (2006) P06014] is a minimal model, employing local communications that captures the emergence of shared communication schemes (languages) in a population of autonomous semiotic agents. Implementing the naming games with local broadcasts on random geometric graphs, serves as a model for agreement dynamics in large-scale, autonomously operating wireless sensor networks. Further, it captures essential features of the scaling properties of the agreement process for spatially embedded autonomous agents. Among the relevant observables capturing the temporal properties of the agreement process, we investigate the cluster-size distribution and the distribution of the agreement times, both exhibiting dynamic scaling. We also present results for the case when a small density of long-range communication links are added on top of the random geometric graph, resulting in a “small-world”-like network and yielding a significantly reduced time to reach global agreement. We construct a finite-size scaling analysis for the agreement times in this case.

Figure 1

(Color) Snapshots of the time evolution of the contents of the agents’ word lists during the process of reaching global agreement on RGG for $N=1000$ nodes at time (a) $t=1$; (b) $t=43$; (c) $t=169$; (d) $t=291$. The average degree is $\overline{k}\approx 12$. Initially, the word lists are empty for all agents. Time, as through the paper, is measured in units of “speaker”-initiated broadcasts per node. Different colors correspond to different words, with black indicating nodes with multiple words. After the early-time increase in the number of different words in the systems, small spatial clusters sharing the same word quickly form, then subsequently “coarsen” until eventually only one global cluster prevails.

Figure 2

(Color online) Time evolution of the relevant observables in the naming game in the fully connected (FC), two-dimensional regular (with four nearest neighbors), and random geometric networks (RGG) for $N=1024$, averaged over 1000 independent realizations: (a) the total number of words in the system $N_w\left(t\right)$; (b) the number of different words $N_d\left(t\right)$; (c) the average success rate $S\left(t\right)$. The average degree of the underlying RGG is $\overline{k}\approx 12$. Data for the FC and $2d$ regular networks are reproduced by our simulations, following Refs. 20, 22, for comparison.

Figure 3

(Color online) Time evolution of the relevant observables in the naming game in random geometric networks (RGG) for three system sizes on log-log scales, averaged over 1000 independent realizations. The average degree of the underlying RGGs is $\overline{k}\approx 12$. (a) The normalized total number of words in the system $N_w\left(t\right)∕N-1$. (b) The normalized number of different words $N_d\left(t\right)∕N$. (c) The average domain size $C\left(t\right)$. The straight line segments correspond to the best-fit power-law decays $N_w\left(t\right)∕N-1\sim t^{-0.36}$, $N_d\left(t\right)∕N\sim t^{-0.74}$, $C\left(t\right)\sim t^{0.79}$ for (a), (b), and (c), respectively.

Figure 4

(Color online) Average and the standard deviation of the convergence time $t_c$ until global agreement is reached, as a function of the number of nodes on log-log scales, averaged over 1000 independent realizations of the NG on RGG. The average degree of the underlying RGGs is $\overline{k}\approx 12$ (squares) and $\overline{k}\approx 50$ (circles). The straight lines correspond to the best-fit power laws with exponents 1.10, for both the average (solid squares) and the standard deviation (open squares) of RGGs with $\overline{k}\approx 12$, and $1.07$ for those of RGGs with $\overline{k}\approx 50$, respectively.

Figure 5

(Color online) Time evolution of the (scaled) number of different words starting from an “empty” word list initial condition, for various average degree $\overline{k}$ on log-log scales. The number of nodes is $N=1000$. The straight line segment indicates the asymptotic power-law decay as determined earlier [Fig. 3b], independent of the neighborhood size $\overline{k}$.

Figure 6

(Color online) (a) Probability densities of the convergence time for three systems sizes. Data are gathered from 100 000 independent realizations of the NG on RGG. The average degree of the underlying RGGs is $\overline{k}\approx 50$. (b) Probability densities for the scaled variable $x=t_c∕⟨t_c\left(N\right)⟩$ for the same data. The inset shows the same scaled histograms on log-lin scales.

Figure 7

(Color online) (a) Probability densities of the cluster size at different times of the agreement dynamics. Data are collected through 100 000 independent realizations of the NG on RGG. The system size of the underlying RGGs is $N=1000$ and the average degree is $\overline{k}\approx 12$. (b) Probability densities for the scaled variable $x=C∕⟨C\left(t\right)⟩$ for the same data as in (a) on log-lin scales. The solid curve represents the best-fit exponential-like tail, $\propto \exp (-1.24x^{1.12})$.

Figure 8

(Color online) Time evolution of the (scaled) (a) total number of words, (b) number of different words, and (c) the average cluster size for SW RGGs on log-log scales, starting from an “empty” word list initial condition, for various density of long-range links $p$, averaged over 1000 independent realizations of the NG on RGG. The number of nodes is $N=5000$ with average degree $\overline{k}\approx 12$.

Figure 9

(Color online) Average convergence time $t_c$ for SW RGGs: (a) As a function of the density of shortcuts for various system sizes. The inset shows the same data on log-log scales. The straight lines correspond to an estimate of the associated (asymptotic) power-law. (b) As a function of the number of nodes on log-log scales for various density of long-range links $p$. The curves shown are obtained by averaging over 1000 independent realizations of the NG on RGG. The average degree of the underlying RGGs is $\overline{k}\approx 12$.

Figure 10

(Color online) Scaled plot of data shown in Fig. 9, as suggested by the finite-size scaling argument [Eq. (13)]. The straight line segments correspond to the best-fit (asymptotic) power-law behavior of the scaling function $g\left(x\right)$ with exponents 1.10 and 0.31, for small and large arguments, respectively, as described in the text [Eq. (14)].