We study the ( )-color cyclic particle system on the one-dimensional integer lattice ( Z ), first introduced by Bramson and Griffeath (Ann Prob:26–45, 1989). In that paper they show that almost surely, every site changes its color infinitely often if ( 3,4 ) and only finitely many times if ( 5 ). In addition, they conjecture that for ( 3,4 ) the system clusters, that is, for any pair of sites x, y, with probability tending to 1 as (t ), x and y have the same color at time t. Here we prove that conjecture.
In the above setting, we recover the classical multitype voter model by taking @math to be the complete graph on @math . The @math -color cyclic particle system is obtained by letting @math be the directed cycle @math , where @math iff @math (mod @math ). Recently, Lanchier and Scarlatos @cite_4 studied the model on the vertex set @math in the case where @math is symmetric, i.e., @math iff @math . The authors give sufficient conditions for fluctuation, clustering and fixation to occur. In particular, they show that the process clusters if @math has radius 1, that is, there exists an opinion @math which is adjacent to all the other opinions in @math (Theorem 1.1 in @cite_4 ). In our case, @math is not symmetric and its radius is @math , so the result of Theorem captures a different phenomenon.
@cite_4
1551454402 2528943279 2170002160 2964292545
This article is concerned with a general class of stochastic spatial models for the dynamics of opinions. Like in the voter model, individuals are located on the vertex set of a connected graph and update their opinion at a constant rate based on the opinion of their neighbors. However, unlike in the voter model, the set of opinions is represented by the set of vertices of another connected graph that we call the opinion graph: when an individual interacts with a neighbor, she imitates this neighbor if and only if the distance between their opinions, defined as the graph distance induced by the opinion graph, does not exceed a certain confidence threshold. When the confidence threshold is at least equal to the radius of the opinion graph, we prove that the one-dimensional process fluctuates and clusters and give a universal lower bound for the probability of consensus of the process on finite connected graphs. We also establish a general sufficient condition for fixation of the infinite system based on the structure of the opinion graph, which we then significantly improve for opinion graphs which are distance-regular. Our general results are used to understand the dynamics of the system for various examples of opinion graphs: paths and stars, which are not distance-regular, and cycles, hypercubes and the five Platonic solids, which are distance-regular. We study a one-parameter family of discrete dynamical systems called the @math -color firefly cellular automata (FCAs), which were introduced recently by the author. At each discrete time @math , each vertex in a graph has a state in @math , and a special state @math is designated as the blinking' state. At step @math , simultaneously for all vertices, the state of a vertex increments from @math to @math unless @math and at least one of its neighbors is in the state @math . A central question about this system is that on what class of network topologies synchrony is guaranteed to emerge. In a previous work, we have shown that for @math , every @math -coloring on a finite tree synchronizes iff the maximum degree is less than @math , and asked whether this behavior holds for all @math . In this paper, we answer the question positively for @math and negatively for all @math by constructing counterexamples on trees with maximum degree at most @math . In this paper we consider a fundamental problem in the area of viral marketing, called T ARGET S ET S ELECTION problem. In a a viral marketing setting, social networks are modeled by graphs with potential customers of a new product as vertices and friend relationships as edges, where each vertex @math is assigned a threshold value @math . The thresholds represent the different latent tendencies of customers (vertices) to buy the new product when their friend (neighbors) do. Consider a repetitive process on social network @math where each vertex @math is associated with two states, active and inactive, which indicate whether @math is persuaded into buying the new product. Suppose we are given a target set @math . Initially, all vertices in @math are inactive. At time step 0, we choose all vertices in @math to become active. Then, at every time step @math , all vertices that were active in time step @math remain active, and we activate any vertex @math if at least @math of its neighbors were active at time step @math . The activation process terminates when no more vertices can get activated. We are interested in the following optimization problem, called T ARGET S ET S ELECTION : Finding a target set @math of smallest possible size that activates all vertices of @math . There is an important and well-studied threshold called strict majority threshold, where for every vertex @math in @math we have @math and @math is the degree of @math in @math . In this paper, we consider the T ARGET S ET S ELECTION problem under strict majority thresholds and focus on three popular regular network structures: cycle permutation graphs, generalized Petersen graphs and torus cordalis. We consider the problem of clustering a graph @math into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables @math , where @math is the incidence matrix of a graph @math , @math is the vector of unknown vertex variables (with a uniform prior), and @math is a noise vector with Bernoulli @math i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of @math is possible if and only the graph @math is connected, with a sharp threshold at the edge probability @math for Erdős-Renyi random graphs. The first goal of this paper is to determine how the edge probability @math needs to scale to allow exact recovery in the presence of noise. Defining the degree rate of the graph by @math , it is shown that exact recovery is possible if and only if @math . In other words, @math is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph @math , defining the degree rate as @math , where @math is the minimum degree of the graph, it is shown that the proposed method achieves the rate @math , where @math is the spectral gap of the graph @math .