Self-Replicating Graphs

In these adaptive graph models, the vertices reproduce, while highly connected vertices die. Although the rules are simple, the models can generate highly complex behavior—a single edge can grow and break into thousands of different self-replicating structures. Every time step, the graph is updated by performing the "reproduction stage" and then the "killing stage". In the reproduction stage, every vertex has an "offspring vertex" that is born with the same connections as its parent. In the killing stage, every vertex with more connections than the "degree cap" gets destroyed. In model 1, offspring inherit their parent's neighborhood. In model 3, there is an extra "umbilical" connection between parent and offspring.



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


The models are inspired by the growth of animal social networks. The reproduction stage is akin to springtime, when animals reproduce—having offspring with similar social relationships to their parents. The killing stage is akin to the winter time—when harsh conditions kill animals that share resources with too many neighbors. The rules behind the models are reminiscent of Conway's Game of Life, except these models generate their own space.
When the degree cap is large, the behavior can be highly complex. Consider model 1. When the degree cap is 4, a single edge grows (after three updates) to become a connected structure with 12 vertices. After another update, this structure breaks into four more edges, which continue self-replicating in the same way. When the degree cap is 10, a single edge eventually generates a vast "ecosystem" of 723 different structures that grow, change, and break into copies of one another. Some of the structures hold thousands of vertices. When the degree cap is infinite (i.e. pure reproduction, with no death), every bipartite graph will eventually appear as an induced subgraph of the resulting structure.
[1] R. Southwell and C. Cannings, "Some Models of Reproducing Graphs. III Game Based Reproduction," Applied Mathematics 1, 2010 pp. 334–342.
[2] R. Southwell and C. Cannings, "Games on Graphs That Grow Deterministically," GameNets, 2009 pp. 347–356.


    • 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+