The Naming Games (NG) are agent-based models for agreement dynamics,peer pressure and herding in socio-economic networks, and protocol selection in autonomous ad-hoc sensor networks. We show that noise plays a vital role in turning the Markov Chain model into an ergodic one, the Noisy Naming Games (NNG), in which all multi-name states are recurrent and therefore persistent, compared to the original NG for which the single-name state is absorbing and all other states are only quasi-stable. We introduce a related Markov Random Field (MRF) and its Gibbs Sampler which yields a closed form expression in terms of the local specification of the MRF for the stationary distribution of the NNG. The Gibbs Sampler algorithm offers a enhanced method for community-detection in raw social interaction data such as Twitter and FaceBook in which the low Gibbs energy multi-name states correspond to significant community structures within a given social network. We also show that this algorithm requires only $O(m 2^{cm})$ calculations where $c, m$ are respectively the size of the fixed Names list of the NNG and the maximal degree of the network graph, to compute the MRF's local specification in terms of the neighborhood structure of the network graph, which is then reused in all sweeps of the Sampler. Authors: Weituo Zhang and Chjan Lim

 

CHJAN LIM

NOISY NAMING GAMES --- ENHANCED COMMUNITY DETECTION

 

Contributed Talk