Four-Color Outer Median Cellular Automata on Graphs

Outer median (OM) rules on cellular automata (CA) calculate the color of the next step of the active cell by looking at the neighbors of the active cell and taking the floor of the median of the colors of those neighbors. Then basic rules are applied on the resultant pairs: {active cell, floor of median of neighbors}. This effectively allows CA rules to be taken "off the lattice", whereby an active cell can have any number of neighbors and still have the same number of rules. Therefore, the CA translates naturally to application on a network of nodes (graph), each node representing an active cell, and the node neighbors representing the neighbors of the active cell. The node evolution is shown as an array plot, for 50 steps.


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


A set of 11 interesting four-color rules was provided for this Demonstration: {835410659, 165886556, 2586168012, 1853213473, 625101555, 793262014, 1215618935, 582466131, 2234605538, 31963262, 2751474038}
A sociogram is a graph that tries to emulate a social interaction network. These sociograms were built (by hand) to look like typical social networks such as those for Facebook friends or virus transmittal studies. A symmetric circulant graph was specifically chosen to compare against the irregular sociogram to illustrate the effects of these topological differences on the node evolutions. It is interesting to see that even with a symmetric circulant graph there is complex behavior, with the same rules sometimes producing complex, though different, behavior on different graphs with the same number of nodes.
You can also observe increasing likelihood of complexity with more nodes, though that is expected.
In the future, the author will be looking at outer median rules on graphs with respect to real-world models (mainly social interaction networks), perturbing the OM-ruled graphs, looking at "mass media"-like global neighbors, and so forth. The simplicity of the OM-ruled graphs is their power: they give one the ability to rework old-standard "Game of Life" models, inherently local or nonlocal only with very complex constraints, into something more naturally nonlocal.
This Demonstration was created as part of a project for the NKS Summer School 2008.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.

Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2018 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+