24 Dec 2011

# The Calculus of Complexity

Many resarchers who work in “complexity science” or deal with “the sciences of complexity”, especially scientists associated with the Santa Fe Institute (SFI), complain a lack of a sound, rigorous mathematical theory. We have a few suggestive metaphors and disparate piece of knowledge, but no rigorous and useful mathematical framework. John Howard Miller, Scott E. Page, Melanie Mitchell, Stuart Kauffman, James Crutchfield and Steven Strogatz argue that we need a calculus of complexity, a mathematical theory that describes complexity in a general way, which would allow us to explain phenomena and make predictions across many different systems. It is an open question if such a theory exists.

Miller and Page ask in their book about “Complex adaptive systems” [1] if there is a mathematics of complex adaptive social systems (Appendix A.4, p. 234)

“While computational models of complex adaptive social systems are a valuable theoretical tool, there may be other complementary tools that can be developed. The calculus allowed us to take certain, difficult-to-solve, nonlinear equations and reform them into simple linear problems. Is there a mathematics of complex adaptive social systems that will provide a similar transformation? Any simulation can be written as an instantiation of a recursive function, suggesting that a given model run is nothing more than a sequence of interconnected algebraic equations. But can we say something more general here? Ultimately, we are seeking a simple explanation for complex behavior. While there are examples from cellular automata that suggest that the only way to predict the future behavior of the system is to let it fully run out, the obvious hope is that there are other opportunities to uncover more compact descriptions of complex behavior.” [1]

Steven Strogatz said in his book SYNC [2] that we need the conceptual equivalent of a calculus:

“We’re still waiting for a major breakthrough in understanding, and it could be a long time in coming. I think we may be missing the conceptual equivalent of calculus, a way of seeing the consequences of the myriad interactions that define a complex system. It could be that this ultracalculus, if it were handed to us, would be forever beyond our comprehension. We just don’t know.” [2]

He says that traditional calculus is based on the concept of change: “Calculus is the mathematics of change. [..] you’ll find two ideas shining through. All the rest, as Rabbi Hillel said of the Golden Rule, is just commentary. Those two ideas are the “derivative” and the “integral.” Each dominates its own half of the subject, named in their honor as differential and integral calculus. Roughly speaking, the derivative tells you how fast something is changing; the integral tells you how much it’s accumulating.”

Stuart Kauffman writes in his book “At Home in the Universe” [5] on page 299:

“We lack a theory of how the elements of our public lives link into webs of elements that act on one another and transform one another. We call these transformations ‘history’. Hence with all the accidents of history, one must engage in a renewed debate: Is there a place for law in the historical sciences? Can we find lawlike patterns, cultural, economic, and otherwise?”

This question is quite similar to the question of Leo Nikolayevich Tolstoy in his epic novel War and Peace (Book 11, Chapter 1): “Only by taking infinitesimally small units for observation (the differential of history, that is, the individual tendencies of men) and attaining to the art of integrating them (that is, finding the sum of these infinitesimals) can we hope to arrive at the laws of history.”

Both Kauffman and Tolstoy are great story tellers, and history is teld in stories, too. Is history just a collection of stories or more? It is unclear if we can establish universal “laws of history”, as they say, but it is clear that the most basic law which governs history is evolution and co-evolution. Besides evolution, what else can we say if we concentrate on agent based models? Are phenomena like the “Butterfly Effect”, “Path Dependence” or “Frozen Accidents” equivalent to laws? Is the micro or the macro level more important for the “laws of history”?

Melanie Mitchell thinks we need a calculus of complexity, too. She asks in her ook “Complexity – a guided toor” [3]:

“We are waiting for the right concepts and mathematics to be formulated to describe the many forms of complexity we see in nature […] Calculus provides a mathematical language to rigorously describe change and motion, in terms of such notions as infinitesimal, derivative, integral, and limit. These concepts already existed in mathematics but in a fragmented way. Newton was able to see how they are related and to construct a coherent edifice that unified them and made them completely general. This edifice is what allowed Newton to create the science of dynamics. Can we similarly invent the calculus of complexity that captures the origins and dynamics of self-organization, emergent behavior, and adaptation in complex systems?”

Let us summarize what Miller, Page, Kauffman, Mitchell, and Stogatz said so far.  We would like to to describe the many forms of complexity in nature,  and we are..

• ..waiting for the right concepts to be formulated
• ..seeking a simple explanation for complex behavior in general
• ..looking for the conceptual equivalent of calculus to explain complex systems
• ..trying to find universal “laws of history” to describe the change of complex systems

Wait – to seek explanations for complex behaviors and to find a calculus of complexity in general, is the task of science in general, isn’t it? If there is a general theory, a theory of everything, for all these vastly diffent kinds of complex systems we find on Earth it is simply evolution. Evolution is the only theory that can be applied to nearly all fields, subjects and systems, because everything has evolved and is still changing and evolving. Therefore the most universal theory of science is evolution, so if we can explain evolutionary and complex adaptive systems, we have made good progress. There is a lot we know about evolution already [6]. We can describe certain aspects of evolutionary systems by mathematical modelling.  And we can apply the concepts of evolution to other systems. What else can we do?

Let us go a step back. The reason why we can go beyond suggestive metaphors in complexity theory and why we can examine complex systems systematically in the first place is clearly the advance in computational power. Computing has pervaded nearly every science, but computing itself is not the science of nearly everything. Agent-based computational models are the scientific instruments to examine complex systems. They are the tool of choice to understand the complexity of economic, ecological, and social systems [7]. CA and ABM modeling allows us to explain the common patterns of some complex systems, and simple recursive algorithms allows us to produce complex fractals and fractal patterns. Simulation models are powerful tools to explain complexity in nature.

So we have evolution and evolutionary systems on one side, and we know it is the most basic theory. On the other side we have agent-based computational models, and we have found many of the underlying principles of insect colonies, economic systems, the brain, and other complex systems. The important ones are adaptation, emergence, path-dependence, and swarm-intelligence. Although these are appealing concepts, they do not always rest on well-defined notions and definitions. The challenge is to connect and reconcile both sides in a theory of complex adaptive systems.

This can only be successful if the concepts are well-defined, and if they are firmly grounded in computational science, since computational tools allow us to examine complex systems. Calculus provides a way to measure physical objects and their movements. We can hardly measure complexity if it is an ill-defined notion. However we can measure how “patterned” and diverse a system is. A pattern is something we can measure, for example in form of a fractal dimension. Likewise talk about emergence remains fuzzy unless we are focussing on concrete agent-based models.

What kind of models exist? Fractals are the right forms of mathmatics for self-similar forms. Using simple IFS rules, one can produce beautiful fractals and describe a lot of the beauty of nature. RBNs, CAs and ABMs are powerful simulation models.  How far can take us simulation models on the road to a “calculus of complexity”? Is it possible to combine a few smaller models to a larger model? Even simple agent-based models can exhibit complex behavior patterns, but most of them do not. They can not be added and subtracted like functions, although emergence is related to integration in calculus. ABMs can capture certain emergent phenomena, which result from the interactions of individual entities, as Eric Bonabeau says in his paper about agent-based modeling . Basically they tells us how a local interaction pattern translates into a global pattern. The rules of the ABM tells us like the derative how (how fast and how much) something changes locally. The name of the model (for example Conway’s Game of Life, Thomas Schelling’s Segregation model for ghetto formation, Craig Reynold’s Boids model for swarm formation, or Robert Axelrod’s Dissemination model for culture or cluster formation) tells us the overall effect of the rules, how much it is accumulating and how much it will change.

 f(x) = F'(x) rule of the game F(x) name of the model Interaction Pattern RBN rule emergent state (attractor) network CA rule emergent pattern (Conway’s Game of Life, Rule 30 pattern, ..) grid ABM rule emergent phenomenon (swarm, cluster, ghetto, ..) loosely coupled

They are all “generative” models, since they generate patterns by repeated execution, just like an IFS. Basically all of them tells us how a local interaction pattern with the nearest neighbor (RBN: network, CA: grid, ABM: loosely coupled) translates into a global pattern. Besides these basic models (RBN, CA and ABM), we can simply use data to explain data. Mathematics is about symmetries and regularities among numbers and quantities. It is so successful and effective because we can explain the symmetries and regularities in Mathematics to explain the symmetries and regularities in the physical world. Complex systems are characterized by an overwhelming amount of data. We can use data to explain and understand data.

There is a Google Research Paper from Alon Halevy, Peter Norvig and Fernando Pereira named the Unreasonable Effectiveness of Data (a play on Eugene Wigner’s essay ‘the unreasonable effectiveness of mathematics in the natural sciences’). They argue the best approach is to embrace the complexity of the domain and address it by harnessing the power of data.

Is data the only way to explain data in some complex systems, too? After all, humans and the societies they live in are constantly changing complex adaptive systems with astonishing abilities and path-dependent behavior. If we know the complete history and biography of a person, company or society, we can explain and predict the behavior by this data to a certain degree. Since more and more data about persons is collected in social networks and elsewhere, this is indeed a possibility.

[1] John Howard Miller and Scott E. Page, “Complex adaptive systems: an introduction to computational models of social life”, Princeton University Press, 2007
[2] Steven H. Strogatz, “SYNC: The Emerging Science of Spontaneous Order”, Hyperion, 2003
[3] Melanie Mitchell, “Complexity – a guided toor”, Oxford University Press, 2009
[4] ACM ubiquity, April 2011: An interview with Melanie Mitchell On complexity
[5] Stuart Kauffman, “At Home in the Universe”, Oxford University Press, 1996
[6] Ruse, Travis, Wilson (Eds.), Evolution: The First Four Billion Years, Harvard University Press, 2009
[7] Joshua M. Epstein, Agent-based computational models and generative social science, Complexity, Vol. 4 (1999) 41-60

Message:

or