Jan Burian
honzaburian (at) seznam.cz
You can find here:
Intuitive definitions of complexity
Basics of (complex) systems science
Selforganization and related concepts
Formal definitions of complexity
Very short introduction to modeling methodology
System is an entity in terms of parts and relations between them.
Complex system (complex comes from Latin com together + plectere to twine or braid) is a system composed from relatively many mutually related parts.
Complex systems are usually (but not always) intricated  hard to describe or understand.
Examples of complex systemsParts of human society:
 Markets
 Organizations
 Language
 Internet
Biology:
 Cells
 Organ – e.g. brain
 Immune system
 Organisms
 Populations
 Ecosystem
Physics:
 Turbulence
 Weather
 Percolation
 Sandpile
The world consists of many complex systems, ranging from our own bodies to ecosystems to economic systems. Despite their diversity, complex systems have many structural and functional features in common that can be effectively simulated using powerful, userfriendly software. As a result, virtually anyone can explore the nature of complex systems and their dynamical behavior under a range of assumptions and conditions. (M. Ruth, B Hannon, Dynamic Modeling Series Preface)
Structurally complex system
A system that can be analyzed into many components having relatively many relations among them, so that the behavior of each component can depend on the behavior of many others. (Herbert Simon)Remember: The number of relationships could be much higher than the number of components!
Dynamically complex system
A system that involves numerous interacting agents whose aggregate behaviors are to be understood. Such aggregate activity is nonlinear, hence it cannot simply be derived from summation of individual components behavior. (Jerome Singer)
System types  Simple structure  Complex structure 
Simple dynamics  Example: Pendulum Model: Analytical  differential equations 
Example: Closed reservoir of gas 
Complex dynamics 
Example: Double
pendulum 
Example: Ant
pile 
Remember: Interconnection of parts matters in complex systems!
Reductionism: The properites of the whole system could be explained in terms of its parts.  Holism : The whole system cannot be determined or explained by its component parts alone. Instead, the system as a whole determines in an important way how the parts behave. 


Pragmatic approach rests on a combination of both reductionism and holism.
The basic rules of the complex systems could be paradoxically very simple, but their effects are intricate and unexpected because of feedback relations between parts.
Feedback
The return of a portion of the output of a process or system to the input.
State space (phase space) is an abstract space in which all possible states of a system are represented, with each possible state of the system corresponding to one unique point in the state space. Dimensions of state space represent all relevant parameters of the system. For example state space of mechanical systems has six dimensions and consists of all possible values of position and momentum variables.
Dynamics of the system is the set of functions that encode the movement of the system from one point in the state space to another.
Trajectory of the system is the sequence of system states.
Fixed point is a point in the state space where the system is in equilibrium and does'nt change.
Attractor is a part of the state space where some trajectories end.
Attractor typesFixed point
Limit cycle
Strange attractor
Dynamical systems can often be modeled by differential equations dx/dt=v(x), where x(t)=(x1(t), …, xn(t)) is a vector of state variables, t is time, and v(x)=(v1(x), …, vn(x)) is a vector of functions that encode the dynamics. For example, in a chemical reaction, the state variables represent concentrations. The differential equations represent the kinetic rate laws, which usually involve nonlinear functions of the concentrations. Such nonlinear equations are typically impossible to solve analytically, but one can gain qualitative insight by imagining an abstract ndimensional state space with axes x1, …, xn. As the system evolves, x(t) flows through state space, guided by the ‘velocity’ field dx/dt = v(x) like a speck carried along in a steady, viscous fluid. Suppose x(t) eventually comes to rest at some point x*. Then the velocity must be zero there, so we call x* a fixed point. It corresponds to an equilibrium state of the physical system being modeled. If all small disturbances away from x* damp out, x* is called a stable fixed point — it acts as an attractor for states in its vicinity. Another longterm possibility is that x(t) flows towards a closed loop and eventually circulates around it forever. Such a loop is called a limit cycle. It represents a selfsustained oscillation of the physical system. A third possibility is that x(t) might settle onto a strange attractor, a set of states on which it wanders forever, never stopping or repeating. Such erratic, aperiodic motion is considered chaotic if two nearby states flow away from each other exponentially fast. Longterm prediction is impossible in a real chaotic system because of this exponential amplification of small uncertainties or measurement errors. (Strogatz, 2001)
Example: The predatorprey model
We study the dynamics of mutually dependent population size of predators and prey.
The model is supported by analyses of 100 year fur trapping records of the Hudson's Bay Company.
Animation of the system dynamics and the two differential equations governing the dynamics (LotkaVolterra equations). X represents the size of hare population and Y the size of lynx population.
The portrait of dynamics for different initial x and y parameters forms a fractal.
More information about this fractal.
There are many formal definitions of complexity available. Only a small portion of them is suitable for description of complex systems. There are two particular notions of complexity which are not suitable for description of complex systems but have very good sense in other domains.
Good measures of system complexity should measure the amount of regularities in the system (and not its randomness). Such measures should be low for both very simple systems (where is only one or very few dominant regularities) and random systems (where are almost no regularities). Such measures are called nonmonotonic. We can say that they are somewhere between order and randomness  on the „edge of chaos“ (Langton, 1990).
Neural complexity (Sporns et al., 2000, 2002) is a measure inspired by the cognitive processes in the brain. It measures how much the change of activity in one part of he network changes the activity in other parts. The authors described it shortly as a measure of "the difference that makes difference". Neural complexity is one of many complexity measures based on mutual information.
Mutual information between two parts of a system is defined:
MI(Xjk,, XXjk) = H(Xjk) + H(X Xjk) – H(X)
There X is the system, Xjk is the jth permutation of a part of size k and XXjk is the rest of the system.
Neural complexity is formally the sum of average mutual information between subsets of the system and the rest of the system
The neural anatomy, neural activity, EEG signal and neural complexity of the brain of an old (a), adult (b) and very young (c) cat. In the old cat there are mostly local specialized connections present but the global integrative connections are missing due to degenrative processes, the result is rather random dynamics. In the adult cat there are both local and global connections present, the result is complex dynamics. In the young cat the local connections are not developed yet but the global connections are already present, the result is regular dynamics (Edelman & Tononi, 2000).
The statistical complexity (Shallizi 2001, 2003, 2004) reflects the intrinsic difficulty of predicting the future states of the system from the system history. It is the amount of information needed about the past of a given point in order to optimally predict its future. Systems with a high degree of local statistical complexity are ones with intricate spatiotemporal organization. Statistical complexity is low both for highly disordered and triviallyordered systems.
Selforganization (First used by Ashby in 1948.). The ability of the system to autonomously (without being guided or managed by an outside source) increase its complexity.
If a local system is an open system receiving relatively stable and appropriate amount of energy from its environment and the local system is composed from sufficient number of parts which are able to interact through positive and negative feedback, there could (depending on some parameters) be established relatively stable network of feedback loops. This process is called selforganization and the established dynamic network is called selforganized system.
Examples of selforganisation:
In Physics:
Benard cells  coherent motion of large number of molecules in heated liquid layers.
BelousovZhabotinsky reactions  a specific "coctail" of chemical ingredients loops through visualy discernable states when it receives thermal (heated) or mechanical (stirred) energy.
In Biology:
Flocking  a group of organism can selforganise in a relatively coherent whole which is able to synchronously react on external stimuli.
Ants demo  increasing the length
of pheromone trace or the number of ants would lead to selforganization
of the food track (result of stigmergic interaction between agents
and environmnent).
An ecosystem or a whole biosphere  the
feedback loops between environment and organism could lead to
stabilisation (homeostatis) of some environmental parameters.
Traditional definition of emergence
The arising of characteristics of the whole which cannot be attributed to the parts. There arise new qualitative and not only quantitative changes. Very vaguely: the whole is more than sum of it parts (an statement made already by Aristotle in Metaphysics).Modern definition
Common characteristics of emergence:
Emergence is „the arising of novel and coherent structures, patterns and properties during the process of selforganization in complex systems." (Corning, 2002; Goldstein, 1999)
 Radical novelty (features not previously observed in the system)
 A global or macro “level” (i.e., there is some property of “wholeness”)
 Coherence or correlation (integrated wholes that maintain themselves over some period of time)
 It is the product of a dynamical process (it evolves)
 It is meaningfull for us (i.e. has some pragmatic value for us – we can use it).
Weak emergence: new properties arising in systems as a result of the interactions at an elemental level. The causal conection between the interactions of the parts and the properties of the whole can be traced in great detail.
In many cases the relationship between parts and the whole depends on large scales of space and time.
Domain  Elementary level  Global level 
Geography  Flow of water  Shape of the river bed 
Brain  Neuronal firing  Synaptical changes 
Organism  Behaviour in specific situations  Ontogeny 
Evolution  Life of an individual  Phylogeny 
Language  Speech acts  Development of language 
Economy  Activity of microeconomical subjects  Macroeconomical properties 
Strong emergence: the properties of the whole supervene on the properties of the parts. Supervenience describes causal dependence between sets of properties. If property B is causaly dependent on property A, it means that one state of property B could be caused by many states of property A, but one state of property A causes exactly one state of property B.
Problems
The combined (cooperative) effects that are produced by two or more particles, elements, parts or organisms – effects that are not otherwise attainable. (Corning, 2002)
Example: Lichen and other symbiotic organisms
Adaptability is the ability of a system to maintain its complexity in changing environment. Often we can find a feedback between system and its environment.
System types  Constructed  Selforganized 
Nonadaptable  Example: Classical machines  Example: Crystals 
Adaptable  Example: Adaptable robots  Example: Living organisms 
Models:
NetLogo
Daisy world model
Generalized
model at NANIA
History
Characteristics
Basic description of a simple cellular automaton (CA) as presented in
(Wolfram, 2002).
This book is available
on internet and represents a good introduction to cellular
automatons (and other simple automatons with complex behavior) but it
also gained bad reputation due its egocentric tone.
Basic types of rules
Totalistic  the state of the cell is dependent on the sum of neighboring cells with specific states (as in the Game of Life  see the next chapter)
Different rules produce very different behavior.
Four classes of behavior in 1D CA (Wolfram,
1983)


Uniform

Repetitive

Random

Complex

Types of 2D neighborhood


von Neumann

Moore

Hexagonal

Game of Life
From the five cells on the left (so called Fpentomino) evolved one hundred steps a complex pattern.
Left: An example of an complex oscilator in Life (Gosper's glider gun). Right: Turing machine implemented in Life (Rendell, 2005).
Selfreplication was first investigated by von Neumann in 1940s. The von Neumann selfreproducing automata is actually a universal constructor' that constructs "any machine'' in its 29state cellular space. In particular, it is capable of Turing universal computation. It solves the selfreproduction problem by reading a tape containing instructions on how to build a copy of itself, provides the copy with a copy of its own input tape, and then presses the ON button starting the copy in operation. In the 1980s, C. Langton and then J. Byl showed that in fact much smaller automata can in fact selfreproduce.
Langton's selfreplicating loop

CA rule 110


A seashell with CAlike patterns
Mireks's Java Cellebration  one of the best CA tools
Game of Life and Cellular automaton on Wikipedia
CA Tutorial by Alexander Schatten,
"History of Cellular Automata" from Stephen Wolfram's "A New Kind of Science"
General article about Cellular Automata by Cosma Shallizi
The DDLab manual by Andy Wuensche with many information about CA, discrete dynamical networks and their attractor basins.
In CA there was interaction possible only between neighbouring cells in a spatial matrix. But the interaction between active parts of a system could be generally described by a network where the active components are represented by nodes and the interactions by edges. Complex networks are a subgroup of networks with "interesting" properties. Natural and social networks are often complex.
Motivation for the study of complex networks:
Examples of complex networks



The 1318 transnational corporations that form the core of the economy. (Vitali S. et al., 2011) Structure of internet (nodes  servers, edges 
connections) 
Biology

Structure of yeast protein interactions (nodes  proteins, edges  reactions) (Barabasi et. al., 2003) Macaque cortex network (Young, 1993) 
For more examples see Gallery of network images
Some properties of complex networks:
Types of complex networks (Huang, 2005)


Random network 
Small World network 
Scalefree network 
Comparison between the degree distribution of scalefree networks (circle) and random graphs (square) having the same number of nodes and edges. For clarity the same two distributions are plotted both on a linear (left) and logarithmic (right) scale. The bellshaped degree distribution of random graphs peaks at the average degree and decreases fast for both smaller and larger degrees, indicating that these graphs are statistically homogeneous. By contrast, the degree distribution of the scalefree network follows the power law, which appears as a straight line on a logarithmic plot. The continuously decreasing degree distribution indicates that lowdegree nodes have the highest frequencies; however, there is a broad degree range with nonzero abundance of very highly connected nodes (hubs) as well. Note that the nodes in a scalefree network do not fall into two separable classes corresponding to lowdegree nodes and hubs, but every degree between these two limits appears with a frequency given by P(k). (Albert, 2005) 
The Potential Implications of ScaleFree Networks (Barabasi et al., 2005):
Chapter about networks in Complex Science for a Complex World.
Exploring complex networks, an article by Strogatz in Nature.
Scalefree networks, an article by Barabasi and Bonabeau in Scientific American.
Models are always “wrong” but sometimes could be useful! (Georg E. P. Box)
A different look at logical relationship between a multiagent
model and reality:
Axelrod (2003) points out: “like deduction model starts with a set
of explicit assumptions. But unlike deduction, it does not prove
theorems. Instead, a simulation generates data that can be analyzed
inductively”. Induction comes at the moment of explaining the behavior
of the model. It should be noted that although induction is used to
obtain knowledge about the behavior of a given model, the use of a model
to obtain knowledge about the behavior of the real world refers to the
logical process of abduction. Abduction, also called inference to the
best explanation, is amethod of reasoning in which one looks for the
hypothesis that would best explain the relevant evidence, as in the case
when the observation that the grass is wet allows one to suppose that it
rained. (Encyclopedia of Complexity)
The term "agent" means an active, autonomous and situated unit.
ABM are a subclass of Multiagent systems (MAS). Typically in MAS agents could be biological or artificial entitities situated in a real world like a group of animals, group of cooperating robots or virtual entities situated in a nonsimulated environment like software agents acting in a computer network. In ABM agents are typically software objects (inter) acting in a simulated environment. ABM could be interpreted as models of realworld MAS.
Which features of real complex systems can we better understand with the help of ABM?
Prisoner's dilemma in game theory
Two agents decide between cooperation and noncooperation and are
rewarded after their decisions.
Three basic situations could arise:
Iterated prisonner's dilemma (IPD)
The decisions of agents are repeated and rewards accumulated.
The tournament of different playing strategies surprisingly
showed that the best strategy for IPD is very simple:
Tit for Tat: If you cooperate I also cooperate, if you don't cooperate
I also don't cooperate.
If we encode the strategies into a simple genome and evolve competing populations of these strategies the Tit for Tat strategy will evolve spontaneously and become dominant for a reasonable range of rewards.
Other examples:
Applications:
(Graphic by T. Eymann)
Aims of ACE (according to Tesfatsion):
ABM and microeconomical models share the bottomup approach but in other aspects they substantially differ.
In the process of formalizing a theory into mathematics it is often the case that one or more — usually many! — assumptions are made for purposes of simplification; representative agents are introduced, or a single price vector is assumed to obtain in the entire economy, or preferences are considered fixed, or the payoff structure is exactly symmetrical, or common knowledge is postulated to exist, and so on. It is rarely desirable to introduce such assumptions, since they are not realistic and their effects on the results are unknown a priori, but it is expedient to do so. ... it is typically a relatively easy matter to relax such ‘heroic’ assumptionsofsimplification in agentbased computational models: agents can be made diverse and heterogeneous prices can emerge, payoffs may be noisy and all information can be local.(Axtel, 2000)
Microeconomical models

ABM

analytical solutions

computational synthesis

looking for equilibrium

dynamical systems often without any equilibrium

description of behavior

emergent behavior

homogenous agents

nonhomogenous agents

based on variables

based on relations

For comprehensive overview see ACE web pages by Leigh Tesfatsion.
Two particularly interesting models implemented in NetLogo:
Artificial stock market by Carlos Goncalves
Model of market without intermediation by Michal Kvasnička
Advantages
Drawbacks
Examples of extremely simple NetLogo Forrest fire model and its modification for beginners.
Advantages
Drawbacks
For other ABM tools and more detailed comparation see http://en.wikipedia.org/wiki/Comparison_of_agentbased_modeling_software
A guide for newcomers to agent based modeling in the social sciences  by Robert Axelrod and Leigh Tesfatsion
ACE web pages by Leigh Tesfatsion
Agentbased modeling: Methods and techniques for simulating human systems by Eric Bonabeau
Seeing around corners  a popular article about ABM by Jonathan Rauch
Why agents? On the varied motivations for agent computing in the social sciences  an elaborated analysis of relations between ABM and classical analytical models, by Robert Axtell
From factors to actors: Computational sociology and agentbased modeling  sociological approach to ABM by Michael W. Macy and Robert Willer
Complexity of Cooperation Web  by Robert Axelrod
Twenty Years on: The Evolution of Cooperation Revisited  an overview by Robert Hoffmann
Albert, R. J Cell Sci 2005;118:49474957
Axelrod, R. (2003): Advancing the Art of Simulation in the Social Sciences. Japanese Journal for Management Information System, Special Issue on AgentBased Modeling, Vol. 12, No. 3, Dec. 2003.
Axelrod, R. (1987): The Evolution of Strategies in the Iterated Prisoner's Dilemma. In Lawrence Davis (ed.),Genetic Algorithms and Simulated Annealing. London: Pitman, and Los Altos, pp. 3241. available on WWW: < http://wwwpersonal.umich.edu/~axe/research/Evolving.pdf>.
Barabasi, A. L. Bonabeau, E. Scientific American. New York: May 2003. Vol. 288, Iss. 5; p. 60.
Cools, S.B., C. Gershenson, and B. D'Hooghe (2006): Selforganizing traffic lights: A realistic simulation. available on WWW: < http://uk.arxiv.org/abs/nlin.AO/0610040>.
Corning, Peter A. (2002), The ReEmergence of "Emergence: A Venerable Concept in Search of a Theory. Complexity 7(6): 1830
De Wolf, Tom & Tom Holvoet (2005), "Emergence Versus SelfOrganisation: Different Concepts but Promising When Combined", Engineering Self Organising Systems: Methodologies and Applications, Lecture Notes in Computer Science: 3464, 115. Available on WWW:< http://www.cs.kuleuven.be/~tomdw/publications/pdfs/2005esoa04lncs.pdf >.
Edelman, G. Tononi, G. Universe of consciousness. Basic Book. New York. 2000.
GellMann, M. What Is Complexity?. Complexity. 1995, Vol 1, no.1.
Huang, ChungYuan, Sun, ChuenTsai and Lin, HsunCheng (2005). Influence of Local Information on Social Simulations in SmallWorld Network Models. Journal of Artificial Societies and Social Simulation 8(4)8 http://jasss.soc.surrey.ac.uk/8/4/8.html.
J. Goldstein. Emergence as a Construct: History and Issues. Emergence 11: 1999, pp. 4972.
Hammond, R.A., Axelrod, R. (2005): The Evolution of Ethnocentrism. The Journal of Conflict Resolution. Beverly Hills: Dec 2006. Vol. 50, Iss. 6; pg. 926, 11 pgs.
Hoffmann, R. (2000): Twenty Years on: The Evolution of Cooperation Revisited. Journal of Artificial Societies and Social Simulation vol. 3, no. 2. Available on WWW:< http://jasss.soc.surrey.ac.uk/3/2/forum/1.html>.
Kauffman, S. (1995): At Home in the Universe: The Search for the Laws of SelfOrganization and Complexity. Oxford University Press.
Langton, C. G. Computation at the edge of chaos. Physica D, 42, 1990.
Lovelock, J.E.; Margulis, L. (1974). "Atmospheric homeostasis by and for the biosphere The Gaia hypothesis". Tellus 26 (1): 2–10.
Macy, W.M., Willer, R. (2002): From factors to actors: Computational sociology and agentbased modeling. Annual Review of Sociology; 2002; 28, pg. 143
61. Paul Rendell (2005). [online] . A Turing Machine in Conway's Game of Life. [cit. 1.5.2010]. Dostupné na WWW: < http://rendellattic.org/gol/tm.htm >.
Sporns, O. Tononi, G. and Edelman, G.M. Connectivity and complexity: the relationship between neuroanatomy and brain dynamics. Neural Networks, 13:909–992, 2000. available on WWW <http://php.indiana.edu/~osporns/nn connectivity.pdf>.
Sporns, O. Tononi, G. Classes of network connectivity and dynamics. Complexity, 7:28–38, 2002. available on WWW <http://php.indiana.edu/~osporns/complexity 2002.pdf>.
Shalizi, C. R. and Crutchfield, J. P. Computational mechanics: Pattern and prediction, structure and simplicity. Journal of Statistical Physics, 104:817–879, 2001. available on WWW: <http://arxiv.org/abs/condmat/9907176>.
Shalizi, C. R. Optimal nonlinear prediction of random fields on networks. Discrete Mathematics and Theoretical Computer Science, AB(DMCS):11–30, 2003. available on WWW: <http://arxiv.org/abs/math.PR/0305160>.
Shalizi, C. R. Shalizi, L. K. and Haslinger, R. Quantifying selforganization with optimal predictors. Physical Review Letters, 93:118701, 2004. available on WWW: <http://arxiv.org/abs/nlin.AO/0409024>.
Wuensche, A. Discrete Dynamical Networks and their Attractor Basins. In: Complex Systems '98. University of New South Wales, Sydney, Australia. 1998.
Wolfram, S. A New Kind of Science. Wolfram Media. 2002.
Young, L. The organization of neural system in the cerebral cortex. Proceedings of the Royal society. 1993, Series B, 252: 1318.
Brockman, J. (ed.). Třetí kultura. Academia. Praha. 2008.
Burian, J. Reaktivní multiagentní modely v ekonomii. Doktorská práce. VŠE Praha. 2010. Dostupné na WWW:< http://eldar.cz/cognition/complex/articles/burian_rACE.pdf >.
Burian, J. Multiagentní model transakčních nákladů na finančních trzích. In: Kvasnička, V. Kelemen, J. Pospíchal, J.(eds.). Kognice a umělý život VIII. 2008. Slezská univerzita. Opava. Dostupné na WWW:< http://eldar.cz/honza/articles/burian_ace_fin_market_tc.doc >.
Burian, J. Evoluce averze k riziku a nejistotě. In: Kvasnička, V. Kelemen, J. Pospíchal, J.(eds.). Kognice a umělý život VII. 2007. Slezská univerzita. Opava. Dostupné na WWW:< http://eldar.cz/honza/articles/burian_evoluce_averze.doc >.
Burian, J. Samoorganizace a kognice. In Kelemen, J., Kvasnička V. (eds.). Kognice a umělý život VI. Opava. Slezská univerzita v Opavě. 2005. Dostupné na WWW:< http://eldar.cz/honza/articles/burian_samoorganizae_kognice_final.doc>.
Capra, F. Tkáň života. Academia. Praha. 2004.
Havel, I.M. Přirozené a umělé myšlení jako filosofický problém In: Umělá inteligence III. (V. Mařík a kol., editoři), Academia, Praha 2001, s. 1775. Dostupné na WWW: < http://www.cts.cuni.cz/reports/1999/CTS9911.htm >.
Kauffman, S. Čtvrtý zákon. Paseka. Praha a Litomyšl. 2004.
Kubík, A. Inteligentní agenty. Grada. 2004.
Mandelbrot, B. Fraktály. Mladá fronta. Praha. 2003.
Mařík, V. Štěpánková, O. (Eds.) Umělá inteligence III (kapitola Umělý život). Academia. Praha. 2003.
Salamon, T. Design of AgentBased Models : Developing Computer Simulations for a Better Understanding of Social Processes. Repin, Czech Republic: Bruckner Publishing. 2011. WWW: <http://www.designofagentbasedmodels.info>
Highfield, R. Coveney, P. Mezi chaosem a řádem. Mladá Fronta. Praha. 2003.