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 *closed-form* solution because the right-hand side is "closed".

A *model* is just some (simplified) representation of a system (any kind of representation).

When modeling a complex system, you should consider:

- what are your goals? what questions do you want to answer?
- what is the structure of the system?
- what are the possible states?
- what are the dynamics of the system?

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 *iterative map*.

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 *higher-order system*.

An *autonomous system* is a dynamical equation whose rules don't explicitly include time *non-autonomous system* is a dynamical equation whose rules *do* 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:

- exponential growth/decay
- periodic oscillations
- stationary states
- or some combination of the above
- when their coefficient matrices are non-diagonalizable, they can also show behaviors that are polynomials (or products of polynomials and exponentials) of time

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 *Lyaponuv stable*, which means that the system's state neither diverges away from nor converges to the equilibrium point. Note that this is not a conclusive indicator of it being Lyaponuv stable!

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 *matrix exponential* for a square matrix

where

The matrix exponential

- its eigenvalues are exponentials of
$X$ 's eigenvalues - its eigenvectors are the same length as
$X$ 's eigenvectors, i.e.$Xv = \lambda v \Rightarrow e^v e^{\lambda}v$

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):

$\text{Re}(\lambda) > 0$ means the component is growing$\text{Re}(\lambda) < 0$ means the component is shrinking$\text{Re}(\lambda) = 0$ means the component is conserved

For the dominant eigenvalue

$\text{Re}(\lambda_d) > 0$ means the system is unstable, diverging to infinity$\text{Re}(\lambda_d) < 0$ means the system is stable, converging to the origin$\text{Re}(\lambda_d) = 0$ means the system is stable, but may converge to a non-zero equilibrium point

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 *neighborhood* around a given automaton.

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:

- no boundaries - the space is infinite, expanding in all directions, filled with the quiescent state
- periodic boundaries - the space "wraps around" at the edges
- cut-off boundaries - the space just ends at the edges
- fixed boundaries - sets the cells at the edge of the finite space to have fixed states that never change

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.