Problem 1: One-dimensional cellular automata

We’ll start with some 1-dimensional cellular automata (CA). For these, feel free to adapt the code we used in class.

Problem 1A) Consider the following rules for a 1-dimentional CA, which uses a neighborhood radius of 1 (i.e. each cell considers itself and the immediate neighbors to either side):

Which rule is this? Determine the binary number rule associated with this rule set. (Hint: if you don’t want to worry about figuring out the binary value by hand, this page may be useful.)


Problem 1B) Implement the model in python with an 8-cell 1-dimensional grid, with wrapped boundaries (i.e. a ring). Explore the network phase space for this rule, and highlight the attracting subcomponents.

In your write-up, be sure to include plots of each network component (i.e. basin of attraction), with the attracting sub-component highlighted in another color, as well as a description of the model dynamics for each component.


Problem 1C) Choose one of the configurations from the phase space to be the model initial condition, and plot the CA state over 20 timesteps. Be sure to note which initial configuration you chose.


Problem 1D) Choose one of the larger components/basins of attraction. Try out one of the centrality measures from the python NetworkX package (e.g. closeness or betweenness centrality are often nice examples). Plot the component and adjust the node colors based on the centrality score of each node. You can do this by setting (for example) node_color=list(nx.closeness_centrality(subg).values()) when you call nx.draw_networkx_nodes(). Which types of nodes appear to be highlighted by the centrality type you chose?


Problem 2: Two-dimensional cellular automata - Langton’s Ant


Figure 1. Simulation of the first 10500 steps of Langton’s Ant on a \(100 \times 100\) grid.

At the end of Chapter 7 in Think Complexity (p. 73), Downey discusses a class of CA variants known as “Turmites,” a type of two-dimensional Turing machine. He focuses specifically on a famous Turmite that has been shown to be Turing complete, called “Langton’s Ant”:

The most famous Turmite is Langton’s Ant, discovered by Chris Langton in 1986. See http://en.wikipedia.org/wiki/Langton_ant.

The ant is a read-write head with four states, which you can think of as facing north, south, east or west. The cells have two states, black and white.

The rules are simple. During each time step, the ant checks the color of the cell is it on. If it is black, the ant turns to the right, changes the cell to white, and moves forward one space. If the cell is white, the ant turns left, changes the cell to black, and moves forward.

Given a simple world, a simple set of rules, and only one moving part, you might expect to see simple behavior—but you should know better by now. Starting with all white cells, Langton’s ant moves in a seemingly random pattern for more than 10,000 steps before it enters a cycle with a period of 104 steps. After each cycle, the ant is translated diagonally, so it leaves a trail called the “highway.”

You can think about Langton’s Ant as either an agent moving across a grid, or a cellular automata, where the ‘ant’ cell is coded by including more colors in the cellular automata. In this framing, most cells are colored black or white, but each ‘ant’ is indicated by rules allowing more colors (eight colors representing an ant facing each of the four directions on either a black or white cell). (You can try implementing Langton’s ant from either perspective—if you choose a multicolor CA, think about how to convert the Langton’s ant rules into a set of cellular automata rules.)


Problem 2A) Write your own implementation of Langton’s Ant in Python. I’d recommend starting using PyCX for visualization or setting up your code so you visualize it after every step to start with, so that you can easily animate your ant as it explores the space (the PyCX voting model we looked at together in class may be a good starting point, or the majority rule cellular automata moodel). Use a grid size of at least \(11\times 11\), as this will contain the ant for 200 steps (you may choose if you want a wrapped or non-wrapped boundary). Start with all white cells (i.e. all 0’s), with the ant initially placed in the center facing north (up) (note the center position is \((5,5)\) in an \(11\times 11\) grid, since python indexes from 0). Simulate the first 200 steps of the ant and add the plot to your write-up.

A few notes for moving and plotting the ant, if you use imshow() to plot the grid:


Problem 2B) How many possible initial states/configurations are there for an \(11\times 11\) grid of Langton’s Ant (assuming a single ant)? You can work this out by figuring out how many possible configurations of black and white cells there are, and how many possible ways there are to place and orient the ant. How plausible is it to characterize the phase space network for such a system?


Problem 2C) Next, expand your grid size (to at least \(50 \times 50\)) and set the center \(3x3\) cells to an arbitrary configuration of black and white cells (you can choose one or assign it randomly). Simulate Langton’s ant using these conditions with a longer duration of your choice. What happens to the ant dynamics as time goes on? (Note that if you choose a very large grid and/or long time, it may take a few minutes to run this simulation.)


Optional Problem 2D) (This problem is not required! It’s just for fun if you’re interested.) Try setting the center \(3x3\) cells to random configurations of black and white cells, then run Langton’s ant for at least 10,500 steps. Do this for at least 100 initial configuration samples (or even all \(2^{3\times 3} = 512\) of them!). Does the ant always converge to a ‘highway’ pattern? In what fraction of runs does it converge to a highway within the simulation duration?

(Note that you probably don’t want to plot the ant live if you do this! You may want to just run the model to the final timestep and then show the final plot, otherwise the simulation time can be very long!)

This problem relates to an open (unsolved) question in cellular automata, whether Langton’s ant will always converge to the highway behavior for all finite initial conditions, or whether it is possible to see other long-term dynamics (i.e. is the highway the only type of attractor for Langton’s ant?). One piece of this problem has been solved—it is known that Langton’s ant will always have an unbounded trajectory,1 but it remains unknown whether it will always do so in a highway pattern.


Problem 3: Exploring network data

Next, let’s start exploring some networks and network data! If you’ve never used NetworkX before, the tutorial in the NetworkX documentation is a good way to get started. You can also look at the phase space network code we used before as an example to adapt.

First let’s import networkx and the other packages we’ll need:

from math import *
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx

Next, download the political books network data set from Mark Newman’s website. This network represents books about US politics published around the time of the 2004 presidential election and sold by Amazon.com, with (undirected) edges representing books frequently co-purchased by the same buyers (data from V. Krebs, unpublished). When you download and unzip the data, you should see a folder containing a Graph Modeling Language (.gml) file. We can read that file into NetworkX and make a new undirected graph like this:

g = nx.read_gml('polbooks/polbooks.gml')

If you’re working in Google Colab, you can upload the file to drive, or I’ve posted a copy on the course website that you can use like this:

# To load from a URL
import requests
import io

response = requests.get('https://epimath.org/misc/polbooks.gml') 
g = nx.read_gml(io.BytesIO(response.content))

First, let’s visualize the network. In NetworkX, we can set the network node positions with the spring layout algorithm, nx.spring_layout(). This approach treats each edge like a spring connecting the nodes, and lets the system evolve into final positions that usually look reasonably nice. Then we can draw the network:

pos=nx.spring_layout(g) # positions for all nodes
nx.draw_networkx(g, pos, with_labels = False, node_size = 100) # draw network
plt.show()

You can also try out other layouts and see how they look too!


Problem 3A) Degree distribution. Plot the degree distribution for this network. You can collect the degree sequence for the network with deg_seq = [d for n, d in g.degree()]. Try this first by plotting the degree distribution on a linear scale, then try it on a log-log scale. Does this degree distribution look scale-free to you? (Would you expect it to?)


Problem 3B) Centrality. Re-draw the network diagram, but this time highlight the nodes (i.e. adjust their color) based on one of the types of centrality available in NetworkX. Which nodes are most central using this type of centrality? What features does this centrality appear to be capturing?


Problem 3C) Political data & assortativity. Next, let’s explore the graph data—each node includes the the book title, as well as a categorization of the book as ‘liberal’ (marked with an l), ‘conservative’ (marked with a c), or ‘neutral’ (marked with an n). You can view the list of nodes using g.nodes(), and see the full data for each node with g.nodes(data=True). You may want to use n,v = g.nodes(data=True), which will allow you to access the nodes as n and the dictionary of data associated with each node as v.

Plot the network with the liberal/conservative/neutral nodes shown in different colors (e.g. blue/red/grey for typical US political party colors). You should hopefully get a plot something like:

Then, calculate the assortativity of the nodes based on their liberal/conservative/neutral political leanings. You can do this using the command nx.attribute_assortativity_coefficient(g, 'value'). How assortative are the books in the network based on their liberal, conservative, or neutral labels? What does this say about the book-purchasing habits of Amazon customers?


Problem 3D) Community structure. Finally, let’s examine the community structure of this network. We’ll use a modularity maximizing approach to find clusters of well-connected nodes, using the greedy_modularity_communities() function in NetworkX. This function is within the algorithms.community module of NetworkX, so we’ll call it like this: nx.algorithms.community.greedy_modularity_communities(g).

Find the communities within the network using the above approach, and then plot the network with each community colored a different color. How well do your communities align with the liberal/conservative/neutral labels on the nodes?


Problem 4: Developing your final project

Finally, this last problem is intended to help you start putting together ideas for the model you will be building for your course project.

Problem 4A) Topic details. Pick one or two topics that you are considering working on (they don’t have to be the same ones you listed before). Address the following in a couple of sentences (no more than 1 paragraph at most needed here—a sentence or two is good!):


Problem 4B) Literature review. Start exploring the literature for papers relevant to your topic. Are there other modeling papers that have addressed this topic? Are there papers with relevant data or reviews that you can use in building your model? Find two papers that might be useful and include the citations in your write-up.


Problem 4C) Potential approach. Lastly, sketch out some ideas on how you might translate your topic of interest into an ABM. This does not need to be final or fully thought out! Just a few sentances will be great, the main purpose of this is to get you started on thinking about how to build your model. Consider the following questions in your discussion:




  1. Kong, X.P., Cohen, E.G.D. Diffusion and propagation in triangular Lorentz lattice gas cellular automata. J Stat Phys 62, 737–757 (1991). https://doi.org/10.1007/BF01017981
    Bunimovich, L.A., Troubetzkoy, S.E. Recurrence properties of Lorentz lattice gas cellular automata. J Stat Phys 67, 289–302 (1992). https://doi.org/10.1007/BF01049035
    Gajardo, A., Moreira, A. and Goles, E., 2002. Complexity of Langton’s ant. Discrete Applied Mathematics, 117(1-3), pp.41-50.    ↩︎