^{1,2}, C. Lim

^{1,2}, S. Sreenivasan

^{1,3,4}, J. Xie

^{1,3}, B. K. Szymanski

^{1,3}and G. Korniss

^{1,4}

### Abstract

We investigate consensus formation and the asymptotic consensus times in stylized individual- or agent-based models, in which global agreement is achieved through pairwise negotiations with or without a bias. Considering a class of individual-based models on finite complete graphs, we introduce a coarse-graining approach (lumping microscopic variables into macrostates) to analyze the ordering dynamics in an associated random-walk framework. Within this framework, yielding a linear system, we derive general equations for the expected consensus time and the expected time spent in each macro-state. Further, we present the asymptotic solutions of the 2-word naming game and separately discuss its behavior under the influence of an external field and with the introduction of committed agents.

Individual- or agent-based models provide invaluable tools to investigate the collective behavior and response of complex social systems. These systems typically consist of a large number of individuals interacting through a random and sparse network topology. Despite this non-trivial network topology, it has been demonstrated in many recent examples that unlike in low-dimensional spatially-embedded systems with short-range connections, the collective dynamics in sparse random graphs (with no community structure) exhibit scaling properties very similar to those observed on the complete graph. Therefore, studying fundamental agreement processes on the complete graph can yield insights for the ordering process in more realistic sparse random networks. In this paper, we consider two simple individual-based models and develop a mathematical framework which yields asymptotically exact consensus times for large but finite complete graphs of size

*N*. In particular, after demonstrating the feasibility of this framework on known examples, we apply it to study two distinct stylized approaches in social influencing: (i) influencing individuals by a global external field (mimicking mass media effects) and (ii) introducing committed individuals with a fixed designated opinion (who can influence others but themselves are immune to influence). In the former case, we find the external field dominates the consensus in the large network-size limit, while in the latter case, we find the existence of a tipping point, associated with the disappearance of the metastable state in the opinion space. The results further our understanding of timescales associated with reaching consensus in social networks.

This work was supported in part by the Army Research Laboratory under Cooperative Agreement Number W911NF-09-2-0053, by the Army Research Office Grant No. W911NF-09-1-0254, and by the Office of Naval Research Grant No. N00014-09-1-0607. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government.

I. INTRODUCTION

II. CONSENSUS TIME IN THE VOTER MODEL ON THE COMPLETE GRAPH

A. First-step analysis of consensus times in the voter model

III. THE 2-WORD NAMING GAME

A. First-step analysis of consensus times in the 2-word Naming Game

IV. THE 2-WORD NAMING GAME WITH EXTERNAL INFLUENCE

A. First-step analysis of probability of consensus

V. THE 2-WORD NAMING GAME WITH COMMITTED AGENTS

VI. SUMMARY

### Key Topics

- Random walks
- 15.0
- Agent based models
- 8.0
- External field
- 8.0
- Social system dynamics
- 6.0
- Network topology
- 5.0

## Figures

(Color online) Consensus time for voter model on complete graph. The vertical axis represents the consensus time (normalized by *N*). The horizontal axis is the number of nodes in complete graph. Each star point is an average of 10 runs of numerical simulations of voter model and the solid straight line consists of the solutions of the linear equation for each *N* value.

(Color online) Consensus time for voter model on complete graph. The vertical axis represents the consensus time (normalized by *N*). The horizontal axis is the number of nodes in complete graph. Each star point is an average of 10 runs of numerical simulations of voter model and the solid straight line consists of the solutions of the linear equation for each *N* value.

(Color online) Vector field of the random walk coarse-grained from 2-word naming game. Each vector is the expected drift of the random walk at macrostates . The network is 10 nodes complete graph and the domain of random walk is the lower triangle of the square lattice.

(Color online) Vector field of the random walk coarse-grained from 2-word naming game. Each vector is the expected drift of the random walk at macrostates . The network is 10 nodes complete graph and the domain of random walk is the lower triangle of the square lattice.

(Color online) Consensus time (normalized by *N*) as a function of the logarithm of the network size *N* for 2-word naming game on complete graph. Each star point is an average of 10 runs of numerical simulations of 2-word naming game and the solid straight line consists of the solutions of the linear equation for each *N*.

(Color online) Consensus time (normalized by *N*) as a function of the logarithm of the network size *N* for 2-word naming game on complete graph. Each star point is an average of 10 runs of numerical simulations of 2-word naming game and the solid straight line consists of the solutions of the linear equation for each *N*.

(Color online) The expected time spent on each macrostate before consensus in the 2-word NG on a complete graph with *N* = 100 nodes. The vertical axis *T*(*n* _{ A },*n* _{ B }) is the expected time that the random walk spends in macrostate (*n* _{ A },*n* _{ B }) before consensus, starting from the (*n* _{ A }(0),*n* _{ B }(0)) = (50,50) initial macrostate.

(Color online) The expected time spent on each macrostate before consensus in the 2-word NG on a complete graph with *N* = 100 nodes. The vertical axis *T*(*n* _{ A },*n* _{ B }) is the expected time that the random walk spends in macrostate (*n* _{ A },*n* _{ B }) before consensus, starting from the (*n* _{ A }(0),*n* _{ B }(0)) = (50,50) initial macrostate.

(Color online) Vector field representing the drift of the coarse-grained random walk for four different central influence levels on a complete graph with *N*=20. Increasing *f* corresponds to a progressively stronger biased flow toward state A. The length of each vector has been rescaled to its square root to avoid cluttering the whole graph.

(Color online) Vector field representing the drift of the coarse-grained random walk for four different central influence levels on a complete graph with *N*=20. Increasing *f* corresponds to a progressively stronger biased flow toward state A. The length of each vector has been rescaled to its square root to avoid cluttering the whole graph.

(Color online) Expected time spent on each macrostate before consensus *T*(*n* _{ A },*n* _{ B }) in the 2-word NG on complete graph with *N* = 100 with central influence *f* = 0.05, starting from a unbiased initial macrostate (*n* _{ A }(0),*n* _{ B }(0)) = (50,50).

(Color online) Expected time spent on each macrostate before consensus *T*(*n* _{ A },*n* _{ B }) in the 2-word NG on complete graph with *N* = 100 with central influence *f* = 0.05, starting from a unbiased initial macrostate (*n* _{ A }(0),*n* _{ B }(0)) = (50,50).

(Color online) Probability of all A consensus *P* _{ A } with different external influence level *f* starting from macrostate (*n* _{ A },*n* _{ B }) = (*n* _{0},*N* − *n* _{0}) on 100-node complete graph.

(Color online) Probability of all A consensus *P* _{ A } with different external influence level *f* starting from macrostate (*n* _{ A },*n* _{ B }) = (*n* _{0},*N* − *n* _{0}) on 100-node complete graph.

(Color online) Probability of all B consensus 1 − *P* _{ A } starting from macrostate (*n* _{ A },*n* _{ B }) = (*N*/2,*N*/2) as a function of network size *N* with different external influence level *f* ’s.

(Color online) Probability of all B consensus 1 − *P* _{ A } starting from macrostate (*n* _{ A },*n* _{ B }) = (*N*/2,*N*/2) as a function of network size *N* with different external influence level *f* ’s.

(Color online) Expected normalized consensus time () as a function of the initial macrostate (*n* _{ A },*n* _{ B }) on the complete graph with *N* = 100 nodes. (a) When the fraction of committed agents is *q* = 0.06 < *q* _{ c } and (b) when *q* = 0.12 > *q* _{ c }.

(Color online) Expected normalized consensus time () as a function of the initial macrostate (*n* _{ A },*n* _{ B }) on the complete graph with *N* = 100 nodes. (a) When the fraction of committed agents is *q* = 0.06 < *q* _{ c } and (b) when *q* = 0.12 > *q* _{ c }.

(Color online) Expected time spent in each macrostate before consensus *T*(*n* _{ A },*n* _{ B }) on the complete graph with *N* = 100 nodes, starting from the (*n* _{ A }(0),*n* _{ B }(0)) = (*n* _{ q },*N* − *n* _{ q }) initial macrostate, (a) for *q* = 0.06 < *q* _{ c } and (b) for *q* = 0.12 > *q* _{ c }.

(Color online) Expected time spent in each macrostate before consensus *T*(*n* _{ A },*n* _{ B }) on the complete graph with *N* = 100 nodes, starting from the (*n* _{ A }(0),*n* _{ B }(0)) = (*n* _{ q },*N* − *n* _{ q }) initial macrostate, (a) for *q* = 0.06 < *q* _{ c } and (b) for *q* = 0.12 > *q* _{ c }.

(Color online) Normalized time spent near the consensus state before consensus as a function of network size *N* for different fraction of committed agents *q*, including cases for both *q* < *q* _{ c } and *q* > *q* _{ c }. Note the logarithmic scales on the horizontal axis.

(Color online) Normalized time spent near the consensus state before consensus as a function of network size *N* for different fraction of committed agents *q*, including cases for both *q* < *q* _{ c } and *q* > *q* _{ c }. Note the logarithmic scales on the horizontal axis.

(Color online) Normalized time spent near the meta-stable state as a function of network size *N* for different fraction of committed agents *q*, (a) for *q* < *q* _{ c } and (b) for *q* > *q* _{ c }. The behavior for *q* = 0.08 is shown in both (a) and (b), corresponding to our rough estimate of the critical fraction of committed agents, *q* _{ c } ≈ 0.08 ± 0.01.

(Color online) Normalized time spent near the meta-stable state as a function of network size *N* for different fraction of committed agents *q*, (a) for *q* < *q* _{ c } and (b) for *q* > *q* _{ c }. The behavior for *q* = 0.08 is shown in both (a) and (b), corresponding to our rough estimate of the critical fraction of committed agents, *q* _{ c } ≈ 0.08 ± 0.01.

## Tables

Update events for the voter model and the associated random walk transition probabilities.

Update events for the voter model and the associated random walk transition probabilities.

Update events for the 2-word naming game and the associated random walk transition probabilities.

Update events for the 2-word naming game and the associated random walk transition probabilities.

Update events for the 2-word naming game with central influence and the associated random walk transition probabilities.

Update events for the 2-word naming game with central influence and the associated random walk transition probabilities.

Update events for the 2-word naming game with committed agents and the associated random walk transition probabilities.

Update events for the 2-word naming game with committed agents and the associated random walk transition probabilities.

Article metrics loading...

Full text loading...

Commenting has been disabled for this content