Complex Systems

Complex Networks from Simple Rules Download PDF

Richard Southwell
Jianwei Huang
Information Engineering Department
The Chinese University of Hong Kong
Shatin, New Territories, Hong Kong,

Chris Cannings
School of Mathematics and Statistics
University of Sheffield
Sheffield, S3 7RH, UK


Complex networks are all around us, and they can be generated by simple mechanisms. Understanding what kinds of networks can be produced by following simple rules is therefore of great importance. This issue is investigated by studying the dynamics of extremely simple systems where a "writer" moves around a network, modifying it in a way that depends upon the writer's surroundings. Each vertex in the network has three edges incident upon it, which are colored red, blue, and green. This edge coloring is done to provide a way for the writer to orient its movement. The dynamics of a space of 3888 of these colored trinet automata systems are explored. A large variety of behavior is found, ranging from the very simple to the very complex. Our systems are studied using simulations (with appropriate visualization techniques) and selected rules are analyzed mathematically. An empirical classification scheme is arrived at, which reveals a lot about the kinds of dynamics and networks that can be generated by these systems.