Making Indirect Interactions Explicit in Networks

Category theory provides a language for explicitly describing indirect relationships in graphs.

Want to get notified about new posts? Join the mailing list.

After reading about Ehresmann & Vanbremeersch’s Memory Evolutive Systems and Robert Rosen’s Relational Biology, I tried to come up with some concrete takeaways. The main theme seemed to be that category theory provides a language for explicitly describing indirect relationships in graphs.

Networks as Graphs

Networks, or collections of interacting components, are ubiquitous: societies are networks of people, which are networks of cells, which are networks of molecules, which are networks of particles. Networks are often modeled as weighted graphs, collections of vertices connected by edges, where each edge is assigned a weight (usually a real number). Each vertex $A$ represents a network component, each edge $A \xleftarrow{f} B$ represents direct interaction in which $A$ receives $f$ from $B$ (or $B$ sends $f$ to $A$), and the weight $w(f)$ quantifies some property of $f$. For example, if $A$ and $B$ are dominoes, then $f$ could be the action of $A$ being toppled by $B$, and $w(f)$ could be the probability that $A$ will fall if $B$ falls.

However, many networks have properties that are not immediately obvious from their graphical representations. Perhaps $B$ can be toppled by another domino, $C$, which is too far away to topple $A$. When $C$ falls, it initiates a chain of topples that causes $A$ to fall: $C$ topples $B$, and $B$ topples $A.$ There is no arrow $A \leftarrow C,$ though, because $C$ cannot itself hit $A.$

In real-world networks, hidden properties can be meaningful. For example, the targeted dissemination of information through social networks relies on the existence of indirect connections. To this end, it can be helpful to explicitly represent the indirect interactions that graph-theoretic models leave implicit.

Weighted Categories

Category theory [2], an approach to mathematics that describes mathematical objects in terms relationships to other objects (rather than their internal specifics), has been used to describe properties of biological systems [1,3-5] and can be used to restructure graphs so that all interactions, both direct and indirect, are made explicit. Weighted categories are similar to weighted graphs, except that vertices are called objects and edges are called arrows, the weights of arrows are functions rather than real numbers, and any two arrows with the same source and target need not be equivalent. Intuitively, a weighted category $\mathcal{C}$ can be described as

1. a collection $Ob(\mathcal{C})$ of objects, together with
2. a collection $Hom(\mathcal{C})$ of arrows $A \xleftarrow{f} B$ between objects, where each arrow $f$ points from a single sending object $B$ to a single receiving object $A$ and has weight $w(f)$.

In mathematical settings, arrows are also called homomorphisms, hence the notation $Hom(C).$ The arrows of a category must additionally satisfy the following criteria:

1. For any sequence $A_1 \xleftarrow{f_1} \cdots \xleftarrow{f_n} A_{n+1}$ of head-to-toe adjacent arrows, there is a single composite arrow $A_1 \xleftarrow{f_1f_2\cdots f_n} A_{n+1}.$
2. For each object $X,$ there is an identity arrow $X \xleftarrow{i_X} X,$ and composite arrows are the same regardless of whether identity arrows are included.
3. The weights satisfy some weight composition rule $(\cdot)$ so that $w(f_1f_2 \cdots f_n) = w(f_1) \cdot w(f_2) \cdot \cdots \cdot w(f_n).$

A careful reader will notice ambiguity in criterion (1):

• the arrow obtained by composing $f_1,$ $f_2,$ and $f_3$ is called $f_1f_2f_3,$
• the arrow obtained by composing $f_1$ and $f_2f_3$ is called $f_1f_2f_3,$ and
• the arrow obtained by composing $f_1f_2$ and $f_3$ is called $f_1f_2f_3.$

This ambiguity is deliberate, because the actual mathematical definition of a category requires that all three “versions” of $f_1f_2f_3$ are indistinguishable and hence coincide.

A concrete example of criterion (2) is that the arrows $f_1 f_2,$ $i_1 f_1 f_2,$ $f_1 i_2 f_2,$ $f_1 f_2 i_3,$ $i_1 f_1 i_2 f_2,$ $i_1 f_1 f_2 i_3,$ and $i_1 f_1 i_2 f_2 i_3$ all coincide.

In criterion (3), simple weight rules include, but are not limited to, addition or multiplication. A straightforward consequence of (3) is that all identity arrows are assigned the same weight, called the identity weight.

Converting Graphs to Categories

Given a weighted graph network model, where vertices in a set $V$ represent network components and edges in a set $E$ represent direct interactions, one can generate a weighted category $\mathcal{C}$ whose arrows represent all communication, both direct and indirect, that occurs in the network. One does this by choosing $Ob(\mathcal{C}) = V$ and generating $Hom(\mathcal{C})$ according to the following steps:

1. Include edge arrows. For each edge $f$ in $E$, include $f$ in $Hom(\mathcal{C}).$
2. Include identity arrows. For each vertex $X$ in $V$, include $i_X$ in $Hom(\mathcal{C}).$ Identity edges and identity arrows must coincide.
3. Include composite arrows. For each sequence of head-to-toe adjacent arrows $f_1, f_2 ..., f_n$ in $Hom(\mathcal{C}),$ include the composite arrow $f_1 f_2 \cdots f_n$ in $Hom(\mathcal{C}).$

The weights are specified entirely by our choice of weight composition rule: since identity arrows are all assigned the identity weight and all other noncomposite arrows can be identified as edges, the rule $w(f_1f_2 \cdots f_n) = w(f_1) \cdot w(f_2) \cdot \cdots \cdot w(f_n)$ specifies the weight of every composite arrow.

The choice of weight composition rule often depends on the modeling context. For example, suppose that in the category of economic entities, $A$ is a manufacturer, $B$ is a middleman, and $C$ is a customer who wants a product from the manufacturer $A.$ In this category, each arrow might represent a sale, and the weight of an arrow might be the amount spent by the buyer. In this case, the amount spent by the final buyer in a sequence of exchanges depends only on the final exchange, so the weight composition rule should be chosen as $w(f) \cdot w(g) = w(f)$ for composable weights $f$ and $g,$ so that

References

[1] Ehresmann, A. C., & Vanbremeersch, J. P. (2007). Memory evolutive systems; hierarchy, emergence, cognition (Vol. 4). Elsevier.

[2] Eilenberg, S., & MacLane, S. (1945). General theory of natural equivalences. Transactions of the American Mathematical Society, 231-294.

[3] Rosen, R. (1958). The representation of biological systems from the standpoint of the theory of categories. The bulletin of mathematical biophysics, 20(4), 317-341.

[4] Rosen, R. (1958). A relational theory of biological systems. The bulletin of mathematical biophysics, 20(3), 245-260.

[5] Rosen, R. (1959). A relational theory of biological systems II. The bulletin of mathematical biophysics, 21(2), 109-128

Want to get notified about new posts? Join the mailing list.