A Note on the Majority Dynamics in Inhomogeneous Random Graphs

Shang, Yilun (2021) A Note on the Majority Dynamics in Inhomogeneous Random Graphs. Results in Mathematics, 76 (3). p. 119. ISSN 1422-6383

[img]
Preview
Text
Shang2021_Article_ANoteOnTheMajorityDynamicsInIn.pdf - Published Version
Available under License Creative Commons Attribution 4.0.

Download (483kB) | Preview
Official URL: https://doi.org/10.1007/s00025-021-01436-z

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.

Item Type: Article
Additional Information: Funding information: The work is supported by UoA Flexible Fund No. 201920A1001 from Northumbria University.
Uncontrolled Keywords: Random graph, majority dynamics, inhomogeneous graph.
Subjects: G100 Mathematics
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Elena Carlaw
Date Deposited: 20 May 2021 14:31
Last Modified: 31 Jul 2021 16:31
URI: http://nrl.northumbria.ac.uk/id/eprint/46235

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics