Language Evolution and Computation Bibliography

We investigate the dynamics of a broad class of stochastic copying processes on a network that includes examples from population genetics (spatially structured Wright-Fisher models), ecology (Hubbell-type models), linguistics (the utterance selection model), and opinion dynamics (the voter model) as special cases. These models all have absorbing states of fixation where all the nodes are in the same state. Earlier studies of these models showed that the mean time when this occurs can be made to grow as different powers of the network size by varying the degree distribution of the network. Here we demonstrate that this effect can also arise if one varies the asymmetry of the copying dynamics while holding the degree distribution constant. In particular, we show that the mean time to fixation can be accelerated even on homogeneous networks when certain nodes are very much more likely to be copied from than copied to. We further show that there is a complex interplay between degree distribution and asymmetry when they may covary, and that the results are robust to correlations in the network or the initial condition.

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.

Zipf’s law seems to be ubiquitous in human languages and appears to be a universal property of complex communicating systems. Following the early proposal made by Zipf concerning the presence of a tension between the efforts of speaker and hearer in a communication system, we introduce evolution by means of a variational approach to the problem based on Kullback’s Minimum Discrimination of Information Principle. Therefore, using a formalism fully embedded in the framework of information theory, we demonstrate that Zipf’s law is the only expected outcome of an evolving communicative system under a rigorous definition of the communicative tension described by Zipf.

The naming game (NG)[1, 2] describes a population of agents playing pairwise interactions in order to negotiate conventions. Following Wittgenstein's intuition on language [3], the negotiation is seen as an activity in which one of the individuals (ie, the “speaker”) tries to ...

We examine a naming game with two agents trying to establish a common vocabulary for n objects. Such efforts lead to the emergence of language that allows for an efficient communication and exhibits some degree of homonymy and synonymy. Although homonymy reduces the communication efficiency, it seems to be a dynamical trap that persists for a long, and perhaps indefinite, time. On the other hand, synonymy does not reduce the efficiency of communication, but appears to be only a transient feature of the language. Thus, in our model the role of synonymy decreases and in the long-time limit it becomes negligible. A similar rareness of synonymy is observed in present natural languages. The role of noise, that distorts the communicated words, is also examined. Although, in general, the noise reduces the communication efficiency, it also regroups the words so that they are more evenly distributed within the available ``verbal'' space.

We propose an asymmetric negotiation strategy to investigate the influence of high-degree agents on the agreement dynamics in a structured language game, the naming game. We introduce a model parameter, which governs the frequency of high-degree agents acting as speakers in communication. It is found that there exists an optimal value of the parameter that induces the fastest convergence to a global consensus on naming an object for both scale-free and small-world naming games. This phenomenon indicates that, although a strong influence of high-degree agents favors consensus achievement, very strong influences inhibit the convergence process, making it even slower than in the absence of influence of high-degree agents. Investigation of the total memory used by agents implies that there is some trade-off between the convergence speed and the required total memory. Other quantities, including the evolution of the number of different names and the relationship between agents' memories and their degrees, are also studied. The results are helpful for better understanding of the dynamics of the naming game with asymmetric negotiation strategy.

We investigate a prototypical agent-based model, the naming game, on two-dimensional random geometric networks. The naming game {[}Baronchelli , 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.

A simple model of language evolution proposed by Komarova, Niyogi, and Nowak is characterized by a payoff in communicative function and by an error in learning that measure the accuracy in language acquisition. The time scale for language change is generational, and the model's equations in the mean-field approximation are a particular case of the replicator-mutator equations of evolutionary dynamics. In well-mixed populations, this model exhibits a critical coherence threshold; i.e., a minimal accuracy in the learning process is required to maintain linguistic coherence. In this work, we analyze in detail the effects of different fitness-based dynamics driving linguistic coherence and of the network of interactions on the nature of the coherence threshold by performing numerical simulations and theoretical analyses of three different models of language change in finite populations with two types of structure: fully connected networks and regular random graphs. We find that although the threshold of the original replicator-mutator evolutionary model is robust with respect to the structure of the network of contacts, the coherence threshold of related fitness-driven models may be strongly affected by this feature.

We investigate the coevolutionary dynamics of opinions and networks based upon majority-preference (MP) and minority-avoidance (MA) rules. Under MP, individuals adopt the majority opinion among their neighbors; while in MA individuals can break the link to one holding a minority and different opinion, and rewire either to neighbors of their neighbors with the same opinion or to a random one from the whole population except their nearest neighbors. We study opinion formation as a result of combination of these two competing rules, with a parameter tuning the balance between them. We find that the underlying network can be self-organized into connected communities with like-minded individuals belonging to the same group; thus a broad variety of opinions coexist. Diverse opinions disappear in a population in which all individuals share a uniform opinion, when the model parameter exceeds a critical value. Furthermore, we show that an increasing tendency to redirect to neighbors of neighbors is more likely to result in a consensus of opinion.

We study a modified version of the naming game, a recently introduced model which describes how shared vocabulary can emerge spontaneously in a population without any central control. In particular, we introduce a mechanism that allows a continuous interchange with the external inventory of words. A playing strategy, influenced by the hierarchical structure that individuals' reputation defines in the community, is implemented. We analyze how these features influence the convergence times, the cognitive efforts of the agents, and the scaling behavior in memory and time.

We present a modified naming game by introducing weights of words in the evolution process. We assign the weight of a word spoken by an agent according to its connectivity, which is a natural reflection of the agent's influence in population. A tunable parameter is introduced, governing the word weight based on the connectivity of agents. We consider the scale-free topology and concentrate on the efficiency of reaching the final consensus, which is of high importance in the self-organized system. Interestingly, it is found that there exists an optimal parameter value, leading to the fastest convergence. This indicates appropriate hub's effects favor the achievement of consensus. The evolution of distinct words helps to give a qualitative explanation of this phenomena. Similar nontrivial phenomena are observed in the total memory of agents with a peak in the middle range of parameter values. Other relevant characters are provided as well, including the time evolution of total memory and success rate for different parameter values as well as the average degree of the network, which are helpful for understanding the dynamics of the modified naming game in detail.

We present a mathematical formulation of a theory of language change. The theory is evolutionary in nature and has close analogies with theories of population genetics. The mathematical structure we construct similarly has correspondences with the Fisher-Wright model of population genetics, but there are significant differences. The continuous time formulation of the model is expressed in terms of a Fokker-Planck equation. This equation is exactly soluble in the case of a single speaker and can be investigated analytically in the case of multiple speakers who communicate equally with all other speakers and give their utterances equal weight. Whilst the stationary properties of this system have much in common with the single-speaker case, time-dependent properties are richer. In the particular case where linguistic forms can become extinct, we find that the presence of many speakers causes a two-stage relaxation, the first being a common marginal distribution that persists for a long time as a consequence of ultimate extinction being due to rare fluctuations.

The Naming Game is a model of non-equilibrium dynamics for the self-organized emergence of a linguistic convention or a communication system in a population of agents with pairwise local interactions. We present an extensive study of its dynamics on complex networks, that can be considered as the most natural topological embedding for agents involved in language games and opinion dynamics. Except for some community structured networks on which metastable phases can be observed, agents playing the Naming Game always manage to reach a global consensus. This convergence is obtained after a time generically scaling with the population's size $N$ as $t\_{conv} \sim N^{1.4 \pm 0.1}$, i.e. much faster than for agents embedded on regular lattices. Moreover, the memory capacity required by the system scales only linearly with its size. Particular attention is given to heterogenous networks, in which the dynamical activity pattern of a node depends on its degree. High degree nodes have a fundamental role, but require larger memory capacity. They govern the dynamics acting as spreaders of (linguistic) conventions. The effects of other properties, such as the average degree and the clustering, are also discussed.

We investigate how very large populations are able to reach a global consensus, out of local ``microscopic'' interaction rules, in the framework of a recently introduced class of models of semiotic dynamics, the so-called Naming Game. We compare in particular the convergence mechanism for interacting agents embedded in a low-dimensional lattice with respect to the mean-field case. We highlight that in low-dimensions consensus is reached through a coarsening process which requires less cognitive effort of the agents, with respect to the mean-field case, but takes longer to complete. In 1-d the dynamics of the boundaries is mapped onto a truncated Markov process from which we analytically computed the diffusion coefficient. More generally we show that the convergence process requires a memory per agent scaling as N and lasts a time N^{1+2/d} in dimension d<5 (d=4 being the upper critical dimension), while in mean-field both memory and time scale as N^{3/2}, for a population of N agents. We present analytical and numerical evidences supporting this picture.

Many languages are spoken on Earth. Despite their diversity, many robust language universals are known to exist. All languages share syntax, i.e., the ability of combining words for forming sentences. The origin of such traits is an issue of open debate. By using recent developments from the statistical physics of complex networks, we show that different syntactic dependency networks (from Czech, German, and Romanian) share many nontrivial statistical patterns such as the small world phenomenon, scaling in the distribution of degrees, and disassortative mixing. Such previously unreported features of syntax organization are not a trivial consequence of the structure of sentences, but an emergent trait at the global scale.

We study the Euclidean distance between syntactically linked words in sentences. The average distance is significantly small and is a very slowly growing function of sentence length. We consider two nonexcluding hypotheses: (a) the average distance is minimized and (b) the average distance is constrained. Support for (a) comes from the significantly small average distance real sentences achieve. The strength of the minimization hypothesis decreases with the length of the sentence. Support for (b) comes from the very slow growth of the average distance versus sentence length. Furthermore, (b) predicts, under ideal conditions, an exponential distribution of the distance between linked words, a trend that can be identified in real sentences.

Zipf's law asserts that in all natural languages the frequency of a word is inversely proportional to its rank. The significance, if any, of this result for language remains a mystery. Here we examine a null hypothesis for the distribution of word frequencies, a so-called discourse-triggered word choice model, which is based on the assumption that the more a word is used, the more likely it is to be used again. We argue that this model is equivalent to the neutral infinite-alleles model of population genetics and so the degeneracy of the different words composing a sample of text is given by the celebrated Ewens sampling formula [

Theor. Pop. Biol. 3, 87 (1972)

], which we show to produce an exponential distribution of word frequencies.

We define two words in a language to be connected if they express similar concepts. The network of connections among the many thousands of words that make up a language is important not only for the study of the structure and evolution of languages, but also for cognitive science. We study this issue quantitatively, by mapping out the conceptual network of the English language, with the connections being defined by the entries in a Thesaurus dictionary. We find that this network presents a small-world structure, with an amazingly small average shortest path, and appears to exhibit an asymptotic scale-free feature with algebraic connectivity distribution.