Concurrent conversation modeling and parallel simulation of the naming game in social networks

Abstract

The Naming Game is an effective self-organization model to understand the emergence of linguistic consensus and to investigate the system dynamics in a variety of phenomena over social networks of autonomous agents. The Naming Game is an effective description for the evolution of consensus despite the absence of any central coordination or specialized initialization even in large-scale networks. While the classical game is effective in description, it was defined with inherently sequential evaluation semantics over the entire network. Here, we develop a new concurrent model as a relaxation of the classical formulation and express it in a discrete event style of evaluation. Further, with the uncovered concurrency that was absent in the classical algorithm, we map the concurrent model to parallel discrete event simulation. Using a prototype implementation, we present an initial parallel performance study on networks containing hundreds of thousands of individuals, with a decrease in simulation time in the best-observed case from 4800 seconds down to 1400 seconds.