Global majority consensus by local majority polling on graphs

摘要

We study a local majority algorithm, with two opinions, where nodes poll a subset of their neighbours and update their opinion to the opinion of the majority of the polled neighbours. We derive a condition on the number of neighbours to poll in order to ensure that the nodes end up in the state that was initially held by the majority of nodes. We also derive the time it takes the system to reach consensus. Our results are presented in the context of graphs with prescribed degree distribution and Erdos-Renyi graphs.