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

On the evolutionary language game in structured and adaptive populations

We propose an evolutionary model for the emergence of shared linguistic convention in a population of agents whose social structure is modelled by complex networks. Through agent-based simulations, we show a process of convergence towards a common language, and explore how the topology of the underlying networks affects its dynamics. We find that small-world effects act to speed up convergence, but observe no effect of topology on the communicative efficiency of common languages. We further explore differences in agent learning, discriminating between scenarios in which new agents learn from their parents (vertical transmission) versus scenarios in which they learn from their neighbors (oblique transmission), finding that vertical transmission results in faster convergence and generally higher communicability. Optimal languages can be formed when parental learning is dominant, but a small amount of neighbor learning is included. As a last point, we illustrate an exclusion effect leading to core-periphery networks in an adaptive networks setting when agents attempt to reconnect towards better communicators in the population.

Temporal network epistemology: On reaching consensus in a real-world setting

This work develops the concept of the temporal network epistemology model enabling the simulation of the learning process in dynamic networks. The results of the research, conducted on the temporal social network generated using the CogSNet model and on the static topologies as a reference, indicate a significant influence of the network temporal dynamics on the outcome and flow of the learning process. It has been shown that not only the dynamics of reaching consensus is different compared to baseline models but also that previously unobserved phenomena appear, such as uninformed agents or different consensus states for disconnected components. It has also been observed that sometimes only the change of the network structure can contribute to reaching consensus. The introduced approach and the experimental results can be used to better understand the way how human communities collectively solve both complex problems at the scientific level and to inquire into the correctness of less complex but common and equally important beliefs' spreading across entire societies.

A bird's-eye view of naming game dynamics: From trait competition to Bayesian inference

The present contribution reviews a set of different versions of the basic naming game model, differing in the underlying topology or in the mechanisms regulating the interactions between agents. We include also a Bayesian naming game model recently introduced, which merges the social dynamics of the basic naming game model with the Bayesian learning framework introduced by Tenenbaum and co-workers. The latter model goes beyond the fixed nature of names and concepts of standard semiotic dynamics models and the corresponding one-shot learning process by describing dynamically how agents can generalize a concept from a few examples, according to principles of Bayesian inference.

The impact of variable commitment in the Naming Game on consensus formation

The Naming Game has proven to be an important model of opinion dynamics in complex networks. It is significantly enriched by the introduction of nodes committed to a single opinion. The resulting model is still simple but captures core concepts of opinion dynamics in networks. This model limitation is rigid commitment which never changes. Here we study the effect that making commitment variable has on the dynamics of the system. Committed nodes are assigned a commitment strength, w, defining their willingness to lose (in waning), gain (for increasing) or both (in variable) commitment to an opinion. Such model has committed nodes that can stick to a single opinion for some time without losing their flexibility to change it in the long run. The traditional Naming Game corresponds to setting w at infinity. A change in commitment strength impacts the critical fraction of population necessary for a minority consensus. Increasing w lowers critical fraction for waning commitment but increases this fraction for increasing commitment. Further, we show that if different nodes have different values of w, higher standard deviation of w increases the critical fraction for waning commitment and decrease this fraction for increasing commitment.

Analysis of the high-dimensional naming game with committed minorities

The naming game has become an archetype for linguistic evolution and mathematical social behavioral analysis. In the model presented here, there are N individuals and K words. Our contribution is developing a robust method that handles the case when K=O(N). The initial condition plays a crucial role in the ordering of the system. We find that the system with high Shannon entropy has a higher consensus time and a lower critical fraction of zealots compared to low-entropy states. We also show that the critical number of committed agents decreases with the number of opinions and grows with the community size for each word. These results complement earlier conclusions that diversity of opinion is essential for evolution; without it, the system stagnates in the status quo [S. A. Marvel et al., Phys. Rev. Lett. 109, 118702 (2012)PRLTAO0031-900710.1103/PhysRevLett.109.118702]. In contrast, our results suggest that committed minorities can more easily conquer highly diverse systems, showing them to be inherently unstable.

An Analysis of the Matching Hypothesis in Networks

The matching hypothesis in social psychology claims that people are more likely to form a committed relationship with someone equally attractive. Previous works on stochastic models of human mate choice process indicate that patterns supporting the matching hypothesis could occur even when similarity is not the primary consideration in seeking partners. Yet, most if not all of these works concentrate on fully-connected systems. Here we extend the analysis to networks. Our results indicate that the correlation of the couple's attractiveness grows monotonically with the increased average degree and decreased degree diversity of the network. This correlation is lower in sparse networks than in fully-connected systems, because in the former less attractive individuals who find partners are likely to be coupled with ones who are more attractive than them. The chance of failing to be matched decreases exponentially with both the attractiveness and the degree. The matching hypothesis may not hold when the degree-attractiveness correlation is present, which can give rise to negative attractiveness correlation. Finally, we find that the ratio between the number of matched couples and the size of the maximum matching varies non-monotonically with the average degree of the network. Our results reveal the role of network topology in the process of human mate choice and bring insights into future investigations of different matching processes in networks.

Propensity and stickiness in the naming game: tipping fractions of minorities

Agent-based models of the binary naming game are generalized here to represent a family of models parameterized by the introduction of two continuous parameters. These parameters define varying listener-speaker interactions on the individual level with one parameter controlling the speaker and the other controlling the listener of each interaction. The major finding presented here is that the generalized naming game preserves the existence of critical thresholds for the size of committed minorities. Above such threshold, a committed minority causes a fast (in time logarithmic in size of the network) convergence to consensus, even when there are other parameters influencing the system. Below such threshold, reaching consensus requires time exponential in the size of the network. Moreover, the two introduced parameters cause bifurcations in the stabilities of the system's fixed points and may lead to changes in the system's consensus.

Opinion dynamics and influencing on random geometric graphs

We investigate the two-word Naming Game on two-dimensional random geometric graphs. Studying this model advances our understanding of the spatial distribution and propagation of opinions in social dynamics. A main feature of this model is the spontaneous emergence of spatial structures called opinion domains which are geographic regions with clear boundaries within which all individuals share the same opinion. We provide the mean-field equation for the underlying dynamics and discuss several properties of the equation such as the stationary solutions and two-time-scale separation. For the evolution of the opinion domains we find that the opinion domain boundary propagates at a speed proportional to its curvature. Finally we investigate the impact of committed agents on opinion domains and find the scaling of consensus time.

Cascading failures in spatially-embedded random networks

Cascading failures constitute an important vulnerability of interconnected systems. Here we focus on the study of such failures on networks in which the connectivity of nodes is constrained by geographical distance. Specifically, we use random geometric graphs as representative examples of such spatial networks, and study the properties of cascading failures on them in the presence of distributed flow. The key finding of this study is that the process of cascading failures is non-self-averaging on spatial networks, and thus, aggregate inferences made from analyzing an ensemble of such networks lead to incorrect conclusions when applied to a single network, no matter how large the network is. We demonstrate that this lack of self-averaging disappears with the introduction of a small fraction of long-range links into the network. We simulate the well studied preemptive node removal strategy for cascade mitigation and show that it is largely ineffective in the case of spatial networks. We introduce an altruistic strategy designed to limit the loss of network nodes in the event of a cascade triggering failure and show that it performs better than the preemptive strategy. Finally, we consider a real-world spatial network viz. a European power transmission network and validate that our findings from the study of random geometric graphs are also borne out by simulations of cascading failures on the empirical network.

Evolution of cooperation on spatially embedded networks

In this work we study the behavior of classical two-person, two-strategies evolutionary games on networks embedded in a Euclidean two-dimensional space with different kinds of degree distributions and topologies going from regular to random and to scale-free ones. Using several imitative microscopic dynamics, we study the evolution of global cooperation on the above network classes and find that specific topologies having a hierarchical structure and an inhomogeneous degree distribution, such as Apollonian and grid-based networks, are very conducive to cooperation. Spatial scale-free networks are still good for cooperation but to a lesser degree. Both classes of networks enhance average cooperation in all games with respect to standard random geometric graphs and regular grids by shifting the boundaries between cooperative and defective regions. These findings might be useful in the design of interaction structures that maintain cooperation when the agents are constrained to live in physical two-dimensional space.

Opinion formation in time-varying social networks: The case of the naming game

We study the dynamics of the naming game as an opinion formation model on time-varying social networks. This agent-based model captures the essential features of the agreement dynamics by means of a memory-based negotiation process. Our study focuses on the impact of time-varying properties of the social network of the agents on the naming game dynamics. In particular, we perform a computational exploration of this model using simulations on top of real networks. We investigate the outcomes of the dynamics on two different types of time-varying data: (1) the networks vary on a day-to-day basis and (2) the networks vary within very short intervals of time (20 sec). In the first case, we find that networks with strong community structure hinder the system from reaching global agreement; the evolution of the naming game in these networks maintains clusters of coexisting opinions indefinitely leading to metastability. In the second case, we investigate the evolution of the naming game in perfect synchronization with the time evolution of the underlying social network shedding new light on the traditional emergent properties of the game that differ largely from what has been reported in the existing literature.

Accelerating consensus on coevolving networks: the effect of committed individuals

Social networks are not static but, rather, constantly evolve in time. One of the elements thought to drive the evolution of social network structure is homophily-the need for individuals to connect with others who are similar to them. In this paper, we study how the spread of a new opinion, idea, or behavior on such a homophily-driven social network is affected by the changing network structure. In particular, using simulations, we study a variant of the Axelrod model on a network with a homophily-driven rewiring rule imposed. First, we find that the presence of rewiring within the network, in general, impedes the reaching of consensus in opinion, as the time to reach consensus diverges exponentially with network size N. We then investigate whether the introduction of committed individuals who are rigid in their opinion on a particular issue can speed up the convergence to consensus on that issue. We demonstrate that as committed agents are added, beyond a critical value of the committed fraction, the consensus time growth becomes logarithmic in network size N. Furthermore, we show that slight changes in the interaction rule can produce strikingly different results in the scaling behavior of consensus time, T(c). However, the benefit gained by introducing committed agents is qualitatively preserved across all the interaction rules we consider.

Human-centric sensing

The first decade of the century witnessed a proliferation of devices with sensing and communication capabilities in the possession of the average individual. Examples range from camera phones and wireless global positioning system units to sensor-equipped, networked fitness devices and entertainment platforms (such as Wii). Social networking platforms emerged, such as Twitter, that allow sharing information in real time. The unprecedented deployment scale of such sensors and connectivity options ushers in an era of novel data-driven applications that rely on inputs collected by networks of humans or measured by sensors acting on their behalf. These applications will impact domains as diverse as health, transportation, energy, disaster recovery, intelligence and warfare. This paper surveys the important opportunities in human-centric sensing, identifies challenges brought about by such opportunities and describes emerging solutions to these challenges.

Consensus in networks of mobile communicating agents

Populations of mobile and communicating agents describe a vast array of technological and natural systems, ranging from sensor networks to animal groups. Here, we investigate how a group-level agreement may emerge in the continuously evolving network defined by the local interactions of the moving individuals. We adopt a general scheme of motion in two dimensions and we let the individuals interact through the minimal naming game, a prototypical scheme to investigate social consensus. We distinguish different regimes of convergence determined by the emission range of the agents and by their mobility, and we identify the corresponding scaling behaviors of the consensus time. In the same way, we rationalize also the behavior of the maximum memory used during the convergence process, which determines the minimum cognitive/storage capacity needed by the individuals. Overall, we believe that the simple and general model presented in this paper can represent a helpful reference for a better understanding of the behavior of populations of mobile agents.

Social consensus through the influence of committed minorities

We show how the prevailing majority opinion in a population can be rapidly reversed by a small fraction p of randomly distributed committed agents who consistently proselytize the opposing opinion and are immune to influence. Specifically, we show that when the committed fraction grows beyond a critical value p(c) ≈ 10%, there is a dramatic decrease in the time T(c) taken for the entire population to adopt the committed opinion. In particular, for complete graphs we show that when p < pc, T(c) ~ exp [α(p)N], whereas for p>p(c), T(c) ~ ln N. We conclude with simulation results for Erdős-Rényi random graphs and scale-free networks which show qualitatively similar behavior.

Social influencing and associated random walk models: Asymptotic consensus times on the complete graph

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.

Role of feedback and broadcasting in the naming game

The naming game (NG) describes the agreement dynamics of a population of agents that interact locally in a pairwise fashion, and in recent years statistical physics tools and techniques have greatly contributed to shed light on its rich phenomenology. Here we investigate in details the role played by the way in which the two agents update their states after an interaction. We show that slightly modifying the NG rules in terms of which agent performs the update in given circumstances (i.e., after a success) can either alter dramatically the overall dynamics or leave it qualitatively unchanged. We understand analytically the first case by casting the model in the broader framework of a generalized NG. As for the second case, on the other hand, we note that the modified rule reproducing the main features of the usual NG corresponds in fact to a simplification of it consisting in the elimination of feedback between the agents. This allows us to introduce and study a very natural broadcasting scheme on networks that can be potentially relevant for different applications, such as the design and implementation of autonomous sensor networks, as pointed out in the recent literature.

Diversity, competition, extinction: the ecophysics of language change

As indicated early by Charles Darwin, languages behave and change very much like living species. They display high diversity, differentiate in space and time, emerge and disappear. A large body of literature has explored the role of information exchanges and communicative constraints in groups of agents under selective scenarios. These models have been very helpful in providing a rationale on how complex forms of communication emerge under evolutionary pressures. However, other patterns of large-scale organization can be described using mathematical methods ignoring communicative traits. These approaches consider shorter time scales and have been developed by exploiting both theoretical ecology and statistical physics methods. The models are reviewed here and include extinction, invasion, origination, spatial organization, coexistence and diversity as key concepts and are very simple in their defining rules. Such simplicity is used in order to catch the most fundamental laws of organization and those universal ingredients responsible for qualitative traits. The similarities between observed and predicted patterns indicate that an ecological theory of language is emerging, supporting (on a quantitative basis) its ecological nature, although key differences are also present. Here, we critically review some recent advances and outline their implications and limitations as well as highlight problems for future research.