Majority Voter Model for Information Diffusion

Abstract

A Majority Voter Model is a iterative process on graphs. Let G be a graph with a initial vertex colouring of n colours with the option of a vertex being uncoloured. The is a sequential process where once a vertex is coloured, it can no longer become uncoloured, and at each time step a vertex adopts the colour that occurs most frequently in its neighbourhood. We study two models that approach tie-breaking in a different way. In the event of a tie in the Conservative Majority Model, a vertex will conserve its current colour, and in the event of a tie in the Mixed Majority Model, a vertex will either conserve its colour if its current colour is in the majority or when its current colour is not present in the majority, the vertex will adopt the most preferred colour in the majority.

We classify the periodic configurations of the Conservative Model on paths, cycles, and toroidal grids. We also study the behaviour of uncoloured vertices. We introduce coalitions of colours that form under the model and determine some properties. We show that the removal of these coalitions does not affect the period of the conservative model. Additionally, when the initial configuration is random, we examine some threshold probabilities that ensure the survival of a colour on complete graphs and cycles. We find the period of both models and the length of their pre-period.