A Note on the Majority Dynamics in Inhomogeneous Random Graphs

Yilun Shang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

Abstract

In this note, we study discrete time majority dynamics over an inhomogeneous random graph G obtained by including each edge e in the complete graph Kn independently with probability pn(e). Each vertex is independently assigned an initial state +1 (with probability p+) or −1 (with probability 1−p+), updated at each time step following the majority of its neighbors’ states. Under some regularity and density conditions of the edge probability sequence, if p+ is smaller than a threshold, then G will display a unanimous state −1 asymptotically almost surely, meaning that the probability of reaching consensus tends to one as n→∞. The consensus reaching process has a clear difference in terms of the initial state assignment probability: In a dense random graph p+ can be near a half, while in a sparse random graph p+ has to be vanishing. The size of a dynamic monopoly in G is also discussed.
Original languageEnglish
Article number119
Number of pages17
JournalResults in Mathematics
Volume76
Issue number3
Early online date24 May 2021
DOIs
Publication statusPublished - 1 Aug 2021

Fingerprint

Dive into the research topics of 'A Note on the Majority Dynamics in Inhomogeneous Random Graphs'. Together they form a unique fingerprint.

Cite this