Graph dynamical system¶
A discrete dynamical system built from a graph, local vertex states and neighborhood functions, and an update scheme that induces a global state-transition map.
Core Idea¶
A graph dynamical system constructs global discrete dynamics from local interactions. Vertices carry states; each vertex has a function of its neighborhood; and an update scheme says when or in what order those functions act. Their combination induces a map F on the product of all vertex state sets.
Two graphs matter and must not be confused. The dependency graph specifies who can influence whom, while the phase-space graph has complete configurations as vertices and edges x→F(x). Research seeks local-to-global connections: how connectivity, local functions, and scheduling determine fixed points, attractors, cycles, and reachability. Synchronous and sequential schemes are different model classes, not merely different software implementations.
Structural Signature¶
Sig role-phrases:
- dependency graph — specifies which vertex states each local update may inspect It is essential. Counterfactual: Without neighborhood structure the system is not graph-indexed.
- vertex state sets — provide the local values whose product forms the global state It is essential. Counterfactual: Without local states there is no configuration to evolve.
- local vertex functions — map neighborhood configurations to updated vertex values It is essential. Counterfactual: The graph alone cannot determine dynamics.
- update scheme — orders or synchronizes local applications to create one global evolution rule It is essential. Counterfactual: The same graph and functions can yield different dynamics under different schedules.
- global transition map — sends each complete configuration to its successor and defines the dynamical system It is essential. Counterfactual: Uncombined local rules do not yet specify full-state evolution.
- phase-space graph — represents trajectories, cycles, and basins among global states It is diagnostic. Counterfactual: Studying only the dependency graph can miss the resulting state dynamics.
What It Is Not¶
- It is not any time-varying data displayed on a graph.
- It is not the phase-space graph alone.
- It is not restricted to identical local functions or regular lattices.
- It is not fully specified until the update scheme is given.
- Closest near-miss. A cellular automaton on a regular lattice is a special case, while a generic agent-based model is only a near neighbor unless its local functions and schedule have this explicit graph construction.
Scope of Application¶
- Generalized cellular automata. Synchronous local updates operate on arbitrary finite graphs.
- Sequential dynamical systems. An ordered composition of local maps defines evolution.
- Network processes. Finite-state spreading, regulation, or interaction models use graph-local dependence.
- Phase-space analysis. Global fixed points, cycles, basins, and reachability are derived from constituents.
Clarity¶
Specify graph directionality, local state sets, neighborhood convention, every vertex function, and the update scheme. State whether randomness or infinite spaces extend the standard finite setting. Never use the dependency graph and the phase-space graph interchangeably.
Manages Complexity¶
The framework compresses an exponential global map into a graph plus local rules and schedule. This makes construction and comparison tractable, but the induced phase space can still be enormous. Structural results aim to infer global behavior without enumerating every configuration.
Abstract Reasoning¶
- Choose the vertices and encode allowed dependencies as a graph.
- Assign a state set to each vertex and form the product state space.
- Define each vertex function on its ordered neighborhood state.
- Choose synchronous, sequential, stochastic, or another explicit update scheme.
- Compose local updates to obtain the global transition map F.
- Construct or characterize the phase space and its invariant behavior.
- Vary graph, functions, or schedule separately to attribute changes in dynamics.
Knowledge Transfer¶
The framework transfers across networked processes when interactions can be represented by local functions and a discrete update protocol. It stops at merely graph-indexed observations or continuous dynamics unless those are deliberately reformulated. The portable cargo is local dependency plus scheduled composition into a global map.
Examples¶
Applied / In Practice¶
Binary vertex functions on a cycle graph are all applied to the old configuration at once, yielding a generalized cellular automaton.
Mapped back: graph → Cycle adjacency fixes neighborhoods.; schedule → All vertices update synchronously.; global map → Their simultaneous outputs form the successor configuration..
Applied / In Practice¶
The same local rules applied in the order 1,2,3,4 can produce a different successor and phase space.
Mapped back: schedule → Function composition follows an explicit word or permutation..
Applied / In Practice¶
A graph records observed correlations among time series but supplies no local update functions.
Mapped back: boundary → A descriptive network is not a constructed graph dynamical system..
Structural Tensions¶
T1 — Local Specification versus Global Behavior. Simple neighborhood rules can generate phase spaces whose cycles and basins are hard to infer.
Diagnostic: Analyze how graph, functions, and schedule each constrain the global transition map.
T2 — Synchronous versus Asynchronous Update. Simultaneous and sequential application can change fixed points, cycles, and reachability even with identical local functions.
Diagnostic: Treat the update scheme as model data rather than an implementation detail.
Structural–Framed Character¶
Graph, state, function, and schedule are structural. Their interpretation as genes, agents, automata, or devices is framed by the application. The same formal system can model different domains, but empirical meaning and validation do not transfer automatically.
Structural Core vs. Domain Accent¶
The skeleton is compositional local-to-global evolution. Discrete dynamics supplies finite configurations, function composition, phase spaces, and attractors; graph theory supplies neighborhoods. Removing either local dynamics or graph dependence destroys the specific framework.
Instantiates / Related Primes¶
This entry is a kind of Formal Model.
-
Approved root. The frozen DAG retains this framework as an unparented formal-modeling abstraction.
-
Related — cellular automaton and sequential dynamical system. They are synchronous and ordered-update subclasses respectively.
Relationships to Other Abstractions¶
Current abstraction Graph dynamical system Domain-specific
Parents (1) — more general patterns this builds on
-
Graph dynamical system is a kind of Formal Model Domain-specific
It is explicitly defined by graph-coupled state and update rules.It is explicitly defined by graph-coupled state and update rules.
Hierarchy path (1) — routes to 1 parentless root
- Graph dynamical system → Formal Model → Representation → Abstraction
Neighborhood in Abstraction Space¶
Graph dynamical system sits in a crowded region of the domain-specific corpus (39th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Graph Structures & Algorithms (24 abstractions)
Nearest neighbors
- Prim’s Algorithm — 0.88
- Graphical Game Theory — 0.88
- Loop (Graph Theory) — 0.88
- Prism graph — 0.87
- Cycle Graph (Algebra) — 0.87
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Dynamic graph. Tell: Changes its own vertices or edges; a GDS can use a fixed dependency graph.
- Phase-space graph. Tell: Represents global state transitions rather than local dependency.
- Cellular automaton. Tell: A typically regular and homogeneous special case of synchronous GDS.
- Agent-based model. Tell: May use agents and networks without the explicit local-function/update-scheme formalism.
References¶
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Graph_dynamical_system (revision 1330771905).
- Preserved source candidate: https://web.archive.org/web/20140903062024/http://www.samsi.info/sites/default/files/samsi-05-dec-08.pdf
The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.