## 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):

• If all three cells in the neighborhood are 1’s, the center cell becomes a 0
• If 2 of the 3 cells in the neighborhood are 1’s, become a 1
• If precisely one of the neighbor cells are 1’s, and the center cell is a zero, become a 1
• If only the center cell is a 1, become a 0
• If all cells are 0’s, stay a 0

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.

• How many distinct basins of attraction are there?
• What behaviors does each basin of attraction exhibit? E.g. do all the initial conditions lead to a constant steady state, or does the system approach an oscillation? If it does oscillate, how long is the period of the oscillation?

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:

• If you generate your grid using a numpy array, e.g. config = zeros([n, n]), when you plot your current configuration with imshow(config), it will show the grid like this, where the first index indicates the row and the second indicates the column: $\begin{matrix} config[0,0] & config[0,1] & \cdots \\ config[1,0] & config[1,1] & \cdots \\ \vdots & \vdots & \ddots \\ \end{matrix}$

• Note that this affects both plotting and thinking about how the ant should move (i.e. when the ant moves north, how does that change the ant’s coordinates?)

• To plot the ant’s location as you go, you can use the matplotlib command scatter(), which includes plot markers for triangles facing each of the four cardinal directions (^,>,v,<). However, note that scatter() swaps the coordinates compared to imshow()! Here’s how I implemented the plot (but you can do it however you like!):

from pylab import *
imshow(config, cmap = cm.binary)
antmarker = {0:'^', 1:'>', 2:'v', 3:'<'}
scatter(ant[1], ant[0], s=100, c='red', marker=antmarker[ant[2]])
show()

where ant[0] is the first coordinate of the config numpy array (indicating rows, i.e. the y-value), ant[1] is the second coordinate, and ant[2] is the direction the ant is facing (0 is north/up, 1 is east/right, etc.)

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: