Complex Adaptive Systems (Part 6)

I’ve been slacking off on writing this series of posts… but for a good reason: I’ve been busy writing a paper on the same topic! In the process I caught a couple of mistakes in what I’ve said so far. But more importantly, there’s a version out now, that you can read:

• John Baez, John Foley, Blake Pollard and Joseph Moeller, Network models.

There will be two talks about this at the AMS special session on Applied Category Theory this weekend at U. C. Riverside: one by John Foley of Metron Inc., and one by my grad student Joseph Moeller. I’ll try to get their talk slides someday. But for now, here’s the basic idea.

Our goal is to build operads suited for designing networks. These could be networks where the vertices represent fixed or moving agents and the edges represent communication channels. More generally, they could be networks where the vertices represent entities of various types, and the edges represent relationships between these entities—for example, that one agent is committed to take some action involving the other. This paper arose from an example where the vertices represent planes, boats and drones involved in a search and rescue mission in the Caribbean. However, even for this one example, we wanted a flexible formalism that can handle networks of many kinds, described at a level of detail that the user is free to adjust.

To achieve this flexibility, we introduced a general concept of ‘network model’. Simply put, a network model is a kind of network. Any network model gives an operad whose operations are ways to build larger networks of this kind by gluing smaller ones. This operad has a ‘canonical’ algebra where the operations act to assemble networks of the given kind. But it also has other algebras, where it acts to assemble networks of this kind equipped with extra structure and properties. This flexibility is important in applications.

What exactly is a ‘kind of network’? That’s the question we had to answer. We started with some examples, At the crudest level, we can model networks as simple graphs. If the vertices are agents of some sort and the edges represent communication channels, this means we allow at most one channel between any pair of agents.

However, simple graphs are too restrictive for many applications. If we allow multiple communication channels between a pair of agents, we should replace simple graphs with ‘multigraphs’. Alternatively, we may wish to allow directed channels, where the sender and receiver have different capabilities: for example, signals may only be able to flow in one direction. This requires replacing simple graphs with ‘directed graphs’. To combine these features we could use ‘directed multigraphs’.

But none of these are sufficiently general. It’s also important to consider graphs with colored vertices, to specify different types of agents, and colored edges, to specify different types of channels. This leads us to ‘colored directed multigraphs’.

All these are examples of what we mean by a ‘kind of network’, but none is sufficiently general. More complicated kinds, such as hypergraphs or Petri nets, are likely to become important as we proceed.

Thus, instead of separately studying all these kinds of networks, we introduced a unified notion that subsumes all these variants: a ‘network model’. Namely, given a set C of ‘vertex colors’, a network model is a lax symmetric monoidal functor

F: \mathbf{S}(C) \to \mathbf{Cat}

where \mathbf{S}(C) is the free strict symmetric monoidal category on C and \mathbf{Cat} is the category of small categories.

Unpacking this somewhat terrifying definition takes a little work. It simplifies in the special case where F takes values in \mathbf{Mon}, the category of monoids. It simplifies further when C is a singleton, since then \mathbf{S}(C) is the groupoid \mathbf{S}, where objects are natural numbers and morphisms from m to n are bijections

\sigma: \{1,\dots,m\} \to \{1,\dots,n\}

If we impose both these simplifying assumptions, we have what we call a one-colored network model: a lax symmetric monoidal functor

F : \mathbf{S} \to \mathbf{Mon}

As we shall see, the network model of simple graphs is a one-colored network model, and so are many other motivating examples. If you like André Joyal’s theory of ‘species’, then one-colored network models should be pretty fun, since they’re species with some extra bells and whistles.

But if you don’t, there’s still no reason to panic. In relatively down-to-earth terms, a one-colored network model amounts to roughly this. If we call elements of F(n) ‘networks with n vertices’, then:

• Since F(n) is a monoid, we can overlay two networks with the same number of vertices and get a new one. We call this operation

\cup \colon F(n) \times F(n) \to F(n)

• Since F is a functor, the symmetric group S_n acts on the monoid F(n). Thus, for each \sigma \in S_n, we have a monoid automorphism that we call simply

\sigma \colon F(n) \to F(n)

• Since F is lax monoidal, we also have an operation

\sqcup \colon F(m) \times F(n) \to F(m+n)

We call this operation the disjoint union of networks. In examples like simple graphs, it looks just like what it sounds like.

Unpacking the abstract definition further, we see that these operations obey some equations, which we list in Theorem 11 of our paper. They’re all obvious if you draw pictures of examples… and don’t worry, our paper has a few pictures. (We plan to add more.) For example, the ‘interchange law’

(g \cup g') \sqcup (h \cup h') = (g \sqcup h) \cup (g' \sqcup h')

holds whenever g,g' \in F(m) and h, h' \in F(n). This is a nice relationship between overlaying networks and taking their disjoint union.

In Section 2 of our apper we study one-colored network models, and give lots of examples. In Section 3 we describe a systematic procedure for getting one-colored network models from monoids. In Section 4 we study general network models and give examples of these. In Section 5 we describe a category \mathbf{NetMod} of network models, and show that the procedure for getting network models from monoids is functorial. We also make \mathbf{NetMod} into a symmetric monoidal category, and give examples of how to build new networks models by tensoring old ones.

Our main result is that any network model gives a typed operad, also known as a ‘colored operad’. This operad has operations that describe how to stick networks of the given kind together to form larger networks of this kind. This operad has a ‘canonical algebra’, where it acts on networks of the given kind—but the real point is that it has lots of other algebra, where it acts on networks of the given kind equipped with extra structure and properties.

The technical heart of our paper is Section 6, mainly written by Joseph Moeller. This provides the machinery to construct operads from network models in a functorial way. Category theorists should find this section interesting, because because it describes enhancements of the well-known ‘Grothendieck construction’ of the category of elements \int F of a functor

F: \mathbf{C} \to \mathbf{Cat}

where \mathbf{C} is any small category. For example, if \mathbf{C} is symmetric monoidal and F : \mathbf{C} \to (\mathbf{Cat}, \times) is lax symmetric monoidal, then we show \int F is symmetric monoidal. Moreover, we show that the construction sending the lax symmetric monoidal functor F to the symmetric monoidal category \int F is functorial.

In Section 7 we apply this machinery to build operads from network models. In Section 8 we describe some algebras of these operads, including an algebra whose elements are networks of range-limited communication channels. In future work we plan to give many more detailed examples, and to explain how these algebras, and the homomorphisms between them, can be used to design and optimize networks.

I want to explain all this in more detail—this is a pretty hasty summary, since I’m busy this week. But for now you can read the paper!

3 Responses to Complex Adaptive Systems (Part 6)

  1. Adolfo De Unánue says:

    Hi

    I am a huge fan of this blog series. Thank you for sharing.

    The link to ” John Baez, John Foley, Blake Pollard and Joseph Moeller, Network models.” is broken, Could you point me to the right link?

    Thanks in advance

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s