{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:10:42Z","timestamp":1760242242572,"version":"build-2065373602"},"reference-count":54,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2017,2,9]],"date-time":"2017-02-09T00:00:00Z","timestamp":1486598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Games"],"abstract":"<jats:p>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 onverge 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 xamine 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.<\/jats:p>","DOI":"10.3390\/g8010012","type":"journal-article","created":{"date-parts":[[2017,2,10]],"date-time":"2017-02-10T05:27:09Z","timestamp":1486704429000},"page":"12","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Topological Aspects of the Multi-Language Phases of the Naming Game on Community-Based Networks"],"prefix":"10.3390","volume":"8","author":[{"given":"Filippo","family":"Palombi","sequence":"first","affiliation":[{"name":"ENEA\u2014Italian Agency for New Technologies, Energy and Sustainable Economic Development, Via E. Fermi 45, 00044 Frascati, Italy"}]},{"given":"Simona","family":"Toti","sequence":"additional","affiliation":[{"name":"ISTAT\u2014Italian National Institute of Statistics, Via C. Balbo 16, 00184 Rome, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2017,2,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1103\/RevModPhys.81.591","article-title":"Statistical physics of social dynamics","volume":"81","author":"Castellano","year":"2009","journal-title":"Rev. Mod. Phys."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1023\/A:1005319718167","article-title":"Evolutionary Consequences of Language Learning","volume":"20","author":"Niyogi","year":"1997","journal-title":"Linguist. Philos."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"8028","DOI":"10.1073\/pnas.96.14.8028","article-title":"The evolution of language","volume":"96","author":"Nowak","year":"1999","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1006\/jtbi.1999.0981","article-title":"The Evolutionary Language Game","volume":"200","author":"Nowak","year":"1999","journal-title":"J. Theor. Biol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1126\/science.291.5501.114","article-title":"Evolution of Universal Grammar","volume":"291","author":"Nowak","year":"2001","journal-title":"Science"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1162\/106454603322694825","article-title":"Iterated Learning: A Framework for the Emergence of Language","volume":"9","author":"Smith","year":"2003","journal-title":"Artif. Life"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2003.08.005","article-title":"Optimizing the mutual intelligibility of linguistic agents in a shared world","volume":"154","author":"Komarova","year":"2004","journal-title":"Artif. Intell."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"P06014","DOI":"10.1088\/1742-5468\/2006\/06\/P06014","article-title":"Sharp transition towards shared vocabularies in multi-agent systems","volume":"2006","author":"Baronchelli","year":"2006","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1162\/artl.1995.2.3.319","article-title":"A self-organizing spatial vocabulary","volume":"2","author":"Steels","year":"1995","journal-title":"Artif. Life"},{"key":"ref_10","unstructured":"Langton, C.G., and Shimohara, K. (1997). Artificial Life V; Proceedings of the Fifth International Workshop on the Synthesis and Simulation of Living Systems, The MIT Press."},{"key":"ref_11","unstructured":"Wittgenstein, L. (2009). Philosophical Investigations, Wiley-Blackwell. [4th ed.]."},{"key":"ref_12","unstructured":"Rocha, L.M. (2006). Artif. Life X: Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems, The MIT Press."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"015102","DOI":"10.1103\/PhysRevE.73.015102","article-title":"Topology-induced coarsening in language games","volume":"73","author":"Baronchelli","year":"2006","journal-title":"Phys. Rev. E"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"036105","DOI":"10.1103\/PhysRevE.74.036105","article-title":"Nonequilibrium dynamics of language games on complex networks","volume":"74","author":"Baronchelli","year":"2006","journal-title":"Phys. Rev. E"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1209\/epl\/i2005-10481-7","article-title":"Agreement dynamics on small-world networks","volume":"73","author":"Baronchelli","year":"2006","journal-title":"EPL"},{"key":"ref_16","unstructured":"Cangelosi, A., Smith, A.D.M., and Smith, K. (2006). The Evolution of Language, Proceedings of the 6th International Conference (EVOLANG6), World Scientific Publishing Company."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1989","DOI":"10.1073\/pnas.1418838112","article-title":"The spontaneous emergence of conventions: An experimental study of cultural evolution","volume":"112","author":"Centola","year":"2015","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s11403-009-0057-7","article-title":"The Naming Game in social networks: Community formation and consensus engineering","volume":"4","author":"Lu","year":"2009","journal-title":"J. Econ. Interact. Coord."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Graph clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Comp. Sci. Rev."},{"key":"ref_20","first-page":"1082","article-title":"Communities in networks","volume":"56","author":"Porter","year":"2009","journal-title":"Not. Am. Math. Soc."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Phys. Rep."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1002\/sam.10133","article-title":"A Classification for Community Discovery Methods in Complex Networks","volume":"4","author":"Coscia","year":"2011","journal-title":"Stat. Anal. Data Min."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Newman, M. (2010). Networks: An Introduction, Oxford University Press, Inc.","DOI":"10.1093\/acprof:oso\/9780199206650.003.0001"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/2501654.2501657","article-title":"Overlapping Community Detection in Networks: The State-of-the-art and Comparative Study","volume":"45","author":"Xie","year":"2013","journal-title":"ACM Comput. Surv."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2016.09.002","article-title":"Community detection in networks: A user guide","volume":"659","author":"Fortunato","year":"2016","journal-title":"Phys. Rep."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1134\/S0005117916010094","article-title":"Language games in investigation of social networks: Finding communities and influential agents","volume":"77","author":"Gubanov","year":"2016","journal-title":"Autom. Remote Control"},{"key":"ref_27","first-page":"026113","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman","year":"2004","journal-title":"Phys. Rev."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"016118","DOI":"10.1103\/PhysRevE.80.016118","article-title":"Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities","volume":"80","author":"Lancichinetti","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/2.989932","article-title":"Self-organization and identification of Web communities","volume":"35","author":"Flake","year":"2002","journal-title":"Computer"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Lambiotte, R., and Ausloos, M. (2007). Coexistence of opposite opinions in a network with communities. J. Stat. Mech. Theory Exp., P08026.","DOI":"10.1088\/1742-5468\/2007\/08\/P08026"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Candia, J., and Mazzitello, K.I. (2008). Mass media influence spreading in social networks with community structure. J. Stat. Mech. Theory Exp., P07007.","DOI":"10.1088\/1742-5468\/2008\/07\/P07007"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1140\/epjb\/e2009-00284-2","article-title":"Consensus and ordering in language dynamics","volume":"71","author":"Baronchelli","year":"2009","journal-title":"Eur. Phys. J. B"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"011130","DOI":"10.1103\/PhysRevE.84.011130","article-title":"Social consensus through the influence of committed minorities","volume":"84","author":"Xie","year":"2011","journal-title":"Phys. Rev. E"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Xie, J., Emenheiser, J., Kirby, M., Sreenivasan, S., Szymanski, B.K., and Korniss, G. (2012). Evolution of opinions on social networks in the presence of competing committed groups. PLoS ONE, 7.","DOI":"10.1371\/journal.pone.0033215"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/s10955-014-1003-1","article-title":"Stochastic dynamics of the multi-state voter model over a network based on interacting cliques and zealot candidates","volume":"156","author":"Palombi","year":"2014","journal-title":"J. Stat. Phys."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"028701","DOI":"10.1103\/PhysRevLett.91.028701","article-title":"Does a Single Zealot Affect an Infinite Group of Voters?","volume":"91","author":"Mobilia","year":"2003","journal-title":"Phys. Rev. Lett."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Mobilia, M., Petersen, A., and Redner, S. (2007). On the role of zealotry in the voter model. J. Stat. Mech. Theory Exp., P08029.","DOI":"10.1088\/1742-5468\/2007\/08\/P08029"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","article-title":"Stochastic blockmodels: First steps","volume":"5","author":"Holland","year":"1983","journal-title":"Soc. Netw."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1002\/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2","article-title":"Algorithms for graph partitioning on the planted partition model","volume":"18","author":"Condon","year":"2001","journal-title":"Random Struct. Algorithms"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"McSherry, F. (2001, January 14\u201317). Spectral partitioning of random graphs. Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, USA.","DOI":"10.1109\/SFCS.2001.959929"},{"key":"ref_42","unstructured":"Barab\u00e1si, A.-L. (2013). Network Science, Cambridge University Press."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"051102","DOI":"10.1103\/PhysRevE.76.051102","article-title":"Nonequilibrium phase transition in negotiation dynamics","volume":"76","author":"Baronchelli","year":"2007","journal-title":"Phys. Rev. E"},{"key":"ref_44","unstructured":"Arnold, V.I. (1973). Ordinary Differential Equations, The MIT Press."},{"key":"ref_45","unstructured":"Atkinson, K.E. (2008). An Introduction to Numerical Analysis, Wiley India Pvt. Limited. [2nd ed.]."},{"key":"ref_46","unstructured":"Stanley, H.E. (1971). Introduction to Phase Transitions and Critical Phenomena, Oxford University Press."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1147","DOI":"10.1088\/0305-4470\/35\/5\/303","article-title":"Quasi-stationary distributions for stochastic processes with an absorbing state","volume":"35","author":"Dickman","year":"2002","journal-title":"J. Phys. A"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"047701","DOI":"10.1103\/PhysRevE.65.047701","article-title":"Numerical analysis of the master equation","volume":"65","author":"Dickman","year":"2002","journal-title":"Phys. Rev. E"},{"key":"ref_49","first-page":"14851","article-title":"Microscopic activity patterns in the naming game","volume":"3","author":"Baronchelli","year":"2006","journal-title":"J. Phys. A"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","year":"1999","journal-title":"Science"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0020-0190(89)90102-6","article-title":"An algorithm for drawing general undirected graphs","volume":"31","author":"Kamada","year":"1989","journal-title":"Inf. Process. Lett."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"3200","DOI":"10.1103\/PhysRevLett.86.3200","article-title":"Epidemic spreading in scale-free networks","volume":"86","author":"Vespignani","year":"2001","journal-title":"Phys. Rev. Lett."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"066117","DOI":"10.1103\/PhysRevE.63.066117","article-title":"Epidemic dynamics and endemic states in complex networks","volume":"63","author":"Vespignani","year":"2001","journal-title":"Phys. Rev. E"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Ponti, G., Palombi, F., Abate, D., Ambrosino, F., Aprea, G., Bastianelli, T., Beone, F., Bertini, R., Bracco, G., and Caporicci, M. (2014, January 21\u201325). The role of medium size facilities in the HPC ecosystem: The case of the new CRESCO4 cluster integrated in the ENEAGRID infrastructure. Proceedings of the 2014 International Conference on High Performance Computing and Simulation\u2014HPCS2014, Bologna, Italy.","DOI":"10.1109\/HPCSim.2014.6903807"}],"container-title":["Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-4336\/8\/1\/12\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:27:51Z","timestamp":1760207271000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-4336\/8\/1\/12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,9]]},"references-count":54,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,3]]}},"alternative-id":["g8010012"],"URL":"https:\/\/doi.org\/10.3390\/g8010012","relation":{},"ISSN":["2073-4336"],"issn-type":[{"type":"electronic","value":"2073-4336"}],"subject":[],"published":{"date-parts":[[2017,2,9]]}}}