Majority dynamics and the median process: Connections, convergence and some new conjectures

被引：3

作者：

Amir, Gideon ^{[1
]}

Baldasso, Rangel ^{[1
]}

Beilin, Nissan ^{[1
]}

机构：

[1] Bar Ilan Univ, IL-5290002 Ramat Gan, Israel

来源：

STOCHASTIC PROCESSES AND THEIR APPLICATIONS | 2023年 / 155卷

基金：

以色列科学基金会;

关键词：

Majority dynamics; Median process; FIXATION; GRAPHS; MODELS;

D O I：

10.1016/j.spa.2022.10.015

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We consider the median dynamics process in general graphs. In this model, each vertex has an independent initial opinion uniformly distributed in the interval [0, 1] and, with rate one, updates its opinion to coincide with the median of its neighbors. This process provides a continuous analog of binary majority dynamics. We deduce properties of median dynamics through this connection and raise new conjectures regarding the behavior of majority dynamics on general graphs. We also prove these conjectures on some graphs where majority dynamics has a simple description.(c) 2022 Published by Elsevier B.V.

引用

页码：437 / 458

页数：22

共 26 条

[1] Local Majority Dynamics on Preferential Attachment Graphs
Abdullah, Mohammed Amin
Bode, Michel
Fountoulakis, Nikolaos
[J]. ALGORITHMS AND MODELS FOR THE WEB GRAPH, (WAW 2015), 2015, 9479 : 95 - 106
[2] Global majority consensus by local majority polling on graphs of a given degree sequence
Abdullah, Mohammed Amin
Draief, Moez
[J]. DISCRETE APPLIED MATHEMATICS, 2015, 180 : 1 - 10
[3] Percolation in majority dynamics
Amir, Gideon
Baldasso, Rangel
[J]. ELECTRONIC JOURNAL OF PROBABILITY, 2020, 25
[4] SITE RECURRENCE FOR ANNIHILATING RANDOM-WALKS ON ZD
ARRATIA, R
[J]. ANNALS OF PROBABILITY, 1983, 11 (03) : 706 - 713
[5] Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
Benjamini, Itai
Chan, Siu-On
O'Donnell, Ryan
Tamuz, Omer
Tan, Li-Yang
[J]. STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2016, 126 (09) : 2719 - 2733
[6] Camia F, 2002, PROG PROBAB, V51, P163
[7] Phase ordering after a deep quench: the stochastic Ising and hard core gas models on a tree
Caputo, Pietro
Martinelli, Fabio
[J]. PROBABILITY THEORY AND RELATED FIELDS, 2006, 136 (01) : 37 - 80
[8] Fast Consensus for Voting on General Expander Graphs
Cooper, Colin
Elsaesser, Robert
Radzik, Tomasz
Rivera, Nicolas
Shiraga, Takeharu
[J]. DISTRIBUTED COMPUTING (DISC 2015), 2015, 9363 : 248 - 262
[9] Probabilistic consensus via polling and majority rules
Cruise, James
Ganesh, Ayalvadi
[J]. QUEUEING SYSTEMS, 2014, 78 (02) : 99 - 120
[10] Zero-temperature Glauber dynamics on the 3-regular tree and the median process
Damron, Michael
Sen, Arnab
[J]. PROBABILITY THEORY AND RELATED FIELDS, 2020, 178 (1-2) : 25 - 68

← 1 2 3 →