Detection of communities with Naming Game-based methods

PLoS One. 2017 Aug 10;12(8):e0182737. doi: 10.1371/journal.pone.0182737. eCollection 2017.

Abstract

Complex networks are often organized in groups or communities of agents that share the same features and/or functions, and this structural organization is built naturally with the formation of the system. In social networks, we argue that the dynamic of linguistic interactions of agreement among people can be a crucial factor in generating this community structure, given that sharing opinions with another person bounds them together, and disagreeing constantly would probably weaken the relationship. We present here a computational model of opinion exchange that uncovers the community structure of a network. Our aim is not to present a new community detection method proper, but to show how a model of social communication dynamics can reveal the (simple and overlapping) community structure in an emergent way. Our model is based on a standard Naming Game, but takes into consideration three social features: trust, uncertainty and opinion preference, that are built over time as agents communicate among themselves. We show that the separate addition of each social feature in the Naming Game results in gradual improvements with respect to community detection. In addition, the resulting uncertainty and trust values classify nodes and edges according to role and position in the network. Also, our model has shown a degree of accuracy both for non-overlapping and overlapping communities that are comparable with most algorithms specifically designed for topological community detection.

MeSH terms

  • Algorithms
  • Game Theory
  • Games, Experimental*
  • Humans
  • Linguistics
  • Memory
  • Models, Psychological
  • Names
  • Residence Characteristics

Grants and funding

This work was supported by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (http://www.capes.gov.br/), Grant number: AUXPE 3313/2014; Conselho Nacional de Desenvolvimento Científico e Tecnológico (http://cnpq.br/), Grant numbers: 303738/2013-8 and 143356/2011-9; and Fundação de Amparo à Pesquisa do Estado de São Paulo, Grant number: 2013/13447-3. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.