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 of ‘vertex colors’, a **network model** is a lax symmetric monoidal functor

where is the free strict symmetric monoidal category on and is the category of small categories.

Unpacking this somewhat terrifying definition takes a little work. It simplifies in the special case where takes values in the category of monoids. It simplifies further when is a singleton, since then is the groupoid where objects are natural numbers and morphisms from to are bijections

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

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 ‘networks with vertices’, then:

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

• Since is a functor, the symmetric group acts on the monoid Thus, for each , we have a monoid automorphism that we call simply

• Since is lax monoidal, we also have an operation

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’

holds whenever and 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 of network models, and show that the procedure for getting network models from monoids is functorial. We also make 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 of a functor

where is any small category. For example, if is symmetric monoidal and is lax symmetric monoidal, then we show is symmetric monoidal. Moreover, we show that the construction sending the lax symmetric monoidal functor to the symmetric monoidal category 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!

Some posts in this series:

• Part 1. CASCADE: the Complex Adaptive System Composition and Design Environment.

• Part 2. Metron’s software for system design.

• Part 3. Operads: the basic idea.

• Part 4. Network operads: an easy example.

• Part 5. Algebras of network operads: some easy examples.

• Part 6. Network models.

• Part 7. Step-by-step compositional design and tasking using commitment networks.

• Part 8. Compositional tasking using category-valued network models.

• Part 9 – Network models from Petri nets with catalysts.

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 must be quick! I fixed the link about 10 minutes after posting this article. It seems to work fine now.

Thanks!

Hi,

On the page 11 of the preprint, theorem 12, third dot, I believe you wrote “x” instead of “e”: .

Also, on page 8 of the preprint, I wonder if the diagram of permutations (1526374) is upside down, or if it is the way people in the area draw them.

Hi! Yes, those three x’s should be e’s. Thanks! A fixed version is here.

Thanks for noticing that the diagram of the permutation is ‘upside down’. Of course it’s just a convention, but I personally prefer to read the permutation from top to bottom, like you. I will argue with my coauthors, if necessary.

Joseph Moeller is a grad student at U.C. Riverside working with me and a company called Metron Scientific Solutions on “network models”—a framework for designing networks, which the Coast Guard is already interested in using for their search and rescue missions:

• John C. Baez, John Foley, Joseph Moeller and Blake S. Pollard, Network Models. (Blog article here.)

John Foley has been working out some nice example problems where a collection of agents need to move along the edges of a graph from specified start locations to specified end locations, taking routes that minimize their total fuel usage. However, there are some constraints. Some edges can only be traversed by specified

teamsof agents: they can’t go alone. Also, no one agent is allowed to run out of fuel.This is a nice problem because while it’s pretty simple and specific, it’s representative of a large class of problems where a collection of agents are trying to carry out tasks together. ‘Moving along the edge of a graph’ can stand for a task of any sort. The constraint that some edges can only be traversed by specified teams is then a way of saying that certain tasks can only be accomplished by teams.

Furthermore, there are nice software packages for optimization subject to constraints. For example, John likes one called Choco. So, we plan to use one of these as part of the project.

What makes this all

compositionalis that John has expressed this problem using our ‘network model’ formalism, which I began sketching in Part 6. This allows us to assemble tasks for larger collections of agents from tasks for smaller collections.