University of Hull

CSRG - Complex Systems

CSI

| CSI Technical Reports | Department of Computer Science | University of Hull |

Complex Systems

Complex Systems could be described as models or physical systems that exhibit a surprising sensitivity to either their controlling input parameters or to some non-linear combinational effect of the parameters. Most of the physical systems we encounter are non-linear and although we like to try to understand them in terms of linear behaving components, we are increasingly often having to turn to complex systems analysis methods.

Some systems are described as Complex and Adaptive - often systems that involve some inherent life or even intelligence. We are still exploring the full implications of "life" and "intelligence" in very simple models.

Research in this area looks at just how simple a system can be while still exhibiting behaviour inexplicable in terms of linear analysis. It is interesting to try to characterise systems in terms of their complexity. Our understanding of just what complexity actually is continues to develop. A useful set of ideas is related to the algorithmic information content (AIC) - or the information needed to unambiguously specify or describe a system. Ideas from computational complexity and indeed quantum computational complexity are playing important roles in this field. A closely related area is understanding emergence in systems, since emergent phenomena seem to particularly abound in complex and adaptive systems.

Emergence is one of those terms that is easy to start thinking about but is quite hard to pin down exactly. The generally accepted idea is of some phenomena or behaviour that "emerges" from a complex system in an unanticipated manner. As our understanding of complex systems grows however, we may decide that some phenomena are in fact expected after all, and are no longer mysteriously emergent. A useful and pragmatic definition of emergent phenomena are: those phenomena exhibited by a system that are unexpected a priori, based on the input parameters or information we put into a model or system. This is particularly pertinent to simulated systems for which we can and do formulate a microscopic model, and from which some unanticipated macroscopic phenomena emerges.

Emergence and Complex Systems have become topics of interest in recent years and are described with various degrees of success in several popular science books. Some of my favourite books in this area are:

Other useful books providing an introduction to related areas are:

The study of emergence in the context of simulation models involves finding ways of usefully identifying, classifying and preferably quantifying phenomena we might describe as emergent. We generally need to formulate a microscopic model system analytically, and try to implement or code it up as an efficient simulation. We then need to figure out what to measure or observe so we can capture any emergence. Sometimes this is very surprising indeed and we need to think up unusual things to measure from the overall system. There are techniques from condensed matter physics that are useful in analysing spatial structure and phase transitional emergent phenomena. Often we need to thoroughly investigate different initial model conditions and perhaps try to measure some macroscopic property over many different microscopic runs of our model system. Visualising the overall system is a great aid to deciding what is worth measuring in a model, and various rendering technologies can be used to give a static or animated picture of the system.

One emergent phenomena we have found is in our artificial life model. This is a microscopically formulated predator-prey model of semi-intelligent animat agents. These simulated "animals" interact in a spatial environment according to rather simple built-in rules. We expected to find growing clumps and the obvious sorts of simple and random shapes in a simulation. The spiral pattern and various spontaneous formations reminiscent of military attack and defence formations emerged. The image top right shows an emergent spiral of red predators and blue prey against a background of green corpses.

Understanding complexity impinges on some fairly deep philosophical ideas and consequently there is plenty of controversy about it. One can however make some pragmatic inroads into comparing different systems with some ad hoc metrics. Some useful books at a relatively accessible level are:

Our work in this area is centred around pragmatic ways to assign information content metrics or entropy functions. This involves considering the context for describing a system configuration - what is its state compared to the possible and probable states it might have in its context. Of particular interest is understanding the complexity of graph structures and other spatial arrangements found in systems such as artificial life models and network models.

As well as investigating quantifiable metrics and statistical properties, there are also various applications of complex networks such as: road traffic simulations; human traffic and building evacuation models; and overlay networks that arise from computational grids of services.


| CSI Technical Reports | Ken Hawick | Department of Computer Science | University of Hull |