Nonequilibrium dynamics of language games on complex networks

Collective effect of self-learning and social learning on language dynamics: a naming game approach in social networks

Linguistic rules form the cornerstone of human communication, enabling people to understand and interact with one another effectively. However, there are always irregular exceptions to regular rules, with one of the most notable being the past tense of verbs in English. In this work, a naming game approach is developed to investigate the collective effect of social behaviours on language dynamics, which encompasses social learning, self-learning with preference and forgetting due to memory constraints. Two features that pertain to individuals' influential ability and affinity are introduced to assess an individual's role of social influence and discount the information they communicate in the Bayesian inference-based social learning model. Our findings suggest that network heterogeneity and community structure significantly impact language dynamics, as evidenced in synthetic and real-world networks. Furthermore, self-learning significantly enhances the process of language regularization, while forgetting has a relatively minor impact. The results highlight the substantial influence of network structure and social behaviours on the transition of opinions, from consensus to polarization, demonstrating its importance in language dynamics. This work sheds new light on how individual learners adopt language rules through the lenses of complexity science and decision science, advancing our understanding of language dynamics.

Hyper-cores promote localization and efficient seeding in higher-order processes

Going beyond networks, to include higher-order interactions of arbitrary sizes, is a major step to better describe complex systems. In the resulting hypergraph representation, tools to identify structures and central nodes are scarce. We consider the decomposition of a hypergraph in hyper-cores, subsets of nodes connected by at least a certain number of hyperedges of at least a certain size. We show that this provides a fingerprint for data described by hypergraphs and suggests a novel notion of centrality, the hypercoreness. We assess the role of hyper-cores and nodes with large hypercoreness in higher-order dynamical processes: such nodes have large spreading power and spreading processes are localized in central hyper-cores. Additionally, in the emergence of social conventions very few committed individuals with high hypercoreness can rapidly overturn a majority convention. Our work opens multiple research avenues, from comparing empirical data to model validation and study of temporally varying hypergraphs.

Does Spending More Always Ensure Higher Cooperation? An Analysis of Institutional Incentives on Heterogeneous Networks

Humans have developed considerable machinery used at scale to create policies and to distribute incentives, yet we are forever seeking ways in which to improve upon these, our institutions. Especially when funding is limited, it is imperative to optimise spending without sacrificing positive outcomes, a challenge which has often been approached within several areas of social, life and engineering sciences. These studies often neglect the availability of information, cost restraints or the underlying complex network structures, which define real-world populations. Here, we have extended these models, including the aforementioned concerns, but also tested the robustness of their findings to stochastic social learning paradigms. Akin to real-world decisions on how best to distribute endowments, we study several incentive schemes, which consider information about the overall population, local neighbourhoods or the level of influence which a cooperative node has in the network, selectively rewarding cooperative behaviour if certain criteria are met. Following a transition towards a more realistic network setting and stochastic behavioural update rule, we found that carelessly promoting cooperators can often lead to their downfall in socially diverse settings. These emergent cyclic patterns not only damage cooperation, but also decimate the budgets of external investors. Our findings highlight the complexity of designing effective and cogent investment policies in socially diverse populations.

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.

Coordination and equilibrium selection in games: the role of local effects

We study the role of local effects and finite size effects in reaching coordination and in equilibrium selection in two-player coordination games. We investigate three update rules - the replicator dynamics (RD), the best response (BR), and the unconditional imitation (UI). For the pure coordination game with two equivalent strategies we find a transition from a disordered state to coordination for a critical value of connectivity. The transition is system-size-independent for the BR and RD update rules. For the IU it is system-size-dependent, but coordination can always be reached below the connectivity of a complete graph. We also consider the general coordination game which covers a range of games, such as the stag hunt. For these games there is a payoff-dominant strategy and a risk-dominant strategy with associated states of equilibrium coordination. We analyse equilibrium selection analytically and numerically. For the RD and BR update rules mean-field predictions agree with simulations and the risk-dominant strategy is evolutionary favoured independently of local effects. When players use the unconditional imitation, however, we observe coordination in the payoff-dominant strategy. Surprisingly, the selection of pay-off dominant equilibrium only occurs below a critical value of the network connectivity and disappears in complete graphs. As we show, it is a combination of local effects and update rule that allows for coordination on the payoff-dominant strategy.

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.

Modelling opinion dynamics in the age of algorithmic personalisation

Modern technology has drastically changed the way we interact and consume information. For example, online social platforms allow for seamless communication exchanges at an unprecedented scale. However, we are still bounded by cognitive and temporal constraints. Our attention is limited and extremely valuable. Algorithmic personalisation has become a standard approach to tackle the information overload problem. As result, the exposure to our friends’ opinions and our perception about important issues might be distorted. However, the effects of algorithmic gatekeeping on our hyper-connected society are poorly understood. Here, we devise an opinion dynamics model where individuals are connected through a social network and adopt opinions as function of the view points they are exposed to. We apply various filtering algorithms that select the opinions shown to each user (i) at random (ii) considering time ordering or (iii) its current opinion. Furthermore, we investigate the interplay between such mechanisms and crucial features of real networks. We found that algorithmic filtering might influence opinions’ share and distributions, especially in case information is biased towards the current opinion of each user. These effects are reinforced in networks featuring topological and spatial correlations where echo chambers and polarisation emerge. Conversely, heterogeneity in connectivity patterns reduces such tendency. We consider also a scenario where one opinion, through nudging, is centrally pushed to all users. Interestingly, even minimal nudging is able to change the status quo moving it towards the desired view point. Our findings suggest that simple filtering algorithms might be powerful tools to regulate opinion dynamics taking place on social networks.

The emergence of consensus: a primer

The origin of population-scale coordination has puzzled philosophers and scientists for centuries. Recently, game theory, evolutionary approaches and complex systems science have provided quantitative insights on the mechanisms of social consensus. However, the literature is vast and widely scattered across fields, making it hard for the single researcher to navigate it. This short review aims to provide a compact overview of the main dimensions over which the debate has unfolded and to discuss some representative examples. It focuses on those situations in which consensus emerges 'spontaneously' in the absence of centralized institutions and covers topics that include the macroscopic consequences of the different microscopic rules of behavioural contagion, the role of social networks and the mechanisms that prevent the formation of a consensus or alter it after it has emerged. Special attention is devoted to the recent wave of experiments on the emergence of consensus in social systems.

Consensus dynamics in online collaboration systems

BACKGROUND

In this paper, we study the process of opinion dynamics and consensus building in online collaboration systems, in which users interact with each other following their common interests and their social profiles. Specifically, we are interested in how users similarity and their social status in the community, as well as the interplay of those two factors, influence the process of consensus dynamics.

METHODS

For our study, we simulate the diffusion of opinions in collaboration systems using the well-known Naming Game model, which we extend by incorporating an interaction mechanism based on user similarity and user social status. We conduct our experiments on collaborative datasets extracted from the Web.

RESULTS

Our findings reveal that when users are guided by their similarity to other users, the process of consensus building in online collaboration systems is delayed. A suitable increase of influence of user social status on their actions can in turn facilitate this process.

CONCLUSIONS

In summary, our results suggest that achieving an optimal consensus building process in collaboration systems requires an appropriate balance between those two factors.

Solution to urn models of pairwise interaction with application to social, physical, and biological sciences

We investigate a family of urn models that correspond to one-dimensional random walks with quadratic transition probabilities that have highly diverse applications. Well-known instances of these two-urn models are the Ehrenfest model of molecular diffusion, the voter model of social influence, and the Moran model of population genetics. We also provide a generating function method for diagonalizing the corresponding transition matrix that is valid if and only if the underlying mean density satisfies a linear differential equation and express the eigenvector components as terms of ordinary hypergeometric functions. The nature of the models lead to a natural extension to interaction between agents in a general network topology. We analyze the dynamics on uncorrelated heterogeneous degree sequence networks and relate the convergence times to the moments of the degree sequences for various pairwise interaction mechanisms.

Influence of periodic external fields in multiagent models with language dynamics

We investigate large-scale effects induced by external fields, phenomenologically interpreted as mass media, in multiagent models evolving with the microscopic dynamics of the binary naming game. In particular, we show that a single external field, broadcasting information at regular time intervals, can reverse the majority opinion of the population, provided the frequency and the effectiveness of the sent messages lie above well-defined thresholds. We study the phase structure of the model in the mean field approximation and in numerical simulations with several network topologies. We also investigate the influence on the agent dynamics of two competing external fields, periodically broadcasting different messages. In finite regions of the parameter space we observe periodic equilibrium states in which the average opinion densities are reversed with respect to naive expectations. Such equilibria occur in two cases: (i) when the frequencies of the competing messages are different but close to each other; (ii) when the frequencies are equal and the relative time shift of the messages does not exceed half a period. We interpret the observed phenomena as a result of the interplay between the external fields and the internal dynamics of the agents and conclude that, depending on the model parameters, the naming game is consistent with scenarios of first- or second-mover advantage (to borrow an expression from the jargon of business strategy).

Domain learning naming game for color categorization

Naming game simulates the evolution of vocabulary in a population of agents. Through pairwise interactions in the games, agents acquire a set of vocabulary in their memory for object naming. The existing model confines to a one-to-one mapping between a name and an object. Focus is usually put onto name consensus in the population rather than knowledge learning in agents, and hence simple learning model is usually adopted. However, the cognition system of human being is much more complex and knowledge is usually presented in a complicated form. Therefore, in this work, we extend the agent learning model and design a new game to incorporate domain learning, which is essential for more complicated form of knowledge. In particular, we demonstrate the evolution of color categorization and naming in a population of agents. We incorporate the human perceptive model into the agents and introduce two new concepts, namely subjective perception and subliminal stimulation, in domain learning. Simulation results show that, even without any supervision or pre-requisition, a consensus of a color naming system can be reached in a population solely via the interactions. Our work confirms the importance of society interactions in color categorization, which is a long debate topic in human cognition. Moreover, our work also demonstrates the possibility of cognitive system development in autonomous intelligent agents.

Network dynamics of social influence in the wisdom of crowds

A longstanding problem in the social, biological, and computational sciences is to determine how groups of distributed individuals can form intelligent collective judgments. Since Galton's discovery of the "wisdom of crowds" [Galton F (1907) Nature 75:450-451], theories of collective intelligence have suggested that the accuracy of group judgments requires individuals to be either independent, with uncorrelated beliefs, or diverse, with negatively correlated beliefs [Page S (2008) The Difference: How the Power of Diversity Creates Better Groups, Firms, Schools, and Societies]. Previous experimental studies have supported this view by arguing that social influence undermines the wisdom of crowds. These results showed that individuals' estimates became more similar when subjects observed each other's beliefs, thereby reducing diversity without a corresponding increase in group accuracy [Lorenz J, Rauhut H, Schweitzer F, Helbing D (2011) Proc Natl Acad Sci USA 108:9020-9025]. By contrast, we show general network conditions under which social influence improves the accuracy of group estimates, even as individual beliefs become more similar. We present theoretical predictions and experimental results showing that, in decentralized communication networks, group estimates become reliably more accurate as a result of information exchange. We further show that the dynamics of group accuracy change with network structure. In centralized networks, where the influence of central individuals dominates the collective estimation process, group estimates become more likely to increase in error.

Effects of communication burstiness on consensus formation and tipping points in social dynamics

Current models for opinion dynamics typically utilize a Poisson process for speaker selection, making the waiting time between events exponentially distributed. Human interaction tends to be bursty though, having higher probabilities of either extremely short waiting times or long periods of silence. To quantify the burstiness effects on the dynamics of social models, we place in competition two groups exhibiting different speakers' waiting-time distributions. These competitions are implemented in the binary naming game and show that the relevant aspect of the waiting-time distribution is the density of the head rather than that of the tail. We show that even with identical mean waiting times, a group with a higher density of short waiting times is favored in competition over the other group. This effect remains in the presence of nodes holding a single opinion that never changes, as the fraction of such committed individuals necessary for achieving consensus decreases dramatically when they have a higher head density than the holders of the competing opinion. Finally, to quantify differences in burstiness, we introduce the expected number of small-time activations and use it to characterize the early-time regime of the system.

A boy named Sue

One major lesson learned in the cognitive sciences is that even basic human cognitive capacities are extraordinarily complicated and elusive to mechanistic explanations. This is definitely the case for naming and identity. Nothing seems simpler than using a proper name to refer to a unique individual object in the world. But psychological research has shown that the criteria and mechanisms by which humans establish and use names are unclear and seemingly contradictory. Children only develop the necessary knowledge and skills after years of development and naming degenerates in unusual selective ways with strokes, schizophrenia, or Alzheimer disease. Here we present an operational model of social interaction patterns and cognitive functions to explain how naming can be achieved and acquired. We study the Grounded Naming Game as a particular example of a symbolic interaction that requires naming and present mechanisms that build up and use the semiotic networks necessary for performance in the game. We demonstrate in experiments with autonomous physical robots that the proposed dynamical systems indeed lead to the formation of an effective naming system and that the model hence explains how naming and identity can get socially constructed and shared by a population of embodied agents.

The regularity game: Investigating linguistic rule dynamics in a population of interacting agents

Rules are an efficient feature of natural languages which allow speakers to use a finite set of instructions to generate a virtually infinite set of utterances. Yet, for many regular rules, there are irregular exceptions. There has been lively debate in cognitive science about how individual learners acquire rules and exceptions; for example, how they learn the past tense of preach is preached, but for teach it is taught. However, for most population or language-level models of language structure, particularly from the perspective of language evolution, the goal has generally been to examine how languages evolve stable structure, and neglects the fact that in many cases, languages exhibit exceptions to structural rules. We examine the dynamics of regularity and irregularity across a population of interacting agents to investigate how, for example, the irregular teach coexists beside the regular preach in a dynamic language system. Models show that in the absence of individual biases towards either regularity or irregularity, the outcome of a system is determined entirely by the initial condition. On the other hand, in the presence of individual biases, rule systems exhibit frequency dependent patterns in regularity reminiscent of patterns found in natural language. We implement individual biases towards regularity in two ways: through 'child' agents who have a preference to generalise using the regular form, and through a memory constraint wherein an agent can only remember an irregular form for a finite time period. We provide theoretical arguments for the prediction of a critical frequency below which irregularity cannot persist in terms of the duration of the finite time period which constrains agent memory. Further, within our framework we also find stable irregularity, arguably a feature of most natural languages not accounted for in many other cultural models of language structure.

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.

The influence of social status and network structure on consensus building in collaboration networks

In this paper, we analyze the influence of social status on opinion dynamics and consensus building in collaboration networks. To that end, we simulate the diffusion of opinions in empirical networks and take into account both the network structure and the individual differences of people reflected through their social status. For our simulations, we adapt a well-known Naming Game model and extend it with the Probabilistic Meeting Rule to account for the social status of individuals participating in a meeting. This mechanism is sufficiently flexible and allows us to model various society forms in collaboration networks, as well as the emergence or disappearance of social classes. In particular, we are interested in the way how these society forms facilitate opinion diffusion. Our experimental findings reveal that (i) opinion dynamics in collaboration networks is indeed affected by the individuals’ social status and (ii) this effect is intricate and non-obvious. Our results suggest that in most of the networks the social status favors consensus building. However, relying on it too strongly can also slow down the opinion diffusion, indicating that there is a specific setting for an optimal benefit of social status on the consensus building. On the other hand, in networks where status does not correlate with degree or in networks with a positive degree assortativity consensus is always reached quickly regardless of the status.

Analysis of the "naming game" with learning errors in communications

Naming game simulates the process of naming an objective by a population of agents organized in a certain communication network. By pair-wise iterative interactions, the population reaches consensus asymptotically. We study naming game with communication errors during pair-wise conversations, with error rates in a uniform probability distribution. First, a model of naming game with learning errors in communications (NGLE) is proposed. Then, a strategy for agents to prevent learning errors is suggested. To that end, three typical topologies of communication networks, namely random-graph, small-world and scale-free networks, are employed to investigate the effects of various learning errors. Simulation results on these models show that 1) learning errors slightly affect the convergence speed but distinctively increase the requirement for memory of each agent during lexicon propagation; 2) the maximum number of different words held by the population increases linearly as the error rate increases; 3) without applying any strategy to eliminate learning errors, there is a threshold of the learning errors which impairs the convergence. The new findings may help to better understand the role of learning errors in naming game as well as in human language development from a network science perspective.

Language as an emergent group-level trait

Following Smaldino's definition, we claim that language is also an emergent group-level trait, and propose two facets (human groups tend to organize in a way to efficiently trigger language and linguistic interactions can render formation of certain social organization) to verify this statement, both of which also provide a general framework to address the future work about group-level traits.

The spontaneous emergence of conventions: an experimental study of cultural evolution

How do shared conventions emerge in complex decentralized social systems? This question engages fields as diverse as linguistics, sociology, and cognitive science. Previous empirical attempts to solve this puzzle all presuppose that formal or informal institutions, such as incentives for global agreement, coordinated leadership, or aggregated information about the population, are needed to facilitate a solution. Evolutionary theories of social conventions, by contrast, hypothesize that such institutions are not necessary in order for social conventions to form. However, empirical tests of this hypothesis have been hindered by the difficulties of evaluating the real-time creation of new collective behaviors in large decentralized populations. Here, we present experimental results--replicated at several scales--that demonstrate the spontaneous creation of universally adopted social conventions and show how simple changes in a population's network structure can direct the dynamics of norm formation, driving human populations with no ambition for large scale coordination to rapidly evolve shared social conventions.

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.

Message spreading in networks with stickiness and persistence: large clustering does not always facilitate large-scale diffusion

Recent empirical studies have confirmed the key roles of complex contagion mechanisms such as memory, social reinforcement, and decay effects in information diffusion and behavior spreading. Inspired by this fact, we here propose a new agent–based model to capture the whole picture of the joint action of the three mechanisms in information spreading, by quantifying the complex contagion mechanisms as stickiness and persistence, and carry out extensive simulations of the model on various networks. By numerical simulations as well as theoretical analysis, we find that the stickiness of the message determines the critical dynamics of message diffusion on tree-like networks, whereas the persistence plays a decisive role on dense regular lattices. In either network, the greater persistence can effectively make the message more invasive. Of particular interest is that our research results renew our previous knowledge that messages can spread broader in networks with large clustering, which turns out to be only true when they can inform a non-zero fraction of the population in the limit of large system size.

The Matthew effect in empirical data

The Matthew effect describes the phenomenon that in societies, the rich tend to get richer and the potent even more powerful. It is closely related to the concept of preferential attachment in network science, where the more connected nodes are destined to acquire many more links in the future than the auxiliary nodes. Cumulative advantage and success-breads-success also both describe the fact that advantage tends to beget further advantage. The concept is behind the many power laws and scaling behaviour in empirical data, and it is at the heart of self-organization across social and natural sciences. Here, we review the methodology for measuring preferential attachment in empirical data, as well as the observations of the Matthew effect in patterns of scientific collaboration, socio-technical and biological networks, the propagation of citations, the emergence of scientific progress and impact, career longevity, the evolution of common English words and phrases, as well as in education and brain development. We also discuss whether the Matthew effect is due to chance or optimization, for example related to homophily in social systems or efficacy in technological systems, and we outline possible directions for future research.

Naming game on networks: let everyone be both speaker and hearer

To investigate how consensus is reached on a large self-organized peer-to-peer network, we extended the naming game model commonly used in language and communication to Naming Game in Groups (NGG). Differing from other existing naming game models, in NGG everyone in the population (network) can be both speaker and hearer simultaneously, which resembles in a closer manner to real-life scenarios. Moreover, NGG allows the transmission (communication) of multiple words (opinions) for multiple intra-group consensuses. The communications among indirectly-connected nodes are also enabled in NGG. We simulated and analyzed the consensus process in some typical network topologies, including random-graph networks, small-world networks and scale-free networks, to better understand how global convergence (consensus) could be reached on one common word. The results are interpreted on group negotiation of a peer-to-peer network, which shows that global consensus in the population can be reached more rapidly when more opinions are permitted within each group or when the negotiating groups in the population are larger in size. The novel features and properties introduced by our model have demonstrated its applicability in better investigating general consensus problems on peer-to-peer networks.

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.

Exploring the effect of power law social popularity on language evolution

We evaluate the effect of a power-law-distributed social popularity on the origin and change of language, based on three artificial life models meticulously tracing the evolution of linguistic conventions including lexical items, categories, and simple syntax. A cross-model analysis reveals an optimal social popularity, in which the λ value of the power law distribution is around 1.0. Under this scaling, linguistic conventions can efficiently emerge and widely diffuse among individuals, thus maintaining a useful level of mutual understandability even in a big population. From an evolutionary perspective, we regard this social optimality as a tradeoff among social scaling, mutual understandability, and population growth. Empirical evidence confirms that such optimal power laws exist in many large-scale social systems that are constructed primarily via language-related interactions. This study contributes to the empirical explorations and theoretical discussions of the evolutionary relations between ubiquitous power laws in social systems and relevant individual behaviors.

Language change in a multiple group society

The processes leading to change in languages are manifold. In order to reduce ambiguity in the transmission of information, agreement on a set of conventions for recurring problems is favored. In addition to that, speakers tend to use particular linguistic variants associated with the social groups they identify with. The influence of other groups propagating across the speech community as new variant forms sustains the competition between linguistic variants. With the utterance selection model, an evolutionary description of language change, Baxter et al. [Phys. Rev. E 73, 046118 (2006)] have provided a mathematical formulation of the interactions inside a group of speakers, exploring the mechanisms that lead to or inhibit the fixation of linguistic variants. In this paper, we take the utterance selection model one step further by describing a speech community consisting of multiple interacting groups. Tuning the interaction strength between groups allows us to gain deeper understanding about the way in which linguistic variants propagate and how their distribution depends on the group partitioning. Both for the group size and the number of groups we find scaling behaviors with two asymptotic regimes. If groups are strongly connected, the dynamics is that of the standard utterance selection model, whereas if their coupling is weak, the magnitude of the latter along with the system size governs the way consensus is reached. Furthermore, we find that a high influence of the interlocutor on a speaker's utterances can act as a counterweight to group segregation.

Information sharing and sorting in a community

We present the results of a detailed numerical study of a model for the sharing and sorting of information in a community consisting of a large number of agents. The information gathering takes place in a sequence of mutual bipartite interactions where randomly selected pairs of agents communicate with each other to enhance their knowledge and sort out the common information. Although our model is less restricted compared to the well-established naming game, the numerical results strongly indicate that the whole set of exponents characterizing this model are different from those of the naming game and they assume nontrivial values. Finally, it appears that in analogy to the emergence of clusters in the phenomenon of percolation, one can define clusters of agents here having the same information. We have studied in detail the growth of the largest cluster in this article and performed its finite-size scaling analysis.

Agent-based models of strategies for the emergence and evolution of grammatical agreement

Grammatical agreement means that features associated with one linguistic unit (for example number or gender) become associated with another unit and then possibly overtly expressed, typically with morphological markers. It is one of the key mechanisms used in many languages to show that certain linguistic units within an utterance grammatically depend on each other. Agreement systems are puzzling because they can be highly complex in terms of what features they use and how they are expressed. Moreover, agreement systems have undergone considerable change in the historical evolution of languages. This article presents language game models with populations of agents in order to find out for what reasons and by what cultural processes and cognitive strategies agreement systems arise. It demonstrates that agreement systems are motivated by the need to minimize combinatorial search and semantic ambiguity, and it shows, for the first time, that once a population of agents adopts a strategy to invent, acquire and coordinate meaningful markers through social learning, linguistic self-organization leads to the spontaneous emergence and cultural transmission of an agreement system. The article also demonstrates how attested grammaticalization phenomena, such as phonetic reduction and conventionalized use of agreement markers, happens as a side effect of additional economizing principles, in particular minimization of articulatory effort and reduction of the marker inventory. More generally, the article illustrates a novel approach for studying how key features of human languages might emerge.

Analytic treatment of tipping points for social consensus in large random networks

We introduce a homogeneous pair approximation to the naming game (NG) model by deriving a six-dimensional Open Dynamics Engine (ODE) for the two-word naming game. Our ODE reveals the change in dynamical behavior of the naming game as a function of the average degree {k} of an uncorrelated network. This result is in good agreement with the numerical results. We also analyze the extended NG model that allows for presence of committed nodes and show that there is a shift of the tipping point for social consensus in sparse networks.

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.

Slow dynamics and rare-region effects in the contact process on weighted tree networks

We show that generic, slow dynamics can occur in the contact process on complex networks with a tree-like structure and a superimposed weight pattern, in the absence of additional (nontopological) sources of quenched disorder. The slow dynamics is induced by rare-region effects occurring on correlated subspaces of vertices connected by large weight edges and manifests in the form of a smeared phase transition. We conjecture that more sophisticated network motifs could be able to induce Griffiths phases, as a consequence of purely topological disorder.

Naming game on adaptive weighted networks

We examine a naming game on an adaptive weighted network. A weight of connection for a given pair of agents depends on their communication success rate and determines the probability with which the agents communicate. In some cases, depending on the parameters of the model, the preference toward successfully communicating agents is essentially negligible and the model behaves similarly to the naming game on a complete graph. In particular, it quickly reaches a single-language state, albeit some details of the dynamics are different from the complete-graph version. In some other cases, the preference toward successfully communicating agents becomes much more important and the model gets trapped in a multi-language regime. In this case gradual coarsening and extinction of languages lead to the emergence of a dominant language, albeit with some other languages still present. A comparison of distribution of languages in our model and in the human population is discussed.

Evolution of opinions on social networks in the presence of competing committed groups

Public opinion is often affected by the presence of committed groups of individuals dedicated to competing points of view. Using a model of pairwise social influence, we study how the presence of such groups within social networks affects the outcome and the speed of evolution of the overall opinion on the network. Earlier work indicated that a single committed group within a dense social network can cause the entire network to quickly adopt the group's opinion (in times scaling logarithmically with the network size), so long as the committed group constitutes more than about of the population (with the findings being qualitatively similar for sparse networks as well). Here we study the more general case of opinion evolution when two groups committed to distinct, competing opinions and , and constituting fractions and of the total population respectively, are present in the network. We show for stylized social networks (including Erdös-Rényi random graphs and Barabási-Albert scale-free networks) that the phase diagram of this system in parameter space consists of two regions, one where two stable steady-states coexist, and the remaining where only a single stable steady-state exists. These two regions are separated by two fold-bifurcation (spinodal) lines which meet tangentially and terminate at a cusp (critical point). We provide further insights to the phase diagram and to the nature of the underlying phase transitions by investigating the model on infinite (mean-field limit), finite complete graphs and finite sparse networks. For the latter case, we also derive the scaling exponent associated with the exponential growth of switching times as a function of the distance from the critical point.

Studying language change using price equation and Pólya-urn dynamics

Language change takes place primarily via diffusion of linguistic variants in a population of individuals. Identifying selective pressures on this process is important not only to construe and predict changes, but also to inform theories of evolutionary dynamics of socio-cultural factors. In this paper, we advocate the Price equation from evolutionary biology and the Pólya-urn dynamics from contagion studies as efficient ways to discover selective pressures. Using the Price equation to process the simulation results of a computer model that follows the Pólya-urn dynamics, we analyze theoretically a variety of factors that could affect language change, including variant prestige, transmission error, individual influence and preference, and social structure. Among these factors, variant prestige is identified as the sole selective pressure, whereas others help modulate the degree of diffusion only if variant prestige is involved. This multidisciplinary study discerns the primary and complementary roles of linguistic, individual learning, and socio-cultural factors in language change, and offers insight into empirical studies of language change.

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.

Modeling the cultural evolution of language

The paper surveys recent research on language evolution, focusing in particular on models of cultural evolution and how they are being developed and tested using agent-based computational simulations and robotic experiments. The key challenges for evolutionary theories of language are outlined and some example results are discussed, highlighting models explaining how linguistic conventions get shared, how conceptual frameworks get coordinated through language, and how hierarchical structure could emerge. The main conclusion of the paper is that cultural evolution is a much more powerful process that usually assumed, implying that less innate structures or biases are required and consequently that human language evolution has to rely less on genetic evolution.

Exploring the roles of complex networks in linguistic categorization

This article adopts the category game model, which simulates the origins and evolution of linguistic categories in a group of artificial agents, to evaluate the effect of social structure on linguistic categorization. Based on the simulation results in a number of typical networks, we examine the isolating and collective effects of some structural features, including average degree, shortcuts, and level of centrality, on the categorization process. This study extends the previous simulations mainly on lexical evolution, and illustrates a general framework to systematically explore the effect of social structure on language evolution.

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.