(This pattern is described in Watson, J., Hawkins, J., Bradley, D., Dassanayake, D., Wiles, J. & Hanan, J. (2005). Towards a network pattern language for complex systems. To be presented at The Second Australian Conference on Artificial Life (ACAL 2005), and published by World Scientific in the Advances in Natural Computation series. See Publications for more information.)

Submitted by: Daniel Bradley, John Hawkins, James Watson, Dharma Dassanayake, Scott Heckbert, Andrew Hockey.

1a. Pattern name: Discrete State-Space Trajectory Diagram

1b. Classification: Visualization (Dynamics, State Space, Function, Macro Behaviours)

2. Intent. The pattern describes a technique for visualizing a system's dynamic qualities as a discrete graph. It allows for the identification of the number, size and structure of attractors, as well as the number and length of transients leading to these attractors.

By removing the specific details about the states the system takes, a state space diagram shows an abstract map of a systems dynamics. The removal of details irrelevant to describing dynamics eases the task of analysis by visual inspection.

3. Also known as. Wuensche Diagram, Basin of attraction field

4. Motivation. In all complex systems simulations at each moment the state of the system is described by a set of variables. As the system is updated over time these variables undergo changes that are influenced by the previous state of the entire system. System dynamics can be viewed as tabular data depicting the changes in variables over time. However, it is hard to analyze system dynamics just looking at the changes in these variables, as causal relationships between variables are not readily apparent.

By removing all the details about the actual state and the actual temporal information, we can view the dynamics as a graph with nodes describing states and links describing transitions. For instance software applications can have a large number of states. Problems occur when software applications reach uncommon or unanticipated states. Being able to visualize the entire state space, and quickly comprehend the paths leading to any particular state, allows more targeted analysis. Common states can be thoroughly tested, uncommon states can be identified and artificially induced.

State space diagrams allow for numerous insights into system behaviour, in particular some states of the system can be shown to be unreachable, while others are unavoidable.

5. Applicability. Any situation in which you have a model or system which changes state over time and you want to examine the abstract dynamical qualities of these changes. For example, social network theory, gene regulatory networks, urban and agricultural water usage, and concept maps in cognition and language modeling.

6. Structure. See Figure 3 below.

Discrete State-Space Trajectory Diagram - Structure

7. Participants. See Figure 4 below.

Discrete State-Space Trajectory Diagram - participants

8. Collaborations. Can be used with Activation Diagram to visualize the details of a given state.

9. Consequences.

  • The pattern supports it's objectives by removing details unrelated to the system dynamics, then examining only states and transitions.
  • There are several tradeoffs in applying this pattern. Firstly it works only for discrete state-spaces or discretely quantised continuous spaces. It is not tractable to show entire state space dynamics for systems with a large number of possible states. However, one can perform random sampling of the system and view partial state space diagrams.
  • For large diagrams the layout of nodes and connections is critical for comprehending the structure.
  • There can be a very large number of possible states for a given system. In these cases, visualization of the entire state space at once can be difficult.

10. Implementation.

  • There are two major methods of implementing the data structure beneath the transition network. It can be written as an adjacency list where each node points to a linked list of connections. Secondly it may be stored as a complete matrix of NxN dimensions (where N is the number of states). Non-zero entries in the matrix indicate the existence of a connection between nodes.
  • With an appropriate layout, e.g., Wuensche, the whole state space can be viewed at once. For large number of states, the diagram can be made easier to read by trimming off the most outlying states from transients.
  • Ghosting/colour changes allow the user to examine changes to system dynamics when some underlying aspect of the system is changed.
  • It is important to recognise that the graphical model is abstract only. Any spatial information contained in the underlying model is being removed.

11. Sample code. A complete state space transition network is produced thus:

--------------------------------------------------------------
initialiseStateTransitionNetwork(noOfStates)
For each currentState in Model
    model.setState(currentState)
    model.updateState()
    nextState = model.getState()
    StateTransitionNetwork.addTransition(currentState,nextState)
End for
--------------------------------------------------------------

Similarly to explore a particular trajectory through the state space:

--------------------------------------------------------------
initialiseStateTransitionNetwork(initialTrajectoryState)
currentState = initialTrajectoryState
nextState = model.nextState(currentState)    
StateTransitionNetwork.addTransition(currentState, nextState)

While Not StateTransitionNetwork.contains(nextState)  
    currentState = nextState  
    model.setState(currentState)
    model.updateState()
    nextState = model.getState()
    StateTransitionNetwork.addTransition(currentState, nextState)
End for
--------------------------------------------------------------

These code snippets cover the generation of the data structure representing the state space diagram. Once this has been generated there are a number of layout algorithms for creating the actual visualization.

12. Known uses. Boolean models of Gene networks, NK landscape problems, Visualizing basins of attraction in random Boolean networks.

13. Related patterns. Network Diagram, Neural Networks, Activation Diagram, Hypercube

About this document ...

Towards a Network Pattern Language for Complex Systems

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.