20 Triads
20.1 Types of Undirected Triads
We could do the same thing we did with dyads (subgraphs of order two) with the different subgraphs of order three in an undirected graph. These are called undirected triads.
Take for instance, the subgraph defined by nodes B, C, and F in the graph shown in Figure 6.1. This is shown in Figure 20.1. It shows three people who are not connected to one another! Like strangers in a park sitting on three different benches. This is called the null triad.
Now let’s define a subgraph using nodes A, C, and E. The resulting triad is shown in Figure 20.2. Now this looks like a pair of friends A and C, in the same room with a stranger (E) whom they are not acquainted with. You may have experienced this before at a social gathering. This is called the disconnected triad. It is disconnected, because the subgraph formed by the three nodes is disconnected, as defined earlier; there is no way that either A or C can reach E, given that E is an isolate in the subgraph.
We can continue. Let’s define a subgraph from the larger graph in shown in Figure 6.1, but this time we will pick nodes A, B, and C. What comes out? This is shown in Figure 20.3. This time, there is one person, node A, who is acquainted with two other people, nodes B and C, but they don’t seem to know one another. It’s like when you have friends from work and friends from school who have never met. This is called the open triad, because even though the subgraph is connected (there are no isolate nodes like in Figure 20.2, there is a “open hole” in the triad separating nodes B and C. Perhaps A should introduce their friends to one another!
One last one. Let’s define a subgraph from Figure 6.1, but this time let’s pick nodes A, D, and F. The result is shown in Figure 20.4. Now we have three friends all of whom know one another! So there are three distinct pairs of relations in the triad: AD, AF and DF.
Figure 20.4 is what we would see for that group of three friends that always seems to hang out together. This is called the closed triad, because there is no room to add more links to it. It is also called the closed triad because it is the configuration you get when you add a final link to the open triad (thus “closing” it). As discussed in Chapter 11, a closed triad is also a cycle of length three.
Figure 20.5 shows the four types of undirected triads using unlabeled subgraphs. The key point is that in an undirected graph, there can only be these four types of triads. So every threesome of actors is part of a null, disconnected, open, or closed triad.
All four triads are subgraphs of the same order (three), but they are different in size. The null triad is size zero, the disconnected triad is size one, the open triad is size two, and the closed triad is size three.
Dyads, triads, and subgraphs of higher order (called network motifs) are the building blocks of larger network structures in society (Milo et al. 2002).
20.2 Types of Directed Triads
Just in the same way we can enumerate all the directed triads that exist in a directed graph, we can do the same for subgraphs of order three, namely triads. However, now that we are talking about threesomes, things get more complicated because we have a larger number of combinations to deal with. Let us go through them.
First, it is useful to think about what we are dealing with. First, with a subgraph of order three we have three “slots” in the structure to consider. Each of these slots is a directed dyad. Thus, a triad can also be thought of as a concatenation of three directed dyads. That means that in a directed dyad, each of the slots can only be in on of three states (just like regular directed dyads): It can be mutual (M), asymmetric (A), or null (N)!
20.2.1 The Null Triad
So we know that right off the bat, one of the configurations is just going to be composed of three null dyads. Let’s call it \(NNN\), and is going to look like just like the null dyad in the directed case (see Figure 20.1.
20.2.2 Disconnected Directed Triads
Another set of configurations is going to be composed disconnected directed triads that are going to feature one connected dyad and two null dyads. Let’s call them \(NNC\). However, while there was only one such configuration in the undirected triad case, there’s going to be two in the directed triad case, because there are two kinds of directed connected dyads (asymmetric and mutual). So, one of the disconnected directed triads is going to have two null dyads and one asymmetric connected dyad. It looks like Figure 20.6. The other one is going to have two null dyads and a mutual connected dyad. It’s going to look like Figure 20.7. That’s it for the two null dyad configurations. We have collected a total of three directed triadic configurations so far!
20.2.3 Open Directed Triads
Now let’s think about directed triadic configurations featuring two asymmetric directed edges and one null dyad. These are directed versions of the open triad we considered in the undirected case. Here things get a bit interesting because edge directionality generates distinct configurations even when the number of links within the triad is the same (in this case two). So let’s call this configuration set \(AAN(*)\), where the \(*\) will be substituted with a letter to distinguish between the different arrangements.
In one set up, we have a person who directs an asymmetric edge to another person, and this person directs an asymmetric edge to a third. This is called the directed line, so let’s call this triad \(NNA(L)\), where “L” stands for “Line.” It looks like Figure 20.8. Think of when someone tells you a secret and then you tell someone else.
In another set up, we have a person who directs two asymmetric edges at two people at the same time. This is called the out star, so let’ call this triad \(NNA(O)\), where “O” stands for “out-star.” It looks like Figure 20.9. Think of you sending a text to two of your friends on a groupchat.
In yet another set up, we have two people who direct two asymmetric edges to a third person at the same time. This is called (you guessed it) the in star, so let’ call this triad \(NNA(I)\), where “I” stands for “in-star.” It looks like Figure 20.10. Think of two of your friends performing an intervention on you.
With these three additional entries, our total set of directed triadic configurations has grown to six!
Now, let’s consider cases where: (a) the triad is both connected and open, and (b) there is one mutual dyad in the triad. There are two of these cases (let’s call them \(MAN1\), and \(MAN2\)). These are less interesting because only difference is whether the asymmetric edge is going in one direction or the other direction. These cases are shown in Figure 20.11.
Finally, let’s consider the case where: (a) the triad is both connected and open, and (b) there are two mutual dyad in the triad. There is only one case like this (let’s call it \(MMN\)), and is shown in Figure 20.12.
Notably, these three additional configurations brings our total to nine (with six of these being versions of open directed triads)
20.2.4 Closed Directed Triads
Now, let’s consider the cases of closed directed triads. These are triads featuring three connected dyads. Once again, there was only one option in the undirected case, but there’s a much larger number in the directed case because dyads can be connected in two ways (asymmetric and mutual). Let us take the configurations featuring three asymmetric links and called the \(AAA(*)\), where the \(*\) will be substituted with a letter to distinguish between the different arrangements.
In one setup, we have a person who directs an asymmetric edge to another person, this person directs an asymmetric edge to a third, and this third person directs an asymmetric edge back to the first person! As we will see later, this is called a cycle, so let’s call this triad \(AAA(C)\), where “C” stands for “cycle.” It looks like Figure 20.13.
In another setup, we have a person who directs two asymmetric edges to two other people, who are themselves connected by an asymmetric edge. Let’s call this triad \(AAA(I/O)\). Why this weird name? Well if you look at Figure 20.14, this triad combines both the in and out start configurations! In the Figure, node A is the out-star and node C is the in-star. Hence \(AAA(I/O)\), where “I/O” stands for “in/out.”
So these two configurations brings our total to eleven so far! We are almost getting there.
Now let’s consider directed triadic configurations that are: (a) closed and (b) feature exactly one mutual dyad. Since the triad is closed, we therefore know that the other two non-mutual dyads will be joined by an asymmetric link (no null dyads). Let’s call this generic set \(MAA(*)\) triads, where the \(*\) will be substituted with a letter to distinguish between the different arrangements.
Let’s ignore the mutual dyad and focus on the nodes joined by asymmetric links (\(AA\)). We know from our consideration of open triads containing asymmetric links (Figure 20.8, Figure 20.9, and Figure 20.10 above) that there are only three ways nodes in a triad can be connected via asymmetric links: 1) the line, 2), the out-star, and the in-star. So that’s exactly how many triads of these type are there. We can call them \(MAA(L)\), \(MAA(O)\), and \(MM(I)\) and they are shown in Figure 20.15.
These three additional configurations bring our total number of directed triadic configurations to fourteen! Are we done counting directed triad types?
We aren’t. We still have to consider a (final) set of triadic configurations, namely, closed triads containing at least two mutual dyads. Now, since these triads will all have two mutuals and are closed, their only distinguishing feature will be the nature of the third connected dyad. Since connected dyads can only take on of two states (Asymmetric or Mutual), then we know there will also be two subtypes: \(MMA\) (two mutual dyads with a third asymmetric dyad), and \(MMM\) (the triad with all mutual dyads!). These are shown in Figure 20.16. So, with these two triads, the true (and final) number of directed triadic configurations is sixteen!
The full sixteen-member set of possible directed triadic subgraphs is shown in Figure 20.17.
References
Milo, Ron, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. “Network Motifs: Simple Building Blocks of Complex Networks.” Science 298 (5594): 824–27.