While a lot of models with deterministic rules give rise to interesting results, for example Wolfram’s elementary cellular automata, it is also possible to produce lattice models that incorporates both some form of algorithmic rule set akin to cellular automata and stochasticity. For example, in the simplest variant of the Metropolis algorithm for solving the 2D lattice Ising model, at each iteration one picks a spin at random and flips it to favor a decrease in total energy, with a probability of flipping it regardless of not meeting the objective. In this post, we discuss a model similar to how the Ising model but with a slightly different rule set that is more relatable in the context of social systems: the classical voter model.

The classical voter model [1] essentially takes a set of agents that take a particular state (like spins in the Ising model) and allows the agents to interact leading to a change in state, similar to how people may influence each other to change opinion. In the case of agents in a 2D lattice, interaction occurs between nearest neighbor agents. Algorithmically, the rules are as follows:

  1. An agent is selected randomly
  2. Another agent is selected randomly among the nearest neighbor agents.
  3. The agent in 1 takes the state of the agent in 2

The algorithm is simply repeats the process above until it converges to a stable or meta-stable state. Running the algorithm in a lattice that is initialized randomly is shown below.

Fig1 Fig. 1: Animation of one simulation of the classical voter model from a randomly-initialized lattice. Initialization is such that individually each cell has a probability of starting as state 0 (purple) with probability 0.3, and state 1 (yellow) with probability 0.7.

We observe that in this simulation, the population of state 0 agents tends to decrease and form small but mobile clusters. We may be tempted to say that state that has the larger population will always dominate the system after simulating for some time, but running the model several times present another picture.

Fig2 Fig. 2. Trajectory of the population of state 0 (black) and 1 (red) after simulating for 20000 time steps, with the darker lines indicating the mean population of each trajectory at that time step.

Here, we instead see that while there are cases where the less populous state decreases through time, there are also other realizations where the system equilibriates in population or the less populous state even overtaking the more populous state. It is here where the the stochasticity of the model plays a bigger role: we can get different trajectories/outcomes even when the conditions for initialization is similar. This is contrast to deterministic cellular automata which have exact or at least similar outcomes after simulating. Considering that population outcomes differ across realizations of the same model, we instead look into the dynamics of the model and compare it to what we usually expect from a similar spin model, the Ising model. We initialize the system as a droplet, where agents of one state are confined to a circle, and all other agents are outside this circle.

Fig3 Fig. 3. Animation of one simulation of the voter module, but initialized from a droplet, i.e. agents of a particular state are confined within a circle.

In this case, we observe that the circle tends to dissolve, contrast to the ferromagnetic Ising model where the tendency of solid clusters of spins tend to stay in place as it such state has a lower energy [2]. To illustrate the difference, consider a single cell with only 1 of its nearest neighbors having the same state while the other 3 has the opposing state. In the Ising model, the cell is guaranteed to flip state as it decreases the total energy, but for the voter model the cell has 25% probability to still retain it state. The difference in the rules of interaction leads to different dynamics. One interesting extension to the classical voter model is factoring in a time scale to the interaction process. While we have the notion of dynamics of the model as it progresses through each time step, we do not particularly know how fast these processes occur (which may be in minutes, days, or years). Usually, people assume that the process is roughly uniform that is proportional to the population of interacting agents [3]. Instead, we use an algorithm that gives a probabilistic but consistent time scale into the process: the Gillespie algorithm [4]. The Gillespie algorithm can be broken down to the following processes [5]:

  1. an agent is selected based on its propensity, or the likelihood that the agent taking a particular state will undergo a process (i.e. react)
  2. the agent performs the reaction
  3. a duration or time scale is assigned to the current time step by drawing from an exponential distribution that is proportional to its propensity and other relevant parameters.

The rules above are repeated similar to algorithm we previously performed. For the voter model, we choose the propensity of the process to be proportional to the population of each state, which makes it similar to simply picking an agent at random (mean-field case). Running the model gives us non-uniform time steps that are spaced based on the exponential distribution.

Fig4 Fig. 4. (Left) Population trajectory for the first few time steps, and (right) inter-event distribution of the voter model run with time scales determined by the Gillespie algorithm.

However, since the process are identically distributed from the same exponential distribution and the process is iterated with many time steps, the end time of each realization are close with each other. The benefit we get is that instead of time steps, we get the trajectory of the population based on actual time.

Fig5 Fig. 5. Trajectory of the population of state 0 (black) and 1 (red) after simulating for 20000 time steps but with time scaled determined by the Gillespie algorithm, with the darker lines indicating the mean population of each trajectory at that time step.

In conclusion, we have demonstrated the classical voter model on a lattice as a probabilistic cellular automata process unlike typical deterministic cellular automata, and show the its dynamics based on state population and how each state propagates across the lattice. In addition, we have shown that it is possible to add a particular time scale to the process by using the Gillespie algorithm, which can make an algorithmic simulation (based on time steps) model processes much closer based on the time scale it occurs. There are several ways to extend the results above. Cellular automata can be performed in topologies other than a 2D lattice, making interaction go beyond nearest neighbor. For voter models in particular, the process is run over complex networks that are taken from existing social networks. For the time scales, it is possible to used propensities that are either calibrated to observed propagation of opinion, or use propensities that are not exactly proportional to state population, i.e. minority opinions are more likely to propagate. In either case, we have shown that such approach using CA and the Gillespie algorithm presents interesting results.

References:

  1. Clifford, P., & Sudbury, A. (1973). A model for spatial conflict. Biometrika, 60(3), 581-588. (doi: https://dx.doi.org/10.1093/biomet/60.3.581)
  2. Redner S. (2012) Dynamics of Voter Models on Complex & Simple Networks. Mathematical Physics of Complex Networks (MAPCON), MPI Dresden (slides: https://www.pks.mpg.de/~mapcon12/Slides/Redner_Mapcon12.pdf)
  3. Sood, V., Antal, T., & Redner, S. (2008). Voter models on heterogeneous networks. Physical Review E, 77(4), 041121. (doi: https://dx.doi.org/10.1103/PhysRevE.77.041121)
  4. Gillespie, D. T. (1977). Exact stochastic simulation of coupled chemical reactions. The journal of physical chemistry, 81(25), 2340-2361. (doi: https://dx.doi.org/10.1021/j100540a008)
  5. Gibson, M. A., & Bruck, J. (2000). Efficient exact stochastic simulation of chemical systems with many species and many channels. The journal of physical chemistry A, 104(9), 1876-1889. (doi: https://dx.doi.org/10.1021/jp993732q)