MENU

Prof. Vittorio Loreto

Director

language creativity

My research activity is focused on complexity science and its interdisciplinary applications. Along the past years I have been active in several fields from granular media, to complexity and information theory, from social dynamics to sustainabilty. My very recent KREYON project (www.kreyon.net) concerned “Unfolding the dynamics of creativity, novelties and innovation”. In this context I am interested in understanding and modelling how the “new” enters our lives in its multiform instantiations: personal novelties or global innovation. To this end I’m blending, in a unitary interdisciplinary effort, three main activities: web-based experiments, data science and theoretical modeling.
Key to this endeavor is to grasp the structure and the dynamics of the “space of possibilities” in order to come up with a solid mathematical modelling of the way systems – biological, technological, social – explore the new at the individual and collective levels. Exploiting the knowledge of the way the space of possibilities is explored can be helpful to conceive the next generation of Artificial Intelligent algorithms able to cope with the occurrence of novelties, bridging in this way the gap between inference and unanticipated events.

A quantitative and operational definition of what is new is...
read more
Kreyon City is a unique experience whose challenge is that...
read more
The Citychrone platform (www.citychrone.org), originally developed by Sapienza University of...
read more
Despite the recent dramatic boost of inference methods, artificial intelligent...
read more
The rise of Information Age is transforming our world and,...
read more
Anticipation processes concerns all cases in which the next occurrence...
read more
A key research target is the direct individuation of the...
read more
Creativity is more and more recognized as the main driver...
read more
Language dynamics is a rapidly growing field that focuses on...
read more
2019

Subjectivity and complexity of facial attractiveness

Topics:
creativity
Authors
Ibáñez-Berganza Miguel , Amico Ambra , Vittorio Loreto |

Scientific Reports, 9, 1, 2019. pp.8364.

read more

Abstract

The origin and meaning of facial beauty represent a longstanding puzzle. Despite the profuse literature devoted to facial attractiveness, its very nature, its determinants and the nature of inter-person differences remain controversial issues. Here we tackle such questions proposing a novel experimental approach in which human subjects, instead of rating natural faces, are allowed to efficiently explore the face-space and “sculpt” their favorite variation of a reference facial image. The results reveal that different subjects prefer distinguishable regions of the face-space, highlighting the essential subjectivity of the phenomenon. The different sculpted facial vectors exhibit strong correlations among pairs of facial distances, characterising the underlying universality and complexity of the cognitive processes, and the relative relevance and robustness of the different facial distances.

2019

Universal scores for accessibility and inequalities in urban areas

Topics:
creativity
Authors
Biazzo Indaco , Bernardo Monechi , Vittorio Loreto |

in press in Journal of The Royal Society Interface, 2019.

2019

The exploration of the Adjacent Possible explains the emergence and evolution of social networks

Topics:
creativity
Authors
Enrico Ubaldi , Burioni Raffaella , Vittorio Loreto , Tria Francesca |

Submitted for publication, 2019.

2018

Zipf’s, Heaps’ and Taylor’s laws are determined by the expansion into the adjacent possible

Topics:
creativity
Authors
Tria Francesca , Vittorio Loreto , Servedio Vito D. P. |

Entropy, 20, 10, 2018.

read more

Abstract

Zipf's, Heaps' and Taylor's laws are ubiquitous in many different systems where innovation processes are at play. Together, they represent a compelling set of stylized facts regarding the overall statistics, the innovation rate and the scaling of fluctuations for systems as diverse as written texts and cities, ecological systems and stock markets. Many modeling schemes have been proposed in literature to explain those laws, but only recently a modeling framework has been introduced that accounts for the emergence of those laws without deducing the emergence of one of the laws from the others or without ad hoc assumptions. This modeling framework is based on the concept of adjacent possible space and its key feature of being dynamically restructured while its boundaries get explored, i.e., conditional to the occurrence of novel events. Here, we illustrate this approach and show how this simple modeling framework, instantiated through a modified Pólya’s urn model, is able to reproduce Zipf's, Heaps' and Taylor's laws within a unique self-consistent scheme. In addition, the same modeling scheme embraces other less common evolutionary laws (Hoppe's model and Dirichlet processes) as particular cases.
2017

Where Creativity and Innovation are Much Needed Fuelss

Topics:
creativity
Authors
Vittorio Loreto |

43 Visions for Complexity, edited by:Thurner, Stefan, World Scientific, 2017.

2017

Significance and popularity in music production

Topics:
creativity music
Authors
Bernardo Monechi , Pietro Gravino , Servedio Vito D. P. , Tria Francesca , Vittorio Loreto |

Royal Society Open Science, 4, 7, The Royal Society, 2017.

read more

Abstract

Creative industries constantly strive for fame and popularity. Though highly desirable, popularity is not the only achievement artistic creations might ever acquire. Leaving a longstanding mark in the global production and influencing future works is an even more important achievement, usually acknowledged by experts and scholars. ‘Significant’ or ‘influential’ works are not always well known to the public or have sometimes been long forgotten by the vast majority. In this paper, we focus on the duality between what is successful and what is significant in the musical context. To this end, we consider a user-generated set of tags collected through an online music platform, whose evolving co-occurrence network mirrors the growing conceptual space underlying music production. We define a set of general metrics aiming at characterizing music albums throughout history, and their relationships with the overall musical production. We show how these metrics allow to classify albums according to their current popularity or their belonging to expert-made lists of important albums. In this way, we provide the scientific community and the public at large with quantitative tools to tell apart popular albums from culturally or aesthetically relevant artworks. The generality of the methodology presented here lends itself to be used in all those fields where innovation and creativity are in play.

2017

Maximum entropy models capture melodic styles

Topics:
creativity music
Authors
Sakellariou Jason , Tria Francesca , Vittorio Loreto , François Pachet |

Scientific Reports, 7, 1, Nature Publishing Group, 2017. pp.9172.

read more

Abstract

We introduce a Maximum Entropy model able to capture the statistics of melodies in music. The model can be used to generate new melodies that emulate the style of a given musical corpus. Instead of using the n–body interactions of (n−1)–order Markov models, traditionally used in automatic music generation, we use a k-nearest neighbour model with pairwise interactions only. In that way, we keep the number of parameters low and avoid over-fitting problems typical of Markov models. We show that long-range musical phrases don’t need to be explicitly enforced using high-order Markov interactions, but can instead emerge from multiple, competing, pairwise interactions. We validate our Maximum Entropy model by contrasting how much the generated sequences capture the style of the original corpus without plagiarizing it. To this end we use a data-compression approach to discriminate the levels of borrowing and innovation featured by the artificial sequences. Our modelling scheme outperforms both fixed-order and variable-order Markov models. This shows that, despite being based only on pairwise interactions, our scheme opens the possibility to generate musically sensible alterations of the original phrases, providing a way to generate innovation.

2017

Copystree: gaming artificial phylogenies

Topics:
language
Authors
Simone Pompei , Vittorio Loreto , Francesca Tria |

Language Dynamics and Change, 2017.

read more

Abstract

The reconstruction of phylogenies of cultural artefacts represents an open problem that mixes theoretical and computational challenges. Existing bench- marks rely on simulated phylogenies, where hypotheses on the underlying evolutionary mechanisms are unavoidable, or in real data phylogenies, for which no true evolutionary history is known. Here we introduce a web-based game, Copystree, where users create phylogenies of manuscripts, through successive copying actions, in a fully monitored setup. While players enjoy the experience, Copystree allows to build artificial phylogenies whose evolutionary processes do not obey to any pre-defined theoretical mechanisms, being generated instead with the unpredictability of human creativity. We present the analysis of the data gathered during the first set of experiments and use the artificial phylogenies gathered for a first test of existing phylogenetic algorithms.

2017

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

Topics:
language
Authors
Christine Cuskley , Claudio Castellano , Francesca Colaiori , Vittorio Loreto , Martina Pugliese , Francesca Tria |

Cognition, 159, Elsevier, 2017. pp.25--32.

read more

Abstract

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.

2016

On the Emergence of Syntactic Structures: Quantifying and Modeling Duality of Patterning

Topics:
language
Authors
Vittorio Loreto , Pietro Gravino , Vito DP Servedio , Francesca Tria |

Topics in cognitive science, 8, 2, Wiley Online Library, 2016. pp.469--480.

read more

Abstract

The complex organization of syntax in hierarchical structures is one of the core design features of human language. Duality of patterning refers for instance to the organization of the meaningful elements in a language at two distinct levels: a combinatorial level where meaningless forms are combined into meaningful forms and a compositional level where meaningful forms are composed into larger lexical units. The question remains wide open regarding how such a structure could have emerged. Furthermore a clear mathematical framework to quantify this phenomenon is still lacking. The aim of this paper is that of addressing these two aspects in a self-consistent way. First, we introduce suitable measures to quantify the level of combinatoriality and compositionality in a language, and present a framework to estimate these observables in human natural languages. Second, we show that the theoretical predictions of a multi-agents modeling scheme, namely the Blending Game, are in surprisingly good agreement with empirical data. In the Blending Game a population of individuals plays language games aiming at success in communication. It is remarkable that the two sides of duality of patterning emerge simultaneously as a consequence of a pure cultural dynamics in a simulated environment that contains meaningful relations, provided a simple constraint on message transmission fidelity is also considered.

2016

Individual Mobility Patterns in Urban Environment

Topics:
creativity
Authors
Pierpaolo Mastroianni , Bernardo Monechi , Vito DP Servedio , Carlo Liberto , Gaetano Valenti , Vittorio Loreto |

e COMPLEXIS 2016, 1st International Conference on Complex Information Systems, Rome, 22-24 April 2016, 2016.

read more

Abstract

The understanding and the characterisation of individual mobility patterns in urban environments is important in order to improve liveability and planning of big cities. In relatively recent times, the availability of data regarding human movements have fostered the emergence of a new branch of social studies, with the aim to unveil and study those patterns thanks to data collected by means of geolocalisation technologies. In this paper we analyse a large dataset of GPS tracks of cars collected in Rome (Italy). Dividing the drivers in classes according to the number of trips they perform in a day, we show that the sequence of the travelled space connecting two consecutive stops shows a precise behaviour so that the shortest trips are performed at the middle of the sequence, when the longest occur at the beginning and at the end when drivers head back home. We show that this behaviour is consistent with the idea of an optimisation process in which the total travel time is minimised, under the effect of spatial constraints so that the starting points is on the border of the space in which the dynamics takes place.

2016

Exploring the evolution of pathogens organised in discrete antigenic clusters

Topics:
creativity
Authors
Martina Pugliese , Vittorio Loreto , Simone Pompei , Francesca Tria |

Journal of Statistical Mechanics: Theory and Experiment, 2016, 9, IOP Publishing, 2016. pp.093306.

read more

Abstract

We present a numerical model for the evolution of pathogens organised in discrete antigenic clusters, where individuals in the same clusters have the same fitness. The fitness of each cluster is a decreasing function of the total number of cluster members appeared in the population. Cluster transition is modelled with inclusion and exclusion of dynamical epistatic effects. In both cases we observe a continuous transition, driven by the mutation rate, from a dynamics with single clusters alternating in time to the coexistence of many clusters in the population. The transition between the two regimes is investigated in terms of the key parameters of the model. We find that the location and the scaling of this transition can be explained in terms of the time of first appearance of a new cluster in the population. The presence of dynamical epistatic effects results in a shift of the value of the mutation rate where the transition occurs.

2016

Crossing the horizon: exploring the adjacent possible in a cultural system

Topics:
creativity
Authors
Pietro Gravino , Bernardo Monechi , Vito DP Servedio , Francesca Tria , Vittorio Loreto |

submitted to "ICCC 2016 - The Seventh International Conference on Computational Creativity", Proceedings of the Seventh International Conference on Computational Creativity, June 2016, 2016.

read more

Abstract

It is common opinion that many innovations are triggered by serendipity whose notion is associated with fortuitous events leading to unintended consequences. One might argue that this interpretation is due to the poor understanding of the dynamics of innovations. Very little is known, in fact, about how innovations proceed and samples the space of potential novelties. This space is usually referred to as the adjacent possible, a concept originally introduced in the study of biological systems to indicate the set of possibilities that are one step away from what actually exists. In this paper we focus on the problem of defining the adjacent possible space, and analyzing its dynamics, for a particular system, namely the cultural system of the network of movies. We synthesized to this end the graph emerging from the Internet Movies Database (IMDb) and looked at the static and dynamical properties of this network. We deal, in particular, with the subtle mechanism of the adjacent possible by measuring the expansion and the coverage of this elusive space during the global evolution of the system. Finally, we introduce the concept of adjacent possibilities at the level of single node and try to elucidate its nature by looking at the correlations with topological and user annotation metrics.

2016

Unveiling political opinion structures with a web-experiment

Topics:
creativity
Authors
Pietro Gravino , Saverio Caminiti , Alina Sirbu , Francesca Tria , Vito D. P. Servedio , Vittorio Loreto |

COMPLEXIS 2016, 1st International Conference on Complex Information Systems, Rome, 22-24 April 2016, 2016.

read more

Abstract

The dynamics of political votes has been widely studied, both for its practical interest and as a paradigm of the dynamics of mass opinions and collective phenomena, where theoretical predictions can be easily tested. However, the vote outcome is often influenced by many factors beyond the bare opinion on the candidate, and in most cases it is bound to a single preference. The voter perception of the political space is still to be elucidated. We here propose a web experiment (laPENSOcos’i) where we explicitly investigate participant’s opinions on political entities (parties, coalitions, individual candidates) of the Italian political scene. As a main result, we show that the political perception follows a Weber-Fechner-like law, i.e., when ranking political entities according to the user expressed preferences, the perceived distance of the user from a given entity scales as the logarithm of this rank.

2016

Waves of Novelties in the Expansion into the Adjacent Possible

Topics:
creativity
Authors
Bernardo Monechi , Alvaro Ruiz-Serrano , Francesca Tria , Vittorio Loreto |

PloS ONE, edited by:Public Library of Science, 12, 6, 2016. pp.e0179303.

read more

Abstract

The emergence of novelties and their rise and fall in popularity is an ubiquitous phenomenon in human activities. The coexistence of always popular milestones with novel and sometimes ephemeral trends pervades technological, scientific and artistic production. By introducing suitable statistical measures, we demonstrate that different systems of human activities, i.e. the creation of hashtags in Twitter, the interaction with online program code repositories, the creation of texts and the listening of songs on an on-line platform, exhibit surprisingly similar properties.We then introduce a general framework to explain those regularities. We propose a simple mathematical model based on the expansion into the adjacent possible, that has been proven to be a very general and powerful mechanism able to explain many of the statistical patterns emerging in innovation dynamics, to which we add two crucial elements. On the one hand we quantify the idea that, while exploring a conceptual or physical space, inertia exists towards known already discovered elements. On the other hand, we highlight the role of the collective dynamics – where many users interact, in a direct or indirect way in the emergence and diffusion of novelties and innovations.

2016

The Emergence Of Rules And Exceptions In A Population Of Interacting Agents

Topics:
language
Authors
Christine Cuskley , Vittorio Loreto |

The Evolution of Language: Proceedings of the 11th International Conference (EVOLANGX11), edited by:S.G. Roberts and C. Cuskley and L. McCrohon and L. Barcel'o-Coblijn and O. Fehér and T. Verhoef, 2016.

read more

Abstract

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. In this paper, we take a different perspective, examining the dynamics of regularity and irregularity across a population of interacting agents to investigate how inflectional rules are applied to verbs. We show that in the absence of biases towards either regularity or irregularity, the outcome is determined by the initial condition, irrespective of the frequency of usage of the given lemma. On the other hand, in presence of biases, rule systems exhibit frequency dependent patterns in regularity reminiscent of patterns in natural language corpora. We examine the case where individuals are biased towards linguistic regularity in two ways: either as child learners, or through a memory constraint wherein irregular forms can only be remembered by an individual agent 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.

2016

The Evolution Of Collaborative Stories

Topics:
creativity
Authors
Christine Cuskley , Bernardo Monechi , Pietro Gravino , Vittorio Loreto |

The Evolution of Language: Proceedings of the 11th International Conference (EVOLANGX11), edited by:S.G. Roberts and C. Cuskley and L. McCrohon and L. Barcel'o-Coblijn and O. Fehér and T. Verhoef, 2016.

read more

Abstract

Studies in literature and narrative have begun to argue more forcefully for considering human evolution as central to understanding stories and storytelling more generally (Sugiyama, 2001; Hernadi, 2002). However, empirical studies in language evolution have focused primarily on language structure or the language faculty, leaving the evolution of stories largely unexplored (although see Von Heiseler, 2014). Stories are unique products of human culture enabled principally by human language. Given this, the dynamics of creativity in stories, and the traits which make successful stories, are of crucial interest to understanding the evolution of language in the context of human evolution more broadly. The current work aims to illuminate how stories emerge, evolve, and change in the context of a collaborative cultural effort. We present results from a novel experimental paradigm centered around a story game where players write short continuations (between 60 and 120 characters) of existing stories. These continuations then become open to other players to continue in turn. Stories are subject to player selection, allowing for variation and speciation of the resulting narratives, and evolve as a result of collaborative effort between players. The game starts with a seed of over 60 potential stories, and players choose which stories to continue, providing a player-driven story selection mechanism. In this way, stories which are creative, intriguing, and open ended spawn more stories, and eventually lead to longer story paths as play continues. The game also introduces further limitations by constraining a players’ view of the story path: players have access only to a story and its parent, meaning knowledge of the existing narrative is limited. We present data from hundreds of players and stories, creating large story trees which explore the space of different possible narratives which grow out of a confined set of starting points. This data allows us to investigate several aspects of the growing story trees to illuminate not only what makes a story successful, but how creative stories trigger new stories, and what makes individual storytellers successful. Given the selection mechanism central to game play, we identify the most successful stories by their number of offspring. Particularly successful storytellers emerge measured both by how many children their stories have spawned, and also how long their story path extends. We also show that coherent stories often emerge, despite the fact that they are authored by several different players, and any given player only sees a limited snapshot of the story path. We contextualise the results of the game and connect it to language evolution in two ways. First, we look for detectable triggers of innovation and creativity within the story trees, and identify these as expanding the adjacent possible (e.g., new adaptations open the space of other possible adaptations in the future; Tria, Loreto, Servedio, & Strogatz, 2014). We argue that this concept can be extended to stories, using evidence from the game bolstered by evidence from more traditional literature (the Gutenberg Corpus). Second, we frame the results in terms of recurring themes found in storytelling cross-culturally (Tehrani, 2013). We suggest that the most successful triggers of innovation in stories combine original novelty and a firm grounding in existing recurring story frameworks in human culture. This indicates that much like other cultural and biological systems, stories are subject to competing pressures for stability and conservation on the one hand, and innovation and novelty on the other.

2016

Modeling The Emergence Of Creole Languages

Topics:
language
Authors
Francesca Tria , Vittorio Loreto , Vito Servedio , S. Mufwene Salikoko |

The Evolution of Language: Proceedings of the 11th International Conference (EVOLANGX11), edited by:S.G. Roberts and C. Cuskley and L. McCrohon and L. Barcel'o-Coblijn and O. Fehér and T. Verhoef, 2016.

read more

Abstract

Creole languages offer an invaluable opportunity to study the processes leading to the emergence and evolution of Language, thanks to the short – typically a few generations – and reasonably well defined time-scales involved in their emergence. Another well-known case of a very fast emergence of a Language, though referring to a much smaller population size and different ecological conditions, is that of the Nicaraguan Sign Language. What these two phenomena have in common is that in both cases what is emerging is a contact language, i.e., a language born out of the non-trivial interaction of two (or more) parent languages. This is a typical case of what is known in biology as horizontal transmission. In many well-documented cases, creoles emerged in large segregated sugarcane or rice plantations on which the slave labourers were the overwhelming majority. Lacking a common substrate language, slaves were naturally brought to shift to the economically and politically dominant European language (often referred to as the lexifier) to bootstrap an effective communication system among themselves. Here, we focus on the emergence of creole languages originated in the contacts of European colonists and slaves during the 17th and 18th centuries in exogenous plantation colonies of especially the Atlantic and Indian Ocean, where detailed census data are available. Those for several States of USA can be found at http://www.census.gov/history, while for Central America and the Caribbean can be found at http://www.jamaicanfamilysearch.com/Samples/1790al11.htm. Without entering in the details of the creole formation at a fine-grained linguistic level, we aim at uncovering some of the general mechanisms that determine the emergence of contact languages, and that successfully apply to the case of creole formation.

2016

Dynamics on expanding spaces: modeling the emergence of novelties

Topics:
creativity
Authors
Vittorio Loreto , Servedio Vito D. P.and Strogatz Steven H.and Tria Francesca ,

Creativity and Universality in Language, edited by:Degli Esposti, Mirko and Altmann, Eduardo G. and Pachet, François, Springer International Publishing, Cham, 2016. pp.59--83.

read more

Abstract

Novelties are part of our daily lives. We constantly adopt new technologies, conceive new ideas, meet new people, and experiment with new situations. Occasionally, we as individual, in a complicated cognitive and sometimes fortuitous process, come up with something that is not only new to us, but to our entire society so that what is a personal novelty can turn into an innovation at a global level. Innovations occur throughout social, biological, and technological systems and, though we perceive them as a very natural ingredient of our human experience, little is known about the processes determining their emergence. Still the statistical occurrence of innovations shows striking regularities that represent a starting point to get a deeper insight in the whole phenomenology. This paper represents a small step in that direction, focusing on reviewing the scientific attempts to effectively model the emergence of the new and its regularities, with an emphasis on more recent contributions: from the plain Simon's model tracing back to the 1950s, to the newest model of Polya's urn with triggering of one novelty by another. What seems to be key in the successful modeling schemes proposed so far is the idea of looking at evolution as a path in a complex space, physical, conceptual, biological, and technological, whose structure and topology get continuously reshaped and expanded by the occurrence of the new. Mathematically, it is very interesting to look at the consequences of the interplay between the ``actual'' and the ``possible'' and this is the aim of this short review.
2015

Congestion transition in air traffic networks

Topics:
creativity
Authors
Bernardo Monechi , Servedio Vito DP , Vittorio Loreto |

PloS ONE, 10, 5, Public Library of Science, 2015. pp.e0125546.

read more

Abstract

Air Transportation represents a very interesting example of a complex techno-social system whose importance has considerably grown in time and whose management requires a careful understanding of the subtle interplay between technological infrastructure and human behavior. Despite the competition with other transportation systems, a growth of air traffic is still foreseen in Europe for the next years. The increase of traffic load could bring the current Air Traffic Network above its capacity limits so that safety standards and performances might not be guaranteed anymore. Lacking the possibility of a direct investigation of this scenario, we resort to computer simulations in order to quantify the disruptive potential of an increase in traffic load. To this end we model the Air Transportation system as a complex dynamical network of flights controlled by humans who have to solve potentially dangerous conflicts by redirecting aircraft trajectories. The model is driven and validated through historical data of flight schedules in a European national airspace. While correctly reproducing actual statistics of the Air Transportation system, e.g., the distribution of delays, the model allows for theoretical predictions. Upon an increase of the traffic load injected in the system, the model predicts a transition from a phase in which all conflicts can be successfully resolved, to a phase in which many conflicts cannot be resolved anymore. We highlight how the current flight density of the Air Transportation system is well below the transition, provided that controllers make use of a special re-routing procedure. While the congestion transition displays a universal scaling behavior, its threshold depends on the conflict solving strategy adopted. Finally, the generality of the modeling scheme introduced makes it a flexible general tool to simulate and control Air Transportation systems in realistic and synthetic scenarios.

2015

Optimal learning paths in information networks

Topics:
creativity
Authors
Rodi GC , Vittorio Loreto , Servedio VDP , Tria F |

Scientific reports, 5, Nature Publishing Group, 2015. pp.10286.

read more

Abstract

Each sphere of knowledge and information could be depicted as a complex mesh of correlated items. By properly exploiting these connections, innovative and more efficient navigation strategies could be defined, possibly leading to a faster learning process and an enduring retention of information. In this work we investigate how the topological structure embedding the items to be learned can affect the efficiency of the learning dynamics. To this end we introduce a general class of algorithms that simulate the exploration of knowledge/information networks standing on well-established findings on educational scheduling, namely the spacing and lag effects. While constructing their learning schedules, individuals move along connections, periodically revisiting some concepts, and sometimes jumping on very distant ones. In order to investigate the effect of networked information structures on the proposed learning dynamics we focused both on synthetic and real-world graphs such as subsections of Wikipedia and word-association graphs. We highlight the existence of optimal topological structures for the simulated learning dynamics whose efficiency is affected by the balance between hubs and the least connected items. Interestingly, the real-world graphs we considered lead naturally to almost optimal learning performances.

2015

Maximum entropy model for melodic patterns

Topics:
Authors
Jason Sakellariou , and Francesca Tria , Loreto Vittorio , Francois Pachet ,

ICML Workshop on Constructive Machine Learning, 2015.

read more

Abstract

We introduce a model for music generation where melodies are seen as a network of interacting notes. Starting from the principle of maximum entropy we assign to this network a probability distribution, which is learned from an existing musical corpus. We use this model to generate novel musical sequences that mimic the style of the corpus. Our main result is that this model can reproduce high-order patterns despite having a polynomial sample complexity. This is in contrast with the more traditionally used Markov models that have an exponential sample complexity.

2015

Modeling the Emergence of Contact Languages

Topics:
language
Authors
Francesca Tria , Vito D.P. Servedio , Salikoko Mufwene , Vittorio Loreto |

PLoS ONE, 10, 4, Public Library of Science, 2015. pp.e0120771.

read more

Abstract

Contact languages are born out of the non-trivial interaction of two (or more) parent languages. Nowadays, the enhanced possibility of mobility and communication allows for a strong mixing of languages and cultures, thus raising the issue of whether there are any pure languages or cultures that are unaffected by contact with others. As with bacteria or viruses in biological evolution, the evolution of languages is marked by horizontal transmission; but to date no reliable quantitative tools to investigate these phenomena have been available. An interesting and well documented example of contact language is the emergence of creole languages, which originated in the contacts of European colonists and slaves during the 17th and 18th centuries in exogenous plantation colonies of especially the Atlantic and Indian Ocean. Here, we focus on the emergence of creole languages to demonstrate a dynamical process that mimics the process of creole formation in American and Caribbean plantation ecologies. Inspired by the Naming Game (NG), our modeling scheme incorporates demographic information about the colonial population in the framework of a non-trivial interaction network including three populations: Europeans, Mulattos/Creoles, and Bozal slaves. We show how this sole information makes it possible to discriminate territories that produced modern creoles from those that did not, with a surprising accuracy. The generality of our approach provides valuable insights for further studies on the emergence of languages in contact ecologies as well as to test specific hypotheses about the peopling and the population structures of the relevant territories. We submit that these tools could be relevant to addressing problems related to contact phenomena in many cultural domains: e.g., emergence of dialects, language competition and hybridization, globalization phenomena.

2015

General three-state model with biased population replacement: Analytical solution and application to language dynamics

Topics:
language
Authors
Francesca Colaiori , Claudio Castellano , Christine F. Cuskley , Vittorio Loreto , Martina Pugliese , Francesca Tria |

PhysicalReview E, 91, American Physical Society, 2015. pp.012808.

read more

Abstract

Empirical evidence shows that the rate of irregular usage of English verbs exhibits discontinuity as a function of their frequency: the most frequent verbs tend to be totally irregular. We aim to qualitatively understand the origin of this feature by studying simple agent-based models of language dynamics, where each agent adopts an inflectional state for a verb and may change it upon interaction with other agents. At the same time, agents are replaced at some rate by new agents adopting the regular form. In models with only two inflectional states (regular and irregular), we observe that either all verbs regularise irrespective of their frequency, or a continuous transition occurs between a low-frequency state, where the lemma becomes fully regular, and a high-frequency one, where both forms coexist. Introducing a third (mixed) state, wherein agents may use either form, we find that a third, qualitatively different behaviour may emerge, namely, a discontinuous transition in frequency. We introduce and solve analytically a very general class of three-state models that allows us to fully understand these behaviours in a unified framework. Realistic sets of interaction rules, including the well-known naming game (NG) model, result in a discontinuous transition, in agreement with recent empirical findings. We also point out that the distinction between speaker and hearer in the interaction has no effect on the collective behaviour. The results for the general three-state model, although discussed in terms of language dynamics, are widely applicable.

2015

The adoption of linguistic rules in native and non-native speakers: Evidence from a Wug task

Topics:
language
Authors
Christine Cuskley , Francesca Colaiori , Claudio Castellano , Vittorio Loreto , Martina Pugliese , Francesca Tria |

Journal of Memory and Language, 84, 2015. pp.205 - 223.

read more

Abstract

Several recent theories have suggested that an increase in the number of non-native speakers in a language can lead to changes in morphological rules. We examine this experimentally by contrasting the performance of native and non-native English speakers in a simple Wug-task, showing that non-native speakers are significantly more likely to provide non -ed (i.e., irregular) past-tense forms for novel verbs than native speakers. Both groups are sensitive to sound similarities between new words and existing words (i.e., are more likely to provide irregular forms for novel words which sound similar to existing irregulars). Among both natives and non-natives, irregularizations are non-random; that is, rather than presenting as truly irregular inflectional strategies, they follow identifiable sub-rules present in the highly frequent set of irregular English verbs. Our results shed new light on how native and non-native learners can affect language structure.

2015

Local Optimization Strategies in Urban Vehicular Mobility

Topics:
creativity
Authors
Pierpaolo Mastroianni , Bernardo Monechi , Carlo Liberto , Gaetano Valenti , Vito DP Servedio , Vittorio Loreto |

PloS one, 10, 12, Public Library of Science, 2015. pp.e0143799.

read more

Abstract

The comprehension of vehicular traffic in urban environments is crucial to achieve a good management of the complex processes arising from people collective motion. Even allowing for the great complexity of human beings, human behavior turns out to be subject to strong constraints – physical, environmental, social, economical – that induce the emergence of common patterns. The observation and understanding of those patterns is key to setup effective strategies to optimize the quality of life in cities while not frustrating the natural need for mobility. In this paper we focus on vehicular mobility with the aim to reveal the underlying patterns and uncover the human strategies determining them. To this end we analyze a large dataset of GPS vehicles tracks collected in the Rome (Italy) district during a month. We demonstrate the existence of a local optimization of travel times that vehicle drivers perform while choosing their journey. This finding is mirrored by two additional important facts, i.e., the observation that the average vehicle velocity increases by increasing the travel length and the emergence of a universal scaling law for the distribution of travel times at fixed traveled length. A simple modeling scheme confirms this scenario opening the way to further predictions.

2015

Individual biases, cultural evolution, and the statistical nature of language universals: The case of colour naming systems

Topics:
language
Authors
Andrea Baronchelli , Vittorio Loreto , Andrea Puglisi |

PloS one, 10, 5, Public Library of Science, 2015. pp.e0125019.

read more

Abstract

Language universals have long been attributed to an innate Universal Grammar. An alternative explanation states that linguistic universals emerged independently in every language in response to shared cognitive or perceptual biases. A computational model has recently shown how this could be the case, focusing on the paradigmatic example of the universal properties of colour naming patterns, and producing results in quantitative agreement with the experimental data. Here we investigate the role of an individual perceptual bias in the framework of the model. We study how, and to what extent, the structure of the bias influences the corresponding linguistic universal patterns. We show that the cultural history of a group of speakers introduces population-specific constraints that act against the pressure for uniformity arising from the individual bias, and we clarify the interplay between these two forces.

2014

An Air Traffic Control Model Based Local Optimization over the Airways Network

Topics:
creativity
Authors
Bernardo Monechi Vito DP Servedio Vittorio Loreto |

Proceedings of the SESAR Innovation Days (2014), edited by:Dirk Schaefer, EUROCONTROL, 2014.

read more

Abstract

The introduction of a new SESAR scenario in the European Airspace will impact the functioning and the performances of the current Air Traffic Management (ATM) System. The understanding of the features and the limits of the current system could be crucial in order to improve and design the structure of the future ATM. In this paper we present some results of the “Assessment of Critical Delay Patterns and Avalanche Dynamics” PhD project from the ComplexWorld Network. During this project we developed a model of Air Traffic Control (ATC) based on Complex Network theory capable of reproducing the features of the real ATC in three European National Airspaces. We then developed an optimization algorithm based on “Extremal Optimization” in order to build efficient and globally optimized planned trajectories. The ATC model is applied in order to study the efficiency of this new planned trajectories when subject to external perturbations and to compare them to the current situation.

2014

The dynamics of correlated novelties

Topics:
creativity
Authors
Tria F. , Vittorio Loreto , Servedio V. D. P. , Strogatz S. H. |

Scientific Reports, 4, Nature Publishing Group, Jul, 2014. pp.5890.

read more

Abstract

Novelties are a familiar part of daily life. They are also fundamental to the evolution of biological systems, human society, and technology. By opening new possibilities, one novelty can pave the way for others in a process that Kauffman has called “expanding the adjacent possible”. The dynamics of correlated novelties, however, have yet to be quantified empirically or modeled mathematically. Here we propose a simple mathematical model that mimics the process of exploring a physical, biological, or conceptual space that enlarges whenever a novelty occurs. The model, a generalization of Polya’s urn, predicts statistical laws for the rate at which novelties happen (Heaps’ law) and for the probability distribution on the space explored (Zipf’s law), as well as signatures of the process by which one novelty sets the stage for another. We test these predictions on four data sets of human activity: the edit events of Wikipedia pages, the emergence of tags in annotation systems, the sequence of words in texts, and listening to new songs in online music catalogues. By quantifying the dynamics of correlated novelties, our results provide a starting point for a deeper understanding of the adjacent possible and its role in biological, cultural, and technological evolution.

2014

Internal and External Dynamics in Language: Evidence from Verb Regularity in a Historical Corpus of English

Topics:
language
Authors
Christine F. Cuskley , Martina Pugliese , Claudio Castellano , Francesca Colaiori , Vittorio Loreto , Francesca Tria |

PLoS ONE, 9, Public Library of Science, 2014.

read more

Abstract

Human languages are rule governed, but almost invariably these rules have exceptions in the form of irregularities. Since rules in language are efficient and productive, the persistence of irregularity is an anomaly. How does irregularity linger in the face of internal (endogenous) and external (exogenous) pressures to conform to a rule? Here we address this problem by taking a detailed look at simple past tense verbs in the Corpus of Historical American English. The data show that the language is open, with many new verbs entering. At the same time, existing verbs might tend to regularize or irregularize as a consequence of internal dynamics, but overall, the amount of irregularity sustained by the language stays roughly constant over time. Despite continuous vocabulary growth, and presumably, an attendant increase in expressive power, there is no corresponding growth in irregularity. We analyze the set of irregulars, showing they may adhere to a set of minority rules, allowing for increased stability of irregularity over time. These findings contribute to the debate on how language systems become rule governed, and how and why they sustain exceptions to rules, providing insight into the interplay between the emergence and maintenance of rules and exceptions in language.

2013

Emergence of fast agreement in an overhearing population: The case of the naming game

Topics:
language
Authors
Suman Kalyan Maity , Animesh Mukherjee , Francesca Tria , Vittorio Loreto |

EUROPHYSICS LETTERS, 101, 2013.

read more

Abstract

The naming game (NG) describes the agreement dynamics of a population of N agents interacting locally in pairs leading to the emergence of a shared vocabulary. This model has its relevance in the novel fields of semiotic dynamics and specifically to opinion formation and language evolution. The application of this model ranges from wireless sensor networks as spreading algorithms, leader election algorithms to user-based social tagging systems. In this paper, we introduce the concept of overhearing (i.e., at every time step of the game, a random set of N-delta individuals are chosen from the population who overhear the transmitted word from the speaker and accordingly reshape their inventories). When delta= 0 one recovers the behavior of the original NG. As one increases delta, the population of agents reaches a faster agreement with a significantly low-memory requirement. The convergence time to reach global consensus scales as log N as delta approaches 1. Copyright (C) EPLA, 2013

2012

Naming a structured world: a cultural route to duality of patterning

Topics:
language
Authors
Francesca Tria , Bruno Galantucci , Vittorio Loreto |

PLOS ONE, 2012. pp.e37744-1--e37744-8.

read more

Abstract

The lexicons of human languages organize their units at two distinct levels. At a first combinatorial level, meaningless forms (typically referred to as phonemes) are combined into meaningful units (typically referred to as morphemes). Thanks to this, many morphemes can be obtained by relatively simple combinations of a small number of phonemes. At a second compositional level of the lexicon, morphemes are composed into larger lexical units, the meaning of which is related to the individual meanings of the composing morphemes. This duality of patterning is not a necessity for lexicons and the question remains wide open regarding how a population of individuals is able to bootstrap such a structure and the evolutionary advantages of its emergence. Here we address this question in the framework of a multi-agents model, where a population of individuals plays simple naming games in a conceptual environment modeled as a graph. We demonstrate that errors in communication conditions for the emergence of duality of patterning, that can thus be explained in a pure cultural way. Compositional lexicons turn out to be faster to lead to successful communication thanpurely combinatorial lexicons, suggesting that meaning played a crucial role in the evolution of language.

2012

On the origin of the hierarchy of color names

Topics:
language
Authors
Vittorio Loreto , Animesh Mukherjee , Francesca Tria |

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA (PNAS), 2012.

read more

Abstract

One of the fundamental problems in cognitive science is how humans categorize the visible color spectrum. The empirical evidence of the existence of universal or recurrent patterns in color naming across cultures is paralleled by the observation that color names begin to be used by individual cultures in a relatively fixed order. The origin of this hierarchy is largely unexplained. Here we resort to multiagent simulations, where a population of individuals, subject to a simple perceptual constraint shared by all humans, namely the human Just Noticeable Difference, categorizes and names colors through a purely cultural negotiation in the form of language games. We found that the time needed for a population to reach consensus on a color name depends on the region of the visible color spectrum. If color spectrum regions are ranked according to this criterion, a hierarchy with [red, (magenta)-red], [violet], [green/yellow], [blue], [orange], and [cyan], appearing in this order, is recovered, featuring an excellent quantitative agreement with the empirical observations of the WCS. Our results demonstrate a clear possible route to the emergence of hierarchical color categories, confirming that the theoretical modeling in this area has now attained the required maturity to make significant contributions to the ongoing debates concerning language universals.

2011

Statistical physics of language dynamics

Topics:
language
Authors
Vittorio Loreto , Andrea Baronchelli , Animesh Mukherjee , Andrea Puglisi , Francesca Tria |

JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT, P04006, Bristol : IOP Publishing, 2011.

read more

Abstract

Language dynamics is a rapidly growing field that focuses on all processes related to the emergence, evolution, change and extinction of languages. Recently, the study of self-organization and evolution of language and meaning has led to the idea that a community of language users can be seen as a complex dynamical system, which collectively solves the problem of developing a shared communication framework through the back-and-forth signaling between individuals. We shall review some of the progress made in the past few years and highlight potential future directions of research in this area. In particular, the emergence of a common lexicon and of a shared set of linguistic categories will be discussed, as examples corresponding to the early stages of a language. The extent to which synthetic modeling is nowadays contributing to the ongoing debate in cognitive science will be pointed out. In addition, the burst of growth of the web is providing new experimental frameworks. It makes available a huge amount of resources, both as novel tools and data to be analyzed, allowing quantitative and large-scale analysis of the processes underlying the emergence of a collective information and language dynamics.
2010

Modeling the Formation of Language: Conclusions and Future Research

Topics:
Language
Authors
Luc Steels , Vittorio Loreto |

Evolution of Communication and Language in Embodied Agents, edited by:Nolfi, S. and Mirolli, M., Springer, Berlin, 2010. pp.283--288.

2010

Modeling the emergence of universality in color naming patterns

Topics:
language
Authors
Andrea Baronchelli , Tao Gong , Andrea Puglisi , Vittorio Loreto |

Proceedings of the National Academy of Sciences, 107, 6, National Academy of Sciences, 2010. pp.2403--2407.

read more

Abstract

The empirical evidence that human color categorization exhibits some universal patterns beyond superficial discrepancies across different cultures is a major breakthrough in cognitive science. As observed in the World Color Survey (WCS), indeed, any two groups of individuals develop quite different categorization patterns, but some universal properties can be identified by a statistical analysis over a large number of populations. Here, we reproduce the WCS in a numerical model in which different populations develop independently their own categorization systems by playing elementary language games. We find that a simple perceptual constraint shared by all humans, namely the human Just Noticeable Difference (JND), is sufficient to trigger the emergence of universal patterns that unconstrained cultural interaction fails to produce. We test the results of our experiment against real data by performing the same statistical analysis proposed to quantify the universal tendencies shown in the WCS [Kay P & Regier T. (2003) Proc. Natl. Acad. Sci. USA 100: 9085-9089], and obtain an excellent quantitative agreement. This work confirms that synthetic modeling has nowadays reached the maturity to contribute significantly to the ongoing debate in cognitive science.

2008

In-depth analysis of the Naming Game dynamics: the homogeneous mixing case

Topics:
Language
Authors
Baronchelli Andrea , Vittorio Loreto , Luc Steels |

INTERNATIONAL JOURNAL OF MODERN PHYSICS C, 19, World Scientific Publishing Company:PO Box 128, Farrer Road, Singapore 912805 Singapore:011 65 6 4665775, EMAIL: journal, 2008. pp.785--812.

2008

In-depth analysis of the Naming Game dynamics: the homogeneous mixing case

Topics:
language
Authors
Andrea Baronchelli , Vittorio Loreto , Luc Steels |

INTERNATIONAL JOURNAL OF MODERN PHYSICS C, 19, World Scientific Publishing Company, 2008. pp.785--812.

read more

Abstract

Language emergence and evolution have recently gained growing attention through multi-agent models and mathematical frameworks to study their behavior. Here we investigate further the Naming Game, a model able to account for the emergence of a shared vocabulary of form-meaning associations through social/cultural learning. Due to the simplicity of both the structure of the agents and their interaction rules, the dynamics of this model can be analyzed in great detail using numerical simulations and analytical arguments. This paper first reviews some existing results and then presents a new overall understanding.
2007

Social Dynamics: Emergence of Language

Topics:
Language
Authors
Vittorio Loreto , Luc Steels |

Nature Physics, 3, 11, 2007. pp.758--760.

read more

Abstract

Our social behaviour has evolved primarily through contact with a limited number of other individuals. Yet as a species we exhibit uniformities on a global scale. This kind of emergent behaviour is familiar territory for statistical physicists.

2007

The role of topology on the dynamics of the Naming Game

Topics:
language
Authors
Andrea Baronchelli , Luca Dall'Asta , Alain Barrat , Vittorio Loreto |

THE EUROPEAN PHYSICAL JOURNAL. SPECIAL TOPICS, 143, Elsevier Science Limited, 2007. pp.233--235.

read more

Abstract

The Naming Game captures the essential features leading a population to agree on the use of a semiotic convention (or, more in general, an opinion). Consensus emerges through local negotiations between pairs of agents, in the absence of any central co-ordination. Thus, it is natural that topology, identifying the set of possible interactions, plays a central role in the dynamics of the model. Here, we review the role of different topological properties, pointing out that finite connectivity, combined with the small-world property, ensure the best performances in terms of memory usage and time to reach convergence.
2007

Non-equilibrium phase transition in negotiation dynamics

Topics:
language
Authors
Andrea Baronchelli , Luca Dall'Asta , Alain Barrat , Vittorio Loreto |

PHYSICAL REVIEW E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS, 76, AMERICAN PHYSICAL SOC, ONE PHYSICS ELLIPSE, COLLEGE PK, USA, MD, 20740-3844, 2007. pp.051102:1--051102:4.

read more

Abstract

We introduce a model of negotiation dynamics whose aim is that of mimicking the mechanisms leading to opinion and convention formation in a population of individuals. The negotiation process, as opposed to “herdinglike” or “bounded confidence” driven processes, is based on a microscopic dynamics where memory and feedback play a central role. Our model displays a nonequilibrium phase transition from an absorbing state in which all agents reach a consensus to an active stationary state characterized either by polarization or fragmentation in clusters of agents with different opinions. We show the existence of at least two different universality classes, one for the case with two possible opinions and one for the case with an unlimited number of opinions. The phase transition is studied analytically and numerically for various topologies of the agents’ interaction network. In both cases the universality classes do not seem to depend on the specific interaction topology, the only relevant feature being the total number of different opinions ever present in the system.
2006

Sharp transition towards shared vocabularies in multi-agent systems

Topics:
language
Authors
Andrea Baronchelli , Maddalena Felici , Vittorio Loreto , Emanuele Caglioti , Luc Steels |

Journal of Statistical Mechanics: Theory and Experiment, P06014, IOP Publishing, 2006. pp.P06014--P06019.

read more

Abstract

What processes can explain how very large populations are able to converge on the use of a particular word or grammatical construction without global coordination? Answering this question helps to understand why new language constructs usually propagate along an S-shaped curve with a rather sudden transition towards global agreement. It also helps to analyse and design new technologies that support or orchestrate self-organizing communication systems, such as recent social tagging systems for the web. The article introduces and studies a microscopic model of communicating autonomous agents performing language games without any central control. We show that the system undergoes a disorder/order transition, going through a sharp symmetry breaking process to reach a shared set of conventions. Before the transition, the system builds up non-trivial scale-invariant correlations, for instance in the distribution of competing synonyms, which display a Zipf-like law. These correlations make the system ready for the transition towards shared conventions, which, observed on the timescale of collective behaviours, becomes sharper and sharper with system size. This surprising result not only explains why human language can scale up to very large populations but also suggests ways to optimize artificial semiotic dynamics.

2006

Nonequilibrium dynamics of language games on complex networks

Topics:
language
Authors
Andrea Baronchelli , Luca Dall'Asta , Alain Barrat , Vittorio Loreto |

PHYSICAL REVIEW E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS, 74, AMERICAN PHYSICAL SOC, ONE PHYSICS ELLIPSE, COLLEGE PK, USA, MD, 20740-3844, 2006. pp.036105:1--036105:13.

read more

Abstract

The naming game is a model of nonequilibrium 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^1.4, 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.
2006

Topology induced coarsening in language games

Topics:
language
Authors
Andrea Baronchelli , Luca Dall'Asta , Alain Barrat , Vittorio Loreto |

PHYSICAL REVIEW E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS, 73, AMERICAN PHYSICAL SOC, ONE PHYSICS ELLIPSE, COLLEGE PK, USA, MD, 20740-3844, 2006. pp.015102--015105.

read more

Abstract

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 that requires less cognitive effort of the agents, with respect to the mean-field case, but takes longer to complete. In one dimension, 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 <=4 (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 evidence supporting this picture.
2006

Agreement dynamics on small-world networks

Topics:
language
Authors
Luca Dall'Asta , Andrea Baronchelli , Alain Barrat , Vittorio Loreto |

EUROPHYSICS LETTERS, 73, EDP Sciences, 2006. pp.969--975.

read more

Abstract

In this paper we analyze the effect of a non-trivial topology on the dynamics of the so-called Naming Game, a recently introduced model which addresses the issue of how shared conventions emerge spontaneously in a population of agents. We consider in particular the small-world topology and study the convergence towards the global agreement as a function of the population size N as well as of the parameter p which sets the rate of rewiring leading to the small-world network. As long as p >> 1/N, there exists a crossover time scaling as N/P^2which separates an early one-dimensional–like dynamics from a late-stage mean-field–like behavior. At the beginning of the process, the local quasi–one-dimensional topology induces a coarsening dynamics which allows for a minimization of the cognitive effort (memory) required to the agents. In the late stages, on the other hand, the mean-field–like topology leads to a speed-up of the convergence process with respect to the one-dimensional case.