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?

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.

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: