License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.140
URN: urn:nbn:de:0030-drops-74440
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7444/
Go to the corresponding LIPIcs Volume Portal

Mai, Tung ; Panageas, Ioannis ; Vazirani, Vijay V.

Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion

pdf-format:
LIPIcs-ICALP-2017-140.pdf (0.6 MB)

Abstract

Inspired by the work of Kempe et al. [Kempe, Kleinberg, Oren, Slivkins, EC 2013], we introduce and analyze a model on opinion formation; the update rule of our dynamics is a simplified version of that of [Kempe, Kleinberg, Oren, Slivkins, EC 2013]. We assume that the population is partitioned into types whose interaction pattern is specified by a graph. Interaction leads to population mass moving from types of smaller mass to those of bigger mass. We show that starting uniformly at random over all population vectors on the simplex, our dynamics converges point-wise with probability one to an independent set. This settles an open problem of [Kempe, Kleinberg, Oren, Slivkins, EC 2013], as applicable to our dynamics. We believe that our techniques can be used to settle the open problem for the Kempe et al. dynamics as well.

Next, we extend the model of Kempe et al. by introducing the notion of birth and death of types, with the interaction graph evolving appropriately. Birth of types is determined by a Bernoulli process and types die when their population mass is less than epsilon (a parameter). We show that if the births are infrequent, then there are long periods of "stability" in which there is no population mass that moves. Finally we show that even if births are frequent and "stability" is not attained, the total number of types does not explode: it remains logarithmic in 1/epsilon.

BibTeX - Entry

@InProceedings{mai_et_al:LIPIcs:2017:7444,
  author =	{Tung Mai and Ioannis Panageas and Vijay V. Vazirani},
  title =	{{Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{140:1--140:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7444},
  URN =		{urn:nbn:de:0030-drops-74440},
  doi =		{10.4230/LIPIcs.ICALP.2017.140},
  annote =	{Keywords: Opinion Dynamics, Convergence, Jacobian, Center-stable Manifold}
}

Keywords: Opinion Dynamics, Convergence, Jacobian, Center-stable Manifold
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI