2.4 Graphs and Subgraphs

Consider the graph shown in Figure 2.4 again. If all the actors that you are interested in studying are included here, we would refer to it as the whole network. However, sometimes, even when we collect data on a large number of actors we may be interested in analyzing not the whole network, but only some parts of it. How do we do that?

A subgraph of an undirected graph Figure 2.5: A subgraph of an undirected graph

Well, good thing that a graph is actually a set of two sets. If you remember your high school set theory, you can always take a set and consider only a subset of the original members.

Since graphs are sets, we can do the same thing. A subset of the original nodes (or edges) of a graph, is called a subgraph. So if \(G =\{E,V\}\) is the original graph, the subgraph \(G' = \{E',V'\}\) is a subset of \(G\), which is written \(G \subset G'\), with the understanding that \(E' \subset E\) and \(V' \subset V\).

Another subgraph of an undirected graph Figure 2.6: Another subgraph of an undirected graph

For instance, let’s say we were interested in just analyzing actors A, B, D, and F in the graph shown in 2.4. They seem to be a close-knit group of people. In that case, as noted earlier, if we call the original graph \(G\) with vertex and edge sets \(\{E, V\}\)we can define a new subgraph \(G'\), whose node subset \(V'\) only includes the actors we are interested in studying, in this case \(V' = \{A, B, D, F\}\), where \(V' \subset V\).

The subgraph \(G'\) is shown in Figure 2.5. It looks exactly like we wanted, capturing the relations between an inter-connected subgroup of actors in the original graph.8 As we will see later, well-connected subgroups of actors of an original graph are called a cohesive subset. Note that the edge set of the subgraph \(E'\) only includes those edges that are incident to the other nodes in the subgraph and omits those in the original graph that connect to nodes that are not in the subgraph, so \(E' \subset E\).

Additionally, for any graph, we can define a subgraph based on any old random subset of the original node set. It is completely up to us. For instance, we could define a new subgraph \(G''\) of the original graph shown in Figure 2.4, that includes the node set \(V'' = \{C, E, F\}\). That is shown in Figure 2.6. That subgraph is weird and probably not very useful, but it is a subgraph of the original graph anyways!

There is an important difference between the subgraphs shown in Figures 2.5 and 2.6 that will prove important in later discussions. In particular, note that every node in the subgraph shown in Figure 2.5 is linked to the other nodes. When a subgraph of a graph has this property, we say that it is a connected subgraph of the original graph. This is the not case for the subgraph shown in Figure 2.6 where node C is isolated from (not adjacent to) nodes E and F. So this subgraph is a disconnected subgraph of the original graph.

Just like we can define subgraphs based on the node set of a graph, we can define subgraphs based on subsets of the original edge set. For instance, we could pick the edges \(E' = \{AB, AC, AF\}\) and define a subgraph based on them, which will necessarily include node set \(V' = \{A, B, C, F\}\).

When a subgraph is defined according to a subset of nodes, which is the more common case, it is called a node induced subgraph of the original graph. When a subgraph is defined by picking a subset of edges, it is called (you guessed it) an edge induced subgraph of the original graph.

A common reason for defining subgraphs in social network analysis is when we wonder what a network would look like if were to get rid of one actor in it. Sometimes this is useful, when we want to get a sense of how important an actor is for holding the network together. So it is possible to define a subgraph by deleting a node (or an edge). This is written \(G' = G - i\), where i is the name of the node we are deleting. So this says “give me a subgraph G’ that is equal to the original graph G minus node i.”

Yet another subgraph of an undirected graph Figure 2.7: Yet another subgraph of an undirected graph

For instance, Figure 2.7, shows the subgraph that results when we delete node A from the graph in Figure 2.4: \(G' = G-A\). This is called a vertex-deleted subgraph of the original graph. If we had defined the subgraph by removing a single-edge instead (\(G' = G - ij\)), then it would be called an edge-deleted subgraph of the original graph.

As we will see later, subgraphs (as well as vertex and edge deletion) are a useful concept for discussing levels at an “in-between” levels, above the node level but “below” the whole network level (see Figure 1.9 in Chapter 1): Communities, groups, and motifs. However, subgraphs are also useful for network concepts at the node level, because there is a special type of subgraph, called the ego graph that is defined by picking a central node and the nodes that are connected to it.