Topological aspects of the multi-language phases of the Naming Game on community-based networks

Abstract

The Naming Game is an agent-based model where individuals communicate to name an initially unnamed object. On a large class of networks continual pairwise interactions lead the system to an ultimate consensus state, in which agents converge on a globally shared name. Soon after the introduction of the model, it was observed in literature that on community-based networks the path to consensus passes through metastable multi-language states. Subsequently, it was proposed to use this feature as a mean to discover communities in a given network. In this paper we show that metastable states correspond to genuine multi-language phases, emerging in the thermodynamic limit when the fraction of links connecting communities drops below critical thresholds. In particular, we study the transition to multi-language states in the stochastic block model and on networks with community overlap. We also examine the scaling of critical thresholds under variations of topological properties of the network, such as the number and relative size of communities and the structure of intra-/inter-community links. Our results provide a theoretical justification for the proposed use of the model as a community-detection algorithm.

41 pages, 13 figures. Version accepted for publication in Games (special issue "Evolutionary Games and Statistical Physics of Social Networks")

References in corpus (14)

• Statistical physics of social dynamics
• Community detection in networks: A user guide
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Sharp transition towards shared vocabularies in multi-agent systems
• Does a Single Zealot Affect an Infinite Group of Voters ?
• On the Role of Zealotry in the Voter Model
• A Classification for Community Discovery Methods in Complex Networks
• The Spontaneous Emergence of Conventions: An Experimental Study of Cultural Evolution
• Non-equilibrium dynamics of language games on complex networks
• Non-equilibrium phase transition in negotiation dynamics
• The Naming Game in Social Networks: Community Formation and Consensus Engineering
• Agreement dynamics on small-world networks
• Microscopic activity patterns in the Naming Game
• Mass Media Influence Spreading in Social Networks with Community Structure