Last time I introduced typed operads. A typed operad has a bunch of operations for putting together things of various types and getting new things of various types. This is a very general idea! But in the CASCADE project we’re interested in something more specific: networks. So we want operads whose operations are ways to put together networks and get new networks.
That’s what our team came up with: John Foley of Metron, my graduate students Blake Pollard and Joseph Moeller, and myself. We’re writing a couple of papers on this, and I’ll let you know when they’re ready. These blog articles are kind of sneak preview—and a gentle introduction, where you can ask questions.
For example: I’m talking a lot about networks. But what is a ‘network’, exactly?
There are many kinds. At the crudest level, we can model a network as a simple graph, which is something like this:
There are some restrictions on what counts as a simple graph. If the vertices are agents of some sort and the edges are communication channels, these restrictions imply:
• We allow at most one channel between any pair of agents, since there’s at most one edge between any two vertices of our graph.
• The channels do not have a favored direction, since there are no arrows on the edges of our graph.
• We don’t allow a channel from an agent to itself, since an edge can’t start and end at the same vertex.
For other purposes we may want to drop some or all of these restrictions. There is an appalling diversity of options! We might want to allow multiple channels between a pair of agents. For this we could use multigraphs. We might want to allow directed channels, where the sender and receiver have different capabilities: for example, signals may only be able to flow in one direction. For this we could use directed graphs. And so on.
We will also want to consider graphs with colored vertices, to specify different types of agents—or colored edges, to specify different types of channels. Even more complicated variants are likely to become important as we proceed.
To avoid sinking into a mire of special cases, we need the full power of modern mathematics. Instead of separately studying all these various kinds of networks, we need a unified notion that subsumes all of them.
To do this, the Metron team came up with something called a ‘network model’. There is a network model for simple graphs, a network model for multigraphs, a network model for directed graphs, a network model for directed graphs with 3 colors of vertex and 15 colors of edge, and more.
You should think of a network model as a kind of network. Not a specific network, just a kind of network.
Our team proved that for each network model
there is an operad
whose operations describe how to put together networks of that kind. We call such operads ‘network operads’.
I want to make all this precise, but today let me just show you one example. Let’s take
to be the network model for simple graphs, and look at the network operad
I won’t tell you what kind of thing
is yet! But I’ll tell you about the operad
.
• Types. Remember from last time that an operad has a set of ‘types’. For
this is the set of natural numbers,
The reason is that a simple graph can have any number of vertices.
• Operations. Remember that an operad has sets of ‘operations’. In our case we have a set of operations
for each choice of 
An operation
is a way of taking a simple graph with
vertices, a simple graph with
vertices,… and so on, and sticking them together, perhaps adding new edges, to get a simple graph with

vertices.
Let me show you an operation

This will be a way of taking three simple graphs—one with 3 vertices, one with 4, and one with 2—and sticking them together, perhaps adding edges, to get one with 9 vertices.
Here’s what
looks like:
It’s a simple graph with vertices numbered from 1 to 9, with the vertices in bunches: {1,2,3}, {4,5,6,7} and {8,9}. It could be any such graph. This one happens to have an edge from 3 to 6 and an edge from 1 to 2.
Here’s how we can actually use our operation. Say we have three simple graphs like this:
Then we can use our operation to stick them together and get this:
Notice that we added a new edge from 3 to 6, connecting two of our three simple graphs. We also added an edge from 1 to 2… but this had no effect, since there was already an edge there! The reason is that simple graphs have at most one edge between vertices.
But what if we didn’t already have an edge from 1 to 2? What if we applied our operation
to the following simple graphs?
Well, now we’d get this:
This time adding the edge from 1 to 2 had an effect, since there wasn’t already an edge there!
In short, we can use this operad to stick together simple graphs, but also to add new edges within the simple graphs we’re sticking together!
When I’m telling you how we ‘actually use’ our operad to stick together graphs, I’m secretly describing an algebra of our operad. Remember, an operad describes ways of sticking together things together, but an ‘algebra’ of the operad gives a particular specification of these things and describes how we stick them together.
Our operad
has lots of interesting algebras, but I’ve just shown you the simplest one. More precisely:
• Things. Remember from last time that for each type, an algebra specifies a set of things of that type. In this example our types are natural numbers, and for each natural number
I’m letting the set of things
consist of all simple graphs with vertices 
• Action. Remember that our operad
should have an action on
, meaning a bunch of maps

I just described how this works in some examples. Some rules should hold… and they do.
To make sure you understand, try these puzzles:
Puzzle 1. In the example I just explained, what is the set
if 
Puzzle 2. In this example, how many elements does
have?
Puzzle 3. In this example, how many elements does
have?
Puzzle 4. In this example, how many elements does
have?
Puzzle 5. In the particular algebra
that I explained, how many elements does
have?
Next time I’ll describe some more interesting algebras of this operad
These let us describe networks of mobile agents with range-limited communication channels!
The whole series of posts:
• 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.
• Part 10 – Two papers reviewing the whole project.