The thermodynamical paradox

Self-organizing systems not reaching an equilibrium retain their low entropy by exporting high entropy to the environment.

Bifurcation

There may be several possible stable configurations of the system, and which it enters is based on fluctuations between unstable states early on. This branching between possible states is called bifurcation.

Organizational closure

When the system can maintain its structure despite external stimuli, it has organizational closure. That is, the system is self-sufficient through rigid internal stimuli loops. Despite this, such a system will often exchange energy or matter with the external system.

Far-from-equilibrium dynamics

Far-from-equilibrium dynamics denotes systems that don't stabilize in a minimum energy state, but rather depend on an external energy input in order to maintain their self-organization. An example of this is Bénard rolls, where heat is required in order for the water to maintain the movement. This makes the system fragile because of its dependence on the environment, but also more capable to react to external changes.

Sampling bias

• K^N: Total number of transition functions
• n: Number of those transition functions leading to the quiescent state

Then the degree of chaos can be approximated by

lambda = (K^N - n) / K^N

where lambda = 0 means all transition functions lead to the quiescent state. Note that the same lambda value will give different behaviour at different configurations of a CA, so it cannot be used as a fixed value for creating emergent behaviour.

Sampling strategies

Using the bias defined in the previous subsection, two sampling strategies are proposed:

• Random-table method: Pick transition functions iteratively, where lambda is the probability of picking a transition function not leading to the quiescent state
• Table-walk-through: Start with an initial set of transition functions leading to the quiescent state, and randomly replace entries with a transition function not leading to the quiescent state until lambda is correct

Other restrictions

In order to make the studies more tractable, the author imposed further restrictions on the rule space:

• Quiescence condition: If all neighbours are equal (including yourself), remain in the current state
• Isotropy condition: Orientation of neighbourhood states does not matter

Wolfram's qualitative CA classes

The following denotes a categorization of different resulting evolutions a CA display:

Class I: Homogenous state (i.e. only one cell state)
Class II: Simple periodic structures
Class III: Chaos
Class IV: Complex patterns

This categorization can be used to classify the system's behaviour at different lambda.

Structure and parameters

A one-dimensional CA of 128 cells was used, where each end of the array is connected, i.e. a circular array. The neighbourhood function consists of the two closest neighbours on each side of a cell, and the cell itself. In total there were 4 transition functions (and thus 4 possible states each cell could have). In short:

K = 4
N = 5
128 cells

Results

Two kinds of initial state distributions were tested: A uniform random distribution, and a random distribution in the central 20 cells with the remaining cell initialized as 0. The following were the most significant observations (for both distributions) at different intervals of lambda:

• 0 - 0.15 : Dynamics die within few time steps
• 0.2 : Periodic structure (infinite), transient of 7-10 steps
• 0.25 : Longer transients, period of 1
• 0.35 : Dynamical possibilities broadening with longer transients and a new periodic structure
• 0.4 : Transient length 60 steps, period 40 steps
• 0.45 : Transient length 1000 steps, period 14848 steps. Solitary waves (propagating structures) are observed
• 0.5 : Transient length 12000 steps, then settles down to periodic behavior
• 0.55 : Shorter transient length, "settles" in chaotic dynamics
• 0.6 : Shorter transient length, broader dynamical activity
• 0.65 : Chaotic after 10 steps, width increase with 1 cell each time step
• 0.70 : Chaotic after 2 steps
• 0.75 : Chaotic after 1 step, maximum disorder for this K

Furthermore, at lambda = 0.5, a range of array sizes up to 512 cells were tested in order to observe the change in transient length: It grows exponentially with linear increase in array size.

Metrics

In order for a system to support computation, it needs to be able to both store and transmit information, which are opposite dynamics. A balance between the two needs to be found in order to support both functionalities.

The ability to transmit information can be described as the system's entropy (i.e. higher entropy means more chaos), which will be calculated by Shannon entropy. Given a cell A and its probability p_i for using transition function i:

H(A) = -SUM(p_i log2(p_i)), for i = 1, ..., K

In order to measure the cells' ability to affect the behaviour of another, we need a measure of their correlation, or mutual information. Given two cells A and B (either distinct cells or the same at different time steps), the mutual information is defined as:

I(A, B) = H(A) + H(B) - H(A, B)

Structure and parameters

A two-dimensional CA with 64x64 cells, 8 transient functions, and the adjacent cells and itself as neighbourhood was used. In short:

K = 8
N = 5
64x64 cells

Results

First, a gap between 0 <= lambda <= 0.6 and 0 <= H <= 0.84 was observed, which implies a first-order transition between having too little entropy to transmit info and too much entropy to store info. (Note that the transition occured at different lambda on different runs, which could for this measure alone conclude that both storage and transmission of info are supported at different lambda. When comparing with mutual information, though, it is not true.)

Second, the mentioned gap, although it was significant in size, was not completely empty. This implies there are a second-order transition present, which means there are greater dynamics present (and greater possibilites of emergent computation) that is not fully captured by these experiments.

Third, the range of H values observed decreased rapidly when lambda > 0.6, which means the cells have less variety and lose its ability to support storage.

Fourth, when comparing entropy and mutual information, it was found that mutual information was largest around H = 0.32 (H normalized), which would indicate an optimal trade-off between ability to transmit and store data in this vicinity.

Nodes

Takes a value of 0 or 1, which initially is random and later is updated according to an internal logical function (usually a lookup table).

Edges

Connects a node with other nodes, and possibly itself. The connections are created randomly initially. If the number K of edges in to a node is equal across all nodes the network it is called homogenous, if not it is called non-homogenous.

Topological features

• Descendants: All nodes a node affects
• Ancestor: All nodes that affect a node
• Linkage loop: A circuit of nodes that activates itself
• Relevant elements: Nodes that form the linkage loop without having a constant logical function
• Linkage tree: A path of activation that has no feedback to itself

Classification of states

• Successors: The states that a state can lead to
• Predecessors: The states that leads to a state
• In-degree: Number of predecessors
• Garden-of-eden: States without predecessors, i.e. in-degree of 0

Damage spread

Damage spread is a measure of stability for a system, where a damaged, i.e. altered, node state or connection will propagate changes through the network: In ordered networks the changes stop early, as it has no ability to vary its state; in chaotic networks, the change will propagate through the entire network and have drastic effects to the future states; on the edge of chaos the change can propagate through parts of the network, but not necessarily through the whole network.

Convergence

Ordered networks tend to have high convergence, meaning that (many) nearby states flow to the same state. In the chaotic phase, nearby states tend to diverge. In the critical phase, nearby states tend to neither converge nor diverge, but retain differences equivalent to their initial differences.

Classical model

It has a synchronous updating scheme, and each state only has one successor (because the next state is deterministically decided).

Multi-valued networks

Extension to the classical model that allows a node to have more than 2 values. Some natural systems are better modelled with more than 2 values of each node, but for theoretical purposes several boolean models can be combined to achieve the same result.

Topological extensions

A scale-free topology is non-homogenous, which means each node can have any number of incoming connections. The scale-free topology is considered to model real world applications more accurately. Although such networks are not well understood, they are shown to have several beneficial properties:

• Shorter attractors
• Higher entropy
• More mutual information
• Greater adaptivity (in some space of connection variability)

Synchronous RBNs

All nodes are updated simultaneously in timestep t+1 based on the state of timestep t.

Asynchronous RBNs

Node is iteratively picked at random to be updated. This also makes it non-deterministic.

Deterministic Async RBNs

Nodes are updated periodically, but not all at the same time, and in random time interval.

Scale-free networks

A scale-free network has a degree distribution that is scale-free, meaning that a multiplication of its input is equal to a multiplication of the function. This property implies that the network has a power-law distribution.

Price's growth model

A type of preferential attachment (or cumulative advantage) model for directed acyclic graphs. This means that each node will get a number of new connections proportional to its existing number of connections, e.g. an article with many citations is preferred to an equivalent article with few citations, and will thus gain even more citations. The resulting degree distribution is called a power-law degree distribution, where many nodes have low in-degree and few have high in-degree. When a new node is added, it will have a static out-degree, e.g. the number of references in the article, and zero in-degree. Price's model gives zero probability of increasing the in-degree of a node with an initial zero in-degree, but he cheated and added a constant to the in-degree to fix the imperfection (saying that an article can be considered to cite itself).

The model works though, and agrees with observation from real world networks.

Barabási and Albert's model

The same as Price's model, only for undirected graphs. This simplifies the model (and solves the intial zero in-degree problem), but is not as realistic for real world networks.

Vertex copying model

When adding new vertex, either assign edges randomly or copy the edges of another vertex.

Percolation process

Edges (bonds) or vertices (sites) are assigned a status of either "occupied" or "unoccupied", with the aim to study the properties of the resulting subgraphs of occupied and unoccupied sites or bonds. The process is called percolation, which basically means filtering. This process has been used to test the resilience of networks, i.e. how much of the graph can be removed before functionality degrade, or the components degrade significantly in size.

Epidemological processes

Disease spreads through networks by a power law degree distribution (person with many friends is more likely to catch disease than a person with no friends), where the reasoning behind putting people in quarantine is evident: Disconnect these nodes from other nodes, and the epidemic will not spread further. Percolation theory can model the effect of the spreading disease as it disables clusters of the network. By identifying the highest degree vertices and most sensitive parts of the network functionality, measures can be made to limit the damage from the disease.

Search

An exhaustive search creates an index of the network and uses this index for processing future queries. The indexing is usually performed by crawling the whole network initially, then updating the index every time a change occurs. A guided search must query the whole network on each instance, performed by multiple crawlers guided by some heuristic in order to search only promising parts of the network. Network navigation is the idea that networks can be architectured to enable faster search, based on observations such as Milgram's small world where people were connected through a short path unknown to them.

Phase transitions

A network property changing due to altering edges and/or node values is called a phase transition. Altering the graph in a graph coloring problem from low density to high density will trigger a phase transition: With few edges the coloring problem is easy, with many edges the coloring problem is impossible. This concept has been used to illustrate the Ising model as a network, and opinion forming in social networks.

Agents

Two types of agents:

• Beetle
• Tree

Both are modelled on the scale of individuals and on the scale of landscape. On a landscape scale, each agent represents a group of its kind. For beetles such a group would be all invidviduals habitating a tree, and for trees all trees participating in a forest.

Behaviour

The hard part of modeling entire systems based on many individuals is creating models for their behaviour at a local scale. An accurate model of the environment, i.e. the forest, is often hard to create because of insufficient data about local differences, which makes the model even harder to develop.

Stigmergy

Stigmergy is a mechanism of indirect communication between individuals, such as the pheromone trails of ants. Stigmergic cues can trigger actions, where each action is given a probability of being performed. This motivates collaboration among the individuals, as each individual will most of the time perform the action it perceives as the most useful to the colony.

An example of this is bees building cells in their nest, where the current structure functions as the stigmergy: There is a high probability of building another wall in a corner between cells, and a low probability to start building a new cell. That way the bees prioritize to finish cells before building new cells, but will always build new cells when all commenced cells have been finished.

Principles of self-organization

There are some "ingredients" required to maintain a self-organized system:

• Positive feedback: Promote a certain behaviour
• Negative feedback: Mechanism for disencouraging the positive feedback (e.g. pheromones evaporates if not maintained)
• Random fluctuations: Have a probability of not choosing a task, to motivate exploration
• Multiple stigmergic actions: Even if one individual fails to perform a task, others will "save the day"

Basically, this makes a system of checks and balances that relies on no single individual for the colony to survive.

Outer factors

An outer factor of change is independent of the colony, i.e. changes in the environment. This includes food distribution, predators, and weather.

Inner factors

Inner factors relates to changes in the colony or the individual. This includes the size of the colony (e.g. with respect to space available for each individual), and ratio between castes. It is also possible for the individual to modulate based on experience (performing successful actions) and age.

Augmented complex systems

Embedding information into natural complex systems in order to guide it to showing certain behaviour.

Construction

Assemble agents into something else, like Lego, in order to achieve some additional property. Typically all individual agents will retain some of its functionaliy, but not freedom of movement. Example: Robots linking together to build a bridge.

Coalescing

Create clusters or networks to adopt a certain shape, such as an insect swarm. One of the properties that a swarm can achieve is extended sensory input by transitivity, which can be used for evasion or food discovery.

Developing

Creating new agents through division and aggregation, like living cells.

Generating

Evolving the system by changing, adding or removing elements, or changing the rules it operates under.

Supportive elements

• Many elements (e.g. human beings, machines)
• Many interactions
  • Language
  • Economy
  • Social gatherings
  • Through time
• Substructures
  • Family and communities
  • Professionally
  • Regionally (e.g. countries, religion, language)
• Processes supporting organization
  • Biological evolution
  • Social evolution
• Interdependence (see subsection below)
• Complex behaviour (see "Transition from centralized control to self-organization")

Opposing elements

• No interaction with equivalent complex systems
• Humanity's response to environmental changes are not complex

Regarding the last bullet point: In complex systems, the system adapts to external changes in order to survive. Humanity, on the other hand, will to a significant degree adapt the environment to its needs. While this could be viewed as the "optimal form of adaptation", it does not fit with the general characteristics of a complex system. The possibility of adapting the environment comes from humanity's unique position as a system that has surpassed its environment in complexity, or at least parts of it.

Decrease in central control

Before the industrial revolution, the usual organization structure was very homogenous: One person at the top managing several, possibly thousands, of workers performing the same task. After machines replaced much of the manual labor that was performed, organizations became more heterogenous, and thus the complexity of the organization increased. Workers possessed different knowledge and skill sets, while the guy at the top had the same capabilities as before. This requried more layers of management, so that the central management only received the essential information and issued major commands.

From hierarchy to networked organizations

As competition increased and more specialization was requried, more and more levels of management was required to cope with the increased complexity of the organization. Although the information age made management more capable than before, it only mitigated the effect. Today we see that some businesses are more similar to a network of workers with equal responsibility rather than a hierarchy of control.

Without central control one might think that the system is fragile, but it is rather the opposite: If one part of the system fails, it is an opportunity (e.g. economical) for another, and competition motivates adaptation. We can use food distribution as an example: Serving millions of people with different requirements concerning assortment, price, and amount of food is an incredibly complex problem to solve, but the hundreds of distributors, restaurants, and stores satisfy this need (and creates something similar to an emergent behaviour). In the communist regimes where central control were responsible for satisfying this demand, the only way to cope with the problem was to keep the variety to a minimum and only have few stores to make distribution of correct amounts manageable.

The individual

Higher complexity in technology and industry requires more specialized education, and faster adaptation from the businesses' point of view. This entails that more people need to adapt their specialization and/or change careers during their life as well, which becomes harder with a more complex system. The article speculates that with a more complex society even a "specialization" in social life will be required, as people from different backgrounds will find it difficult to interact on a meaningful level, as well as having "specialized" news that fit your areas of knowledge and interest when the amount of news becomes unmanageable.

The individual's relationship to civilization

There were more acceptance for people dying before and during the early industrial revolution, because factory accidents and such just happened, and for most people an odds of 1 to 100 of dying was an acceptable risk. Today, society does not tolerate any risk of a person dying in accidents, and several governments have issued "zero accidents" goals in both traffic and industry. The point is, a complex society makes it safer for the individuals. The change in life expectancy of the average person is proof enough that a complex society is beneficial to the life of individuals.

As for economic safety, more people are changing careers than before, and often several times during their life. Although this instability may lower the life quality of the individuals, the unemployment rate in the US has been relatively stable for several decades, which shows that where some businesses and professions are abandoned others emerge. The general tendency shows that fewer people work for Fortune 500 companies (and the profits of those companies are equally lower as well) than before, which means more small businesses flourish.

Topical areas

Different fields of study in, or roots of, complex systems may be categorized as follows (the categorization is created by the author). Nonlinear Dynamics, Systems Theory, and Game Theory are (by the author) considered to be the roots of research on complex systems.

Models in Science and Engineering

Science is an endeavor to try to understand the world around us by discovering fundamental laws that describes how it works.

Modeling complex systems

Modeling cause and effect in complex systems are complicated compared to traditional science and engineering, and requires the analyst to become familiar with the dynamics of the complex system in order to understand them. Because of this computational modeling has had a significant effect on the research of complex systems.

Still some trial and error will be required in order to get a model right. Some important things to consider when modeling a complex system:

1. What are the key questions?
2. At what scale will the basic individuals operate?
3. How is the system structured?
4. What are the possible states of the system?
5. How does the state of the system change over time?

Problems

Problems or limitations with previous simulations tools with GUI:

• Attention diverted from general "marketable" skills towards learning the tools
• Different tool preferences in different fields
• Details hidden from the user
• Limits user creativity

The main problem of previous programming frameworks:

• Few and hard general-purpose, or only limited-purpose frameworks
• Difficult to use (especially for non-CS students)

Why Python?

• Easily accessible, and free
• Easy to use

Limitations of Python

• Difficult to install (for non-CS students)
• (Relatively) difficult to create GUI