Notes for Introduction to the Modeling and Analysis of Complex Systems (Hiroki Sayama).
Emergence describes properties that are not present in the components of a system but occur at the level (scale) of the system as a result of the interaction between components.("the whole is greater than the sum of its parts"). You can't examine an individual component and see the emergent property there, and they can't be explained purely in terms of the component's properties - their interactions and relationships must be taken into account.
Scale plays an important part in that the phenomena/emergent properties at each scale can be very different.
Self-organization can also occur where coherent macroscopic structures and/or behaviors form over time.
Complex systems exhibit emergence (across scales) as a result of nonlinear interaction amongst their components and exhibit self-organization (across time).
"Nonlinear" refers to that the outputs (e.g. the next state of the system) cannot be expressed as a linear combination of inputs (e.g. the current state of the system). Note that linear equations are analytically solvable, whereas nonlinear equations generally are not.
An analytical solution is a solution written in the form
A model is just some (simplified) representation of a system (any kind of representation).
When modeling a complex system, you should consider:
We prefer models that are simple, valid against empirical evidence, and robust to minor changes in modeling assumptions or parameters. There is often a trade-off between simplicity and validity (i.e. a more complex model can better conform to real-world observations, which introduces an overfitting problem).
Discrete-time dynamical systems are expressed as a difference equation (also called a recurrency equation):
or equivalently:
If there is no
These are called difference equations because they can be translated easily into "difference" form:
Continuous-time dynamical systems are expressed as a differential equation:
In each case,
A phase space is a space in which each state of the system is mapped to a unique spatial location. The number of state variables needed to uniquely specify the system's state (i.e. the dimensions of the space) is the degrees of freedom in the system.
We can use phase space to visualize trajectories of the system through its various states. We may encounter attractors, etc (see other notes on complex systems) in phase space.
A first-order system is one that involves only state variables of the immediate past (at time
An autonomous system is a dynamical equation whose rules don't explicitly include time
Non-autonomous, higher-order difference equations can be converted into autonomous, first-order forms by introducing additional state variables.
For instance, consider the Fibonacci sequence, which is second-order:
We can introduce a "memory" variable
We can do something similar for converting non-autonomous equations into autonomous equations:
Linear dynamical systems can only show the following behaviors:
These behaviors are indicative of linear systems.
The asymptotic behavior of a system is what happens when time is taken to infinity.
We can describe the dynamics of a discrete-time linear dynamical system as:
where
This has the closed-form solution:
The asymptotic behavior of such a system is described by having
Remember that eigenvalues
We can apply this to
Then we need to represent the initial state
Where
Now we have:
So the largest (by absolute value) eigenvalue (called the dominant eigenvalue) will come to dominate this equation as
For these discrete-time models, the absolute value of the eigenvalues can tell us a lot about the system:
- if $ | \lambda_i | > 1 |
---|---|---|
- if $ | \lambda_i | = 1 |
We learn more from the dominant eigenvalue
- if $ | \lambda_d | > 1$, the system is unstable, diverging to infinity |
---|---|---|
- if $ | \lambda_d | = 1$, the system is stable, but may converge to a non-zero equilibrium point |
(from the textbook, figure 5.13)
The dynamics of a linear system are decomposable into multiple independent one-dimensional exponential dynamics, each along the direction given by an eigenvector.
If the eigenvalues of the coefficient matrix are complex conjugate rather than real (i.e. because the matrix is asymmetric), it means that there is rotation happening in the phase space. In this case, the eigenvalues are still informative:
- if $ | \lambda_i | > 1 |
---|---|---|
- if $ | \lambda_i | = 1 |
Also note that the list of eigenvalues for a system is called the (eigenvalue) spectrum of the system.
Unfortunately this methodology of eigenvalues and eigenvectors cannot be applied to the asymptotic analysis of nonlinear dynamical systems.
Eigenvalues and eigenvectors can, however, be used to conduct linear stability analysis of nonlinear systems, which describes the stability of the system at or near its equilibrium point by approximating the dynamics around that point as linear.
The general idea behind this is that we take the equilibrium point and perturb it slightly (by an infinitesimally small amount).
Say we have the nonlinear difference equation:
At the equilibrium point
Then we slightly perturb it:
Assuming
This yields us the simple linear difference equation:
From this we can see that if
If
where
Then we take the eigenvalues of
When around an equilibrium
The points about complex conjugates from before also apply here.
Continuous time models are expressed in differential equations. To get the trajectory of the system's state over time, we just integrate over the differential equation that describes the system. This is usually done via simulation (i.e. numerically, for which there are many different methods, such as the Euler forward method).
The linear/nonlinear and autonomous/non-autonomous distinctions still apply here, though the first-order/higher-order distinction is a little different. Here, a first-order system is a differential equation that involves first-order derivatives of state variables (
The conversion of non-autonomous, higher order equations to autonomous, first-order forms also holds here.
A general formula for continuous-time linear dynamical systems is given by:
where
The asymptotic behavior of this equation has a closed-form solution:
Where
where
The matrix exponential
We assume that
So we represent the initial state of the system as:
We apply this to the asymptotic behavior equation:
This is similar to what we saw for discrete time models except that now the asymptotic behavior is given by the summation of
Note that
Like with discrete-time models, we get a lot of info from the eigenvalues (the real part):
For the dominant eigenvalue
Like with discrete-time nonlinear dynamical systems, we can also conduct linear stability analysis for continuous-time nonlinear dynamical systems.
If we have the nonlinear differential equation:
The equilibrium point
Similar to discrete-time models, we apply the following replacement:
which gives us:
As before, the nonlinear function
The rest of the process is similar to linear stability analysis for discrete-time nonlinear dynamical systems. The main difference is that you only look at the real parts of the eigenvalues, and you compare them with 0, not one.
Automata are "machines" that change their internal state based on inputs and their previous state. Cellular automata (CA) arrange these automata in a spatial grid, such that each automaton is affected by the states of their neighbors. The particular way their state is affected is defined by a state-transition function. The automata are synchronously updated (i.e. simultaneously updated). CA models are discrete in both time and space.
The state
Where
If a state-transition function gives an identical state to rotated configurations of automaton, it is said that the CA model has rotational symmetry. If all states of the CA are orientation-free and the rotation of a situation doesn't involve any rotation of the states themselves, the rotational symmetry is strong, otherwise, it is weak.
If the state-transition function depends only on the sum of the states of cells within the neighbors, the CA is totalistic. By definition, these totalistic state-transition functions are rotationally symmetric.
The states of a CA may be either quiescent (it remains the same if all of its neighbors are in the same quiescent state, e.g. the "blank" state) or non-quiescent (also called active states because they change dynamically and interact with nearby states).
The spatial boundary conditions of a CA must be specified, which describes behavior at the borders of the CA world:
Cellular automata may also be stochastic (i.e. the state-transition function is stochastic), they may include multiple layers (i.e. cell states can be vectors rather than scalars), and they may be asynchronous, e.g. via random updating (randomly choosing cells to update at each time step), or sequential updating (updating cells in a specified order), state-triggered updating (certain states trigger updating of nearby cells), etc.
Involves many discrete agents. Analysis of ABMs is conducted in a more conventional experimental way, e.g. running Monte Carlo simulations, observing outcome distributions, and then determining if there is a significant difference.
Agents may be stateful, they may interact with one another, they may interact with their environment, and they may have predefined rules or learned behaviors.
Cellular automata and network models, because they are also composed of discrete components, are special cases of ABMs.