The Azimuth Project
Blog - networks of dynamical systems

This page is a blog article in progress, written by Eugene Lerman. To see discussions of this article while it is being written, visit the Azimuth Forum.

guest post by Eugene Lerman

Hi, I’m Eugene Lerman. I met John back in the mid 1980s when John and I were grad students at MIT. John was doing mathematical physics and I was studying symplectic geometry. We never talked about networks. Now I teach in the math department at the University of Illinois at Urbana, and we occasionally talk about networks on his blog.

A few years ago a friend of mine who studies locomotion in humans and other primates asked me if I knew of any math that could be useful to him.

I remember coming across an expository paper on ‘coupled cell networks’:

• Martin Golubitsky and Ian Stewart Nonlinear dynamics of networks: the groupoid formalism, Bull. Amer. Math. Soc. 43 (2006), 305–364.

In this paper, Golubitsky and Stewart used the study of animal gaits and models for the hypothetical neural networks called ‘central pattern generators’ that give rise these gaits as motivation for the study of networks of ordinary differential equations with a strange kind of symmetry. In particular they were interested in ‘synchrony’. When a horse trots, or canters, or gallops, its limbs move in a synchronized way—how does this work?

They explained that synchrony could arise when the differential equations have no group symmetries but are ‘groupoid invariant’. I thought that it would be fun to understand what ‘groupoid invariant’ meant and why such invariance leads to synchrony.

I talked my colleague Lee DeVille into joining me on this adventure. Lee had just arrived at Urbana after a postdoc at NYU. After a few years of thinking about these networks Lee DeVille and I realized that strictly speaking one doesn’t really need groupoids for these synchrony results and it’s better to think of the social life of networks instead. Here is what we figured out—a full and much too precise story is here:

Dynamics on networks of manifolds.

Let’s start with an example of a class of ODEs with a mysterious property:

Example. Consider this ordinary differential equation for a function x: 3 \vec{x} : \mathbb{R} \to {\mathbb{R}}^3

x˙ 1 = f(x 1,x 2) x˙ 2 = f(x 2,x 1) x˙ 3 = f(x 3,x 2) \begin{array}{rcl} \dot{x}_1&=& f(x_1,x_2)\\ \dot{x}_2&=& f(x_2,x_1)\\ \dot{x}_3&=& f(x_3, x_2) \end{array}

for some function f: 2. f:{\mathbb{R}}^2 \to {\mathbb{R}}. It is easy to see that a function x(t) x(t) solving

x˙=f(x,x) \displaystyle{ \dot{x} = f(x,x) }

gives a solution of these equations if we set

x(t)=(x(t),x(t),x(t)) \vec{x}(t) = (x(t),x(t),x(t))

You can think of the differential equations in this example as describing the dynamics of a complex system built out of three interacting subsystems. Then any solution of the form

x(t)=(x(t),x(t),x(t)) \vec{x}(t) = (x(t),x(t),x(t))

may be thought of as a synchronization: the three subsystems are evolving in lockstep.

One can also view the result geometrically: the diagonal

Δ={(x 1,x 2,x 3) 3x 1=x 2=x 3} \displaystyle{ \Delta = \{(x_1,x_2, x_3)\in {\mathbb{R}}^3 \mid x_1 =x_2 = x_3\} }

is an invariant subsystem of the continuous-time dynamical system defined by the differential equations. Remarkably enough, such a subsystem exists for any choice of a function f f.

Where does such a synchronization or invariant subsystem come from? There is no apparent symmetry of 3 {\mathbb{R}}^3 that preserves the differential equations and fixes the diagonal Δ, \Delta, and thus could account for this invariant subsystem. It turns out that what matters is the structure of the mutual dependencies of the three subsystems making up the big system. That is, the evolution of x 1 x_1 depends only on x 1 x_1 and x 2, x_2, the evolution of x 2 x_2 depends only on x 2 x_2 and x 3, x_3, and the evolution of x 3 x_3 depends only on x 3 x_3 and x 2. x_2.

These dependencies can be conveniently pictured as a directed graph:

The graph G G has no symmetries. Nonetheless, the existence of the invariant subsystem living on the diagonal Δ \Delta can be deduced from certain properties of the graph G/ G/ The key is the existence of a surjective map of graphs

φ:GG \varphi :G\to G'

from our graph G G to a graph G G' with exactly one node, call it a, a, and one arrow. It is also crucial that φ \varphi has the following lifting property: there is a unique way to lift the one and only arrow of G G' to an arrow of G G once we specify the target node of the lift.

We now formally define the notion of a network of regions and of a continuous-time dynamical system on such a network. Equivalently, we define a network of continuous-time dynamical systems. We start with a directed graph

G={G 1G 0} G=\{G_1\rightrightarrows G_0\}

Here G 1 G_1 is the set of edges, G 0 G_0 is the set of nodes, and the two arrows assign to an edge its source and target, respectively. To each node we attach a region (more formally a manifold, possibly with corners). Here ‘attach’ means that we choose a function P:G 0Region; { P}:G_0 \to {{Region}}; it assigns to each node aG 0 a\in G_0 a region P(a) { P}(a).

In our running example, to each node of the graph G G we attach the real line {\mathbb{R}}. (If we think of the set G 0 G_0 as a discrete category and Region {{Region}} as a category of manifolds with corners and smooth maps, then P { P} is simply a functor.)

Thus a network of regions is a pair (G,P) (G,{ P}), where G G is a directed graph and P { P} is an assignment of regions to the nodes of G. G.

We think of the collection of regions {P(a)} aG 0 \{{ P}(a)\}_{a\in G_0} as the collection of phase spaces of the subsystems constituting the network (G,P) (G, { P}). We refer to P { P} as a phase space function. Since the state of the network should be determined completely and uniquely by the states of its subsystems, it is reasonable to take the total phase space of the network to be the product

(G,P):= aG 0P(a). \displaystyle{ {\mathbb{P}}(G, { P}):= \bigsqcap_{a\in G_0} { P}(a). }

In the example the total phase space of the network (G,P) (G,{ P}) is 3, {\mathbb{R}}^3, while the phase space of the network (G,P) (G', { P}') is the real line {\mathbb{R}}.

Finally we need to interpret the arrows. An arrow bγa b\xrightarrow{\gamma}a in a graph G G should encode the fact that the dynamics of the subsystem associated to the node a a depends on the states of the subsystem associated to the node b. b. To make this precise requires the notion of an ‘open system’, or ‘control system’, which is defined below. (IT’S NOT DEFINED BELOW, IS IT??? HOW ABOUT DEFINING IT HERE???) It also requires way to associate an open system to the set of arrows coming into a node/vertex a a.

To encode the incoming arrows we introduce the input tree I(a) I(a) (this is a very short tree, a corolla if you like). This is a directed graph whose arrows are precisely the arrows of G G coming into the vertex a, a, but any two parallel arrows of G G with target a a will have disjoint sources in I(a) I(a). In the example the input tree I I of the one node of a a of G G' is the tree

There is always a map of graphs ξ:I(a)G \xi:I(a) \to G. For instance for the input tree in the example we just discussed, ξ \xi is the map

Consequently if (G,P) (G,{ P}) is a network and I(a) I(a) is an input tree of a node of G G, then (I(a),Pξ) (I(a), { P}\circ \xi) is also a network. This allows us to talk about the phase space I(a) {\mathbb{P}} I(a) of an input tree. In our running example,

I(a)= 2 {\mathbb{P}} I(a) = {\mathbb{R}}^2

Given a network (G,P) (G,{ P}), there is a vector space Ctrl(I(a)a) {Ctrl}({\mathbb{P}} I(a)\to {\mathbb{P}} a) of open systems to every node a a of G G. (THIS SENTENCE IS UNGRAMMATICAL AND THE CONCEPT OF vector space of open systems DOESN’T SOUND RIGHT - PROBABLY SOME TYPOS HERE. FURTHERMORE THE NOTATION CtrlCtrl WAS NEVER DEFINED - PERHAPS IT’S PART OF THE UNDEFINED CONCEPT OF control system???) In our running example the vector space associated to the one node a a of (G,P) (G',{ P}') is

Ctrl( 2,)C ( 2,) {Ctrl}({\mathbb{R}}^2, {\mathbb{R}}) \simeq C^\infty({\mathbb{R}}^2, {\mathbb{R}})

In the same example the network (G,P) (G,{ P}) has three nodes and we associate the same vector space C ( 2,) C^\infty({\mathbb{R}}^2, {\mathbb{R}}) to each one of them.

We then construct an interconnection map

I: aG 0Ctrl(I(a)a)Γ(T(G,P)) \displaystyle{ {{I}}: \bigsqcap_{a\in G_0} {Ctrl}({\mathbb{P}} I(a)\to {\mathbb{P}} a) \to \Gamma (T{\mathbb{P}}(G, { P})) }

from the product of spaces of all control systems to the space of vector fields

Γ(T(G,P)) \Gamma (T{\mathbb{P}} (G, { P}))

on the total phase space of the network. (We use the standard notation to denote the tangent bundle of a region R R by TR TR and the space of vector fields on R R by Γ(TR) \Gamma (TR)). In our running example the interconnection map for the network (G,P) (G',{ P}') is the map

I:C ( 2,)C (,),f(x,u)f(x,x). \displaystyle{ {{I}}: C^\infty({\mathbb{R}}^2, {\mathbb{R}}) \to C^\infty({\mathbb{R}}, {\mathbb{R}}), \quad f(x,u) \mapsto f(x,x). }

The interconnection map for the network (G,P) (G,{ P}) is the map

I:C ( 2,) 3C ( 3, 3) \displaystyle{ {{I}}: C^\infty({\mathbb{R}}^2, {\mathbb{R}})^3 \to C^\infty({\mathbb{R}}^3, {\mathbb{R}}^3)}

given by

(I(f 1,f 2,f 3))(x 1,x 2,x 3)=(f 1(x 1,x 2),f 2(x 2,x 1),f 3(x 3,x 2)). \displaystyle{ ({{I}}(f_1,f_2, f_3))\,(x_1,x_2, x_3) = (f_1(x_1,x_2), f_2(x_2,x_1), f_3(x_3,x_2)). }

To summarize: a dynamical system on a network of regions is the data (G,P,(w a) aG 0) (G, { P}, (w_a)_{a\in G_0} ) where G={G 1G 0} G=\{G_1\rightrightarrows G_0\} is a directed graph, P:P:G 0Region { P}:{ P}:G_0\to {{Region}} is a phase space function and (w a) aG 0 (w_a)_{a\in G_0} is a collection of open systems compatible with the graph and the phase space function. The corresponding vector field on the total space of the network is obtained by interconnecting the open systems.

Dynamical systems on networks can be turned into a category. Carrying this out gives us a way to associate maps of dynamical systems to combinatorial data.

The first step is to form the category of networks of regions, which we call Graph/Region. {{Graph}}/{{Region}}. In this category, by definition, a morphism from a network (G,P) (G,{ P}) to a network (G,P) (G', { P}') is a map of directed graphs φ:GG \varphi:G\to G' which is compatible with the phase space functions:

Pφ=P. \displaystyle{ { P}'\circ \varphi = { P}. }

Using the universal properties of products it is easy to show that a map of networks φ:(G,P)(G,P) \varphi: (G,{ P})\to (G',{ P}') defines a map φ {\mathbb{P}}\varphi of total phase spaces in the opposite direction:

φ:GG. \displaystyle{ {\mathbb{P}} \varphi: {\mathbb{P}} G' \to {\mathbb{P}} G. }

In the category theory language the total phase space assignment extends to a contravariant functor

:(Graph/Region) opRegion. \displaystyle{ {\mathbb{P}}: {({{Graph}}/{{Region}})}^{op} \to {{Region}}. }

We call this functor the total phase space functor. In our running example, the map

φ:=(G,P) 3=(G,P) {\mathbb{P}}\varphi:{\mathbb{R}} = {\mathbb{P}}(G',{ P}') \to {\mathbb{R}}^3 = {\mathbb{P}} (G,{ P})

is given by

φ(x)=(x,x,x). \displaystyle{ {\mathbb{P}} \varphi (x) = (x,x,x). }

Continuous-time dynamical systems also form a category, which we denote by DS {DS}. The objects of this category are pairs consisting of a region and a vector field on the region. A morphism in this category is a smooth map of regions that intertwines the two vector fields. That is

Hom DS((M,X),(N,Y))={f:MNDfX=Yf} \mathrm{Hom}_{DS} ((M,X), (N,Y)) = \{f:M\to N \mid Df \circ X = Y\circ f\}

for any pair of objects (M,X),(N,Y) (M,X), (N,Y) in DS {DS}. In general morphisms in this category are difficult to determine explicitly. For example if (M,X)=((a,b),ddt) (M, X) = ((a,b), \frac{d}{dt}) then a morphism from (M,X) (M,X) to some dynamical system (N,Y) (N,Y) is simply a piece of an integral curve of the vector field Y Y defined on an interval (a,b) (a,b). And if (M,X)=(S 1,ddθ) (M, X) = (S^1, \frac{d}{d\theta}) is the constant vector field on the circle then a morphism from (M,X) (M,X) to (N,Y) (N,Y) is a periodic orbit of Y Y. Proving that a given dynamical system has a periodic orbit is usually hard.

Consequently, given a map of networks

φ:(G,P)(G,P) \varphi:(G,{ P})\to (G',{ P}')

and a collection of open systems

{w a} aG 0 \{w'_{a'}\}_{a'\in G'_0}

on (G,P) (G',{ P}') we expect it to be very difficult if not impossible to find a collection of open systems {w a} aG 0 \{w_a\}_{a\in G_0} so that

φ:(G,I(w))(G,I(w)) \displaystyle{ {\mathbb{P}} \varphi: ({\mathbb{P}} G', {{I}}' (w'))\to ({\mathbb{P}} G, {{I}} (w)) }

is a map of dynamical systems.

It is therefore somewhat surprising that there is a class of maps of graphs for which the above problem has an easy solution. The graph maps of this class are known by several different names. Following Boldi and Vigna we refer to them as graph fibrations. Note that despite what the name suggests, graph fibrations in general are not required to be surjective on nodes or edges. For example the inclusion

is a graph fibration. We say that a map of networks

φ:(G,P)(G,P) \varphi:(G,{ P})\to (G',{ P}')

is a fibration of networks if φ:GG \varphi:G\to G' is a graph fibration. With some work one can show that a fibration of networks induces a pullback map

φ *: bG 0Ctrl(I(b)b) aG 0Ctrl(I(a)a) \displaystyle{ \varphi^*: \bigsqcap_{b\in G_0'} {Ctrl}({\mathbb{P}} I(b)\to {\mathbb{P} b) \to \bigsqcap_{a\in G_0} {Ctrl}({\mathbb{P}}} I(a)\to {\mathbb{P}} a) }

on the sets of tuples of the associated open systems. The main result of Dynamics on networks of manifolds is a proof that for a fibration of networks φ:(G,P)(G,P) \varphi:(G,{ P})\to (G',{ P}') the maps φ * \varphi^*, φ {\mathbb{P}} \varphi and the two interconnection maps I {{I}} and I {{I}}' are compatible:

Theorem. Let φ:(G,P)(G,P) \varphi:(G,{ P})\to (G',{ P}') be a fibration of networks of manifolds. Then the pullback map

φ *:Ctrl(G,P)Ctrl(G,P) \displaystyle{ \varphi^*: {Ctrl}(G',{ P}')\to {Ctrl}(G,{ P}) }

is compatible with the interconnection maps

I:Ctrl(G,P))Γ(TG)andI:(Ctrl(G,P))Γ(TG). \displaystyle{ {{I}}': {Ctrl}(G',{ P}')) \to \Gamma (T{\mathbb{P}} G') \quad and \quad {{I}}: ({Ctrl}(G,{ P})) \to \Gamma (T{\mathbb{P}} G). }

Namely for any collection wCtrl(G,P) w'\in {Ctrl}(G',{ P}') of open systems on the network (G,P) (G', { P}') the diagram

commutes. In other words,

φ:((G,P),I(w))((G,P),I(φ *w)) \displaystyle{ {\mathbb{P}} \varphi: ({\mathbb{P}} (G',{ P}'), {{I}}' (w'))\to ({\mathbb{P}} (G, { P}), {{I}} (\varphi^* w')) }

is a map of continuous time dynamical systems, a morphism in DS {DS}.

category: blog