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

Inspired by the work of [Kempe, Kleinberg, Oren, Slivkins, EC13] we introduce and analyze a model on opinion formation; the update rule of our dynamics is a simplified version of that of Kempe et. al. 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. 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 et. al., 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 a parameter $\epsilon$. 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$.