2018/04/01 by Hamed Omidvar, Massimo Franceschetti, Omidvar, Hamed +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Distributed #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Opinion Dynamics and Social Influence #Parallel #Probability (math.PR) #Social and Information Networks (cs.SI) #Stochastic processes and statistical mechanics #and Cluster Computing (cs.DC) #cs.DC #cs.SI #math-ph #math.MP #math.PR
paper · pdf · doi:10.48550/arxiv.1804.00358
arXiv admin note: text overlap with arXiv:1811.10677 (arXiv:1811.10677 is an extension of this work by the same authors and these works share many parts.)
openalex publication_date 2018/04/01 · openalex created_date 2020/01/23 · arxiv created 2020/11/12 · arxiv updated 2020/11/13 · openalex updated_date 2026/07/28
We consider a long-range interacting particle system in which binary particles -- whose initial states are chosen uniformly at random -- are located at the nodes of a flat torus (ℤ/hℤ)2. Each node of the torus is connected to all the nodes located in an l_∞-ball of radius w in the toroidal space centered at itself and we assume that h is exponentially larger than w2. Based on the states of the neighboring particles and on the value of a common intolerance threshold τ, every particle is labeled "stable," or "unstable." Every unstable particle that can become stable by flipping its state is labeled "p-stable." Finally, unstable particles that remained p-stable for a random, independent and identically distributed waiting time, flip their state and become stable. When the waiting times have an exponential distribution and τ≤ 1/2, this model is equivalent to a Schelling model of self-organized segregation in an open system, a zero-temperature Ising model with Glauber dynamics, or an Asynchronous Cellular Automaton (ACA) with extended Moore neighborhoods. We first prove a shape theorem for the spreading of the "affected" nodes of a given state -- namely nodes on which a particle of a given state would be p-stable. As w → ∞, this spreading starts with high probability (w.h.p.) from any l_∞-ball in the torus having radius w/2 and containing only affected nodes, and continues for a time that is at least exponential in the cardinalilty of the neighborhood of interaction N = (2w+1)2. Second, we show that when the process reaches a limiting configuration and no more state changes occur, for all τ∈ (τ^*,1-τ^*) ∖ \1/2\ where τ^* ≈ 0.488, w.h.p. any particle is contained in a large "monochromatic ball" of cardinality exponential in N.