In class, we discussed the way “technologies” spread throughout a network via a system of adoption. In the model, nodes adopt a technology if a sufficient fraction of their neighbors has adopted the technology. Although not applied to social networks, the mathematics of models like this has been studied since the 1940s. During his study of self-replicating machines, John von Neumann invented a class of discrete models known as cellular automata.

In a cellular automaton, nodes take on one of several discrete states dependent on the states of their neighboring nodes. Time is divided into discrete increments so that each node’s state at time t is a function of its neighbors’ states at time t-1. Two-dimensional cellular automata can be represented as a grid Each space on the grid is a node, and nodes bordering each other on the grid are neighbors. The nodes’ states can be represented by colors. At each time step, the grid is redrawn according to some update rule, which is essentially some variant of the “switch to A if a q fraction of my neighbors have adopted A” rule we discussed in class. At each node, the rule is run against the grid’s state before any nodes are updated. Every node updates its state at the same time, so the pattern on the grid is dependent only on the grid’s state at the previous time step, not on the order in which nodes are updated.

Many different configurations and rules have been studied, but one known as the Game of Life has risen to especial prominence. Invented by John Conway in 1970, Conway’s Game of Life, the Game of Life, or just Life, is particularly relevant to our discussion because, to some degree, it simulates actual population growth and death. Life is “played” on a square grid, like ordinary graph paper, and each node, or cell, can take on one of two states: “dead” or “alive”. Each cell has eight neighbors. If a dead cell is surrounded by a sufficient fraction of live cells, it becomes alive. If, however, a live cell is surrounded by too many or too few other live cells, it dies from overcrowding or loneliness. Conway worked out the fractions carefully so that the population of cells will change unpredictably—neither dying out rapidly nor saturating the grid. The rules are as follows:

• a dead cell with three neighbors becomes alive
• a live cell with fewer than two neighbors dies
• a live cell with more than three neighbors dies
• a live cell with exactly two or three neighbors lives

A more thorough description of Life, as well as an interactive Java applet implementation, can be found at http://www.math.com/students/wonders/life/life.html.

The truly remarkable property of Life is that it exhibits emergent behavior. Conway did not design the rules of the game to produce a specific outcome, and the rules themselves do not explicitly code for any particular behavior. However, fairly trivial patterns exhibit striking behavior. The above page describes patterns known as oscillators, which repeat after some number of steps; gliders, which propagate themselves across the grid forever; and guns, which repeatedly produce gliders. When these and other basic patterns are strung together, they give rise to far more complex behavior. In fact, it has been proven that it is possible to construct an entire computer within a Life pattern, which is certainly not obvious from the game’s simple definition.