Emergence, Complexity and Computation ECC Guanrong Chen Yang Lou Naming Game Models, Simulations and Analysis Emergence, Complexity and Computation Volume 34 Series editors Ivan Zelinka, Technical University of Ostrava, Ostrava, Czech Republic e-mail: [email protected] Andrew Adamatzky, University of the West of England, Bristol, UK e-mail: [email protected] Guanrong Chen, City University of Hong Kong, Hong Kong, China e-mail: [email protected] Editorial Board Ajith Abraham, MirLabs, USA Ana Lucia C. Bazzan, Universidade Federal do Rio Grande do Sul, Porto Alegre, RS, Brazil Juan C. Burguillo, University of Vigo, Spain Sergej Čelikovský, Academy of Sciences of the Czech Republic, Czech Republic Mohammed Chadli, University of Jules Verne, France Emilio Corchado, University of Salamanca, Spain Donald Davendra, Technical University of Ostrava, Czech Republic Andrew Ilachinski, Center for Naval Analyses, USA Jouni Lampinen, University of Vaasa, Finland Martin Middendorf, University of Leipzig, Germany Edward Ott, University of Maryland, USA Linqiang Pan, Huazhong University of Science and Technology, Wuhan, China Gheorghe Păun, Romanian Academy, Bucharest, Romania Hendrik Richter, HTWK Leipzig University of Applied Sciences, Germany Juan A. Rodriguez-Aguilar, IIIA-CSIC, Spain Otto Rössler, Institute of Physical and Theoretical Chemistry, Tübingen, Germany Vaclav Snasel, Technical University of Ostrava, Czech Republic Ivo Vondrák, Technical University of Ostrava, Czech Republic Hector Zenil, Karolinska Institute, Sweden The Emergence, Complexity and Computation (ECC) series publishes new developments, advancements and selected topics in the fields of complexity, computation and emergence. The series focuses on all aspects of reality-based computation approaches from an interdisciplinary point of view especially from applied sciences, biology, physics, or chemistry. It presents new ideas and inter- disciplinary insight on the mutual intersection of subareas of computation, com- plexity and emergence and its impact and limits to any computing based on physical limits (thermodynamic and quantum limits, Bremermann’s limit, Seth Lloyd limits…) as well as algorithmic limits (Gödel’s proof and its impact on calculation,algorithmiccomplexity,theChaitin’sOmeganumberandKolmogorov complexity, non-traditional calculations like Turing machine process and its con- sequences,…) and limitations arising in artificial intelligence field. The topics are (but not limited to) membrane computing, DNA computing, immune computing, quantumcomputing,swarmcomputing,analogiccomputing,chaoscomputingand computing on the edge of chaos, computational aspects of dynamics of complex systems (systems with self-organization, multiagent systems, cellular automata, artificiallife,…),emergenceofcomplexsystemsanditscomputationalaspects,and agent based computation. The main aim of this series it to discuss the above mentioned topics from an interdisciplinary point of view and present new ideas coming from mutual intersection of classical as well as modern methods of com- putation. Within the scope of the series are monographs, lecture notes, selected contributions from specialized conferences and workshops, special contribution from international experts. More information about this series at http://www.springer.com/series/10624 Guanrong Chen Yang Lou (cid:129) Naming Game Models, Simulations and Analysis 123 Guanrong Chen Yang Lou Department ofElectronic Engineering Centrefor Chaos andComplexNetworks City University of HongKong City University of HongKong Hong Kong,China Hong Kong,China ISSN 2194-7287 ISSN 2194-7295 (electronic) Emergence, Complexity andComputation ISBN978-3-030-05242-3 ISBN978-3-030-05243-0 (eBook) https://doi.org/10.1007/978-3-030-05243-0 LibraryofCongressControlNumber:2018962759 ©SpringerNatureSwitzerlandAG2019 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission orinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfrom therelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors, and the editorsare safeto assume that the adviceand informationin this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authorsortheeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinor for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface Languageisauniquehallmarkofhumanbeingsamongallspeciesinnature,which is emerged and developed by creation, acquisition, and maintenance. Humans use languagetocommunicatewitheachother,toexchangeinformation,andtoexpress ideas, which in many ways have significantly changed our world and ourselves. In the study of language evolution and development, one important scientific method is based on social or computer game simulations. In a typical language game,asimplemathematicalmodelisdesignedandusedtosimulatetheprocessof linguistic pattern formation and recognition, where a population of humans is involvedintheplayandtheyfollowsomepre-setgamerulesleadingtoconsensus of the whole population on a new word, a new phrase, or a new sentence. A representative computer game model for studying language creation and development is the so-called naming game model which, along with several vari- ants,isasimulation-based numericalstudyexploringtheemergenceandevolution of shared information in a population of communicating agents. The shared informationcouldbe,forexample,asetofemergingnamesforanobjectobserved bytheagents,orsomesocialconventions,ideas,knowledge,etc.Thepopulationof agents is connected in a certain communication topology, and thus each agent can beconsideredasanodeintheunderlyingcommunicationnetwork,withthemutual interaction or acquaintance between two connected nodes represented by an edge. Asaresult,naminggameisformulatedasareaction–diffusionprocessonagraph, which can be studied using tools from the graph theory in mathematics. This monograph presents an introduction to the naming game in various ver- sions, specifically the minimal naming game with agents having infinite or finite sizesofmemories(Chaps.2and3),naminggamewithgroupdiscussions(Chap.4), naming game with learning errors in communications (Chap. 5), naming game on multi-community networks (Chap. 6), naming game with multiple words or sen- tences (Chap. 7), and naming game with multiple languages (Chap. 8). It is the authors’ hope that, after reading, the readers could have some fundamental knowledge with a comprehensive understanding of the naming game and its applications to future social and language studies. v vi Preface The book is designed for self-studies by researchers and practitioners, graduate andalsoundergraduatestudents,aswellassocialandlinguisticscientists.Themain contentsofthetextarecollectedfromtheauthors’ownresearchwork,inanatural combination with many others’ contributions, all being edited into a logical pre- sentation of the notion as a self-contained technical book. In so doing, all simu- lationshavebeenre-checkedwithallsimulationfiguresredrawninaunifiedformat. A rather comprehensive list of main references is provided for the reader’s verifi- cation and future studies. During the preparation of the manuscript, the authors received some helpful assistance from several individuals, especially Dr. Zhengping Fan who shared the source code of the multi-local network model and Mr. Jianfeng Zhou who shared the source code of the multi-language naming game model. All of them are acknowledged here with great appreciation. Hong Kong, China Guanrong Chen September 2018 Yang Lou Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Development Towards Applications. . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Abbreviations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Layout of the Monograph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1 Complex Networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.1 ER Random-Graph Network Model . . . . . . . . . . . . . . . . . 11 2.1.2 WS Small-World Network Model. . . . . . . . . . . . . . . . . . . 13 2.1.3 BA Scale-Free Network Model. . . . . . . . . . . . . . . . . . . . . 14 2.1.4 Multi-Local-World Network Model. . . . . . . . . . . . . . . . . . 15 2.2 Naming Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.1 Naming Game Framework . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.2 Minimal Naming Game . . . . . . . . . . . . . . . . . . . . . . . . . . 19 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Finite-Memory Naming Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Finite-Memory Naming Game. . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3.1 Simulation Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3.2 Convergence Time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.3 Memory Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.4 Convergence Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 vii viii Contents 4 Naming Game with Multi-Hearers or Group Discussions. . . . . . . . . 43 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Multi-Hearer Naming Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3 Naming Game with Group Discussions . . . . . . . . . . . . . . . . . . . . 49 4.3.1 Group Formation and Transmitted-Words . . . . . . . . . . . . . 50 4.3.2 Words Transmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.4.1 General Convergence Process of MHNG . . . . . . . . . . . . . 55 4.4.2 Convergence Time of MHNG . . . . . . . . . . . . . . . . . . . . . 56 4.4.3 Peak of Convergence Curve of MHNG. . . . . . . . . . . . . . . 59 4.4.4 General Convergence Process of NGG . . . . . . . . . . . . . . . 61 4.4.5 Convergence Time Analysis. . . . . . . . . . . . . . . . . . . . . . . 64 4.5 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5 Communications with Learning Errors . . . . . . . . . . . . . . . . . . . . . . 71 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.2 Communications with Learning Errors. . . . . . . . . . . . . . . . . . . . . 72 5.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.3.2 Convergence Processes . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.3.3 Convergence Time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.3.4 Maximum Number of Total and Different Words . . . . . . . 83 5.3.5 Convergence Thresholds . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.4 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6 Naming Game on Multi-Community Networks. . . . . . . . . . . . . . . . . 95 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.2 Multi-Local-World Networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.3 Simulation Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.3.1 Convergence Time Versus Number and Sizes of Local-Worlds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.3.2 Convergence Time Versus Rate of Initially Assigned Nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.3.3 Convergence Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.3.4 Discussion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.4 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 7 Multi-Word Naming Game. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.2 Multi-Word Naming Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Contents ix 7.2.1 Conventional Sentence Patterns . . . . . . . . . . . . . . . . . . . . 119 7.2.2 Local Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 7.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 7.3.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 7.3.2 Conventional English Language Patterns. . . . . . . . . . . . . . 124 7.3.3 Man-Designed Language Patterns. . . . . . . . . . . . . . . . . . . 130 7.4 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 8 Multi-Language Naming Game. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 8.2 Multi-Language Naming Game . . . . . . . . . . . . . . . . . . . . . . . . . . 136 8.3 Simulation Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 140 8.3.1 Simulation Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 8.3.2 Convergence Process and Analysis. . . . . . . . . . . . . . . . . . 142 8.3.3 Communication Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 8.3.4 Convergence Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 8.3.5 Maximum Numbers of Total and Different Words. . . . . . . 150 8.4 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Conclusions ... .... .... .... ..... .... .... .... .... .... ..... .... 155 Index .... .... .... .... .... ..... .... .... .... .... .... ..... .... 157