Complex Adaptive System Design (Part 4)

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 G there is an operad O_G 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 G to be the network model for simple graphs, and look at the network operad O_G. I won’t tell you what kind of thing G is yet! But I’ll tell you about the operad O_G.

Types. Remember from last time that an operad has a set of ‘types’. For O_G this is the set of natural numbers, \mathbb{N}. 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 O_G(t_1,\dots,t_n ; t) for each choice of t_1,\dots,t_n, t \in \mathbb{N}.

An operation f \in O_G(t_1,\dots,t_n; t) is a way of taking a simple graph with t_1 vertices, a simple graph with t_2 vertices,… and so on, and sticking them together, perhaps adding new edges, to get a simple graph with

t = t_1 + \cdots + t_n

vertices.

Let me show you an operation

f \in O_G(3,4,2;9)

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 f 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 f 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 O_G 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 t \in \mathbb{N} I’m letting the set of things A(t) consist of all simple graphs with vertices \{1, \dots, t\}.

Action. Remember that our operad O_G should have an action on A, meaning a bunch of maps

\alpha : O_G(t_1,...,t_n ; t) \times A(t_1) \times \cdots \times A(t_n) \to A(t)

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 O_G(t_1,\dots,t_n ; t) if t \ne  t_1 + \cdots + t_n?

Puzzle 2. In this example, how many elements does O_G(1,1;2) have?

Puzzle 3. In this example, how many elements does O_G(1,2;3) have?

Puzzle 4. In this example, how many elements does O_G(1,1,1;3) have?

Puzzle 5. In the particular algebra A that I explained, how many elements does A(3) have?

Next time I’ll describe some more interesting algebras of this operad O_G. These let us describe networks of mobile agents with range-limited communication channels!

7 Responses to Complex Adaptive System Design (Part 4)

  1. arch1 says:

    At worst I’ll be a straight man:
    1) empty set (since sticking graphs together doesn’t create or destroy vertices)
    2-4) 2^P(t,2) (since each pair of distinguishable vertices can independently be joined by an arc, or not)
    5) 2^P(3,2)=8 (same reason)

    • arch1 says:

      Replace “P” with “C” in my answers (the vertices are distinguishable but their order within the pair doesn’t matter)

    • John Baez says:

      arch1 wrote:

      At worst I’ll be a straight man.

      Like a comedian, every mathematician seems more funny with a straight man.

      1) empty set (since sticking graphs together doesn’t create or destroy vertices).

      Right!

      2)-4) 2^C(t,2) (since each pair of distinguishable vertices can independently be joined by an arc, or not)

      If C(t,2) means the binomial coefficient $\binom{t}{2}$, then you’re right! If

      t_1 + \cdots + t_n = t

      then O_G(t_1, \dots, t_n ; t) is the set of simple graphs with t vertices, so its cardinality is

      \displaystyle{ 2^{\binom{t}{2}} }

      5) 2^C(3,2)=8 (same reason)

      Right again! In this example A(t) is also the set of simple graphs wiht t vertices, so its cardinality is also

      \displaystyle{ 2^{\binom{t}{2}} }

      Moral: In this particular example, the algebra is very similar to the operad it’s an algebra of. That’s not always true, but every typed operad O has an algebra of this kind, with

      A(t) = O(t;t)

  2. @whut says:

    (1) ?
    (2) 3
    (3) 3
    (4) 4
    (5) 3

  3. I think you underrate the importance of directionality in the communications channels. Quite generally, in networks representing the execution of business processes, if A talks to B but B does not talk to A, that fact is highly significant; and if B does talk to A, it is for a different reason and it transports a payload of a different type. I do not have any insight into the manner in which this distinction would be expressed in the formalism that you are explaining here and I apologize if this entire comment is a forward reference to a topic that you will introduce later on.

    • John Baez says:

      In this post I’m using simple graphs as an example of how operads can be used to assemble networks. Simple graphs have undirected edges. But they’re just one example of our approach. For networks where communication channels are directed, we use graphs that take this into account: for example, ‘directed graphs’.

      Here’s what I said about this issue… with some emphasis added at points where I address the issue you raise:

      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.

      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.

      I’ll explain the general concept of ‘network model’ later. First I want to illustrate some things you can do with network models, and I’ll do that next time using simple graphs. But fear not—our setup can handle a wide variety of networks.

  4. When we have a ‘less detailed’ algebra A and a ‘more detailed’ algebra A', they will typically be related by a map

    f : A' \to A

    which ‘forgets the extra details’. This map should be a ‘homomorphism’ of algebras, but I’ll postpone the definition of that concept.

    Let me give some examples. I’ll take the operad that I described last time, and describe some of its algebras, and homomorphisms between these.

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