Random Structures & Algorithms

Random Structures and Algorithms · 2006

For an arbitrary finite tree 𝑇 , we find the exact value of the worst-case stabilization time of majority dynamics on 𝑇 .We also prove that for a perfect rooted cubic tree 𝑇 with diameter 𝐷 and uniformly random initial opinions, the dynamics stabilizes in time 𝜏 ∈ (𝐷∕4, 𝐷∕3) with high probability. | IntroductionMajority dynamics is a fundamental process on networks where each node interacts with its neighbors by changing its opinion to match the opinion of the majority.This simply described, and natural model has been of interest in biophysics McCulloch and Pitts (1990), social psychology Yin et al. (2019) and computer science Alistarh et al. (2017).Formally, this process is described as follows.Initially each individual 𝑖 ∈ 𝑉 considered as a vertex of a graph 𝐺 on a (not necessarily finite) set of vertices 𝑉 has an initial opinion 𝜉 0 (𝑖) ∈ {-1, 1}.Then, at every time step 𝑡 ∈ ℕ, they adopt the majority opinion of their neighbors, that is,where 𝑁 𝐺 (𝑖) is the set of neighbors of 𝑖 in 𝐺.For convenience, we only consider graphs with odd degrees, soIt was proved by Goles and Olivos (1980) that the process stabilizes for every finite graph 𝐺.More formally, the following period two property holds true: For every vertex 𝑖 and all large enough 𝑡, 𝜉 𝑡+2 (𝑖) = 𝜉 𝑡 (𝑖).However, the question of estimating the time until stabilization Poljak and Turzík (1986), it is proven that, for every 𝐺 and everyIt is known, however, that for most graphs and most assignments of initial opinions, 𝜏 is much smaller: It was proven in Fountoulakis et al. (2020) that if 𝑝 ≫ 𝑛 -1∕2 then with high probability 1 𝜏 ∶= 𝜏(𝐺(𝑛, 𝑝); 𝜉 0 ) ≤ 4 for 𝜉 0 ∈ ----------------------------------------

Read the paper · More papers on PaperTik