6 Graphs and their Subgraphs
6.1 Graphs and Subgraphs
Consider the graph shown in Figure 6.1. 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?
Well, good thing a graph is actually a pair of 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\). In mathematics, “\(\subset\)” is the symbol for subset. Thus, \(A \subset B\) is read as “set A is a subset of set B.”
For instance, let us say we are interested in just analyzing actors A, B, C, D, and E in the graph shown in Figure 6.1. They seem to be a close-knit group. 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, C, D, E\}\), where \(V' \subset V\).
The subgraph \(G'\) is shown in Figure 6.2. It looks exactly like we wanted, capturing the relations between an interconnected subgroup of actors in the original graph. Note that the edge set of the subgraph \(E'\) only includes those edges that are incident to the other nodes in the subgraph (as defined in Chapter 5) and omits those in the original graph that are incident to nodes that are not in the subgraph, so \(E' \subset E\). As we will see in a later lesson, well-connected subgroups of actors in an original graph are called cohesive subsets.
6.2 Vertex and Edge-Induced Subgraphs
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 6.1, that includes the node set \(V'' = \{D, E, G, I\}\). That is shown in Figure 6.3. That subgraph is weird (composed of two standalone connected dyads) and probably not very useful, but it is a subgraph of the original graph anyways!
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, BJ\}\) and define a subgraph based on them, as shown in Figure 6.4. This necessarily includes the node set \(V' = \{A, B, C, J\}\).
When a subgraph is defined by selecting a subset of nodes to retain (the common case), it is called a vertex-induced subgraph of the original graph, as in Figure 6.2. When a subgraph is defined by picking a subset of edges from the original graph to keep, it is called (you guessed it) an edge-induced subgraph of the original graph.
6.3 Creating Subgraphs by Deleting Nodes and Edges
Another way to think about creating subgraphs is by deleting elements from the original graph. This approach is common in social network analysis when we want to see what a network would look like if certain actors or relationships were removed, which can help reveal how important they are for holding the network together.
6.3.1 Vertex-Deleted Subgraphs
It is possible to define a subgraph by deleting nodes. This is written as \(G' = G - \{a, b, c\}\), where \(\{a, b, c\}\) is the set of nodes being deleted. When you delete nodes, a critical rule applies: all edges incident to those nodes are automatically removed as well.
For example, starting with the graph in Figure 6.1, if we delete the node set \(\{F, G, H, I, J\}\), the resulting subgraph is identical to the one shown in Figure 6.2. This shows that a vertex-deleted subgraph can be equivalent to a vertex-induced subgraph. The action of deleting \(\{F, G, H, I, J\}\) induces a subgraph on the remaining nodes \(\{A, B, C, D, E\}\).
Two special cases of vertex deletion are: - The null graph, which results from removing all nodes from the original graph. - The singleton graph (or trivial graph), which results from removing all nodes except for one.
6.3.2 Edge-Deleted Subgraphs
Just as we can delete nodes, we can also create subgraphs by removing edges. This is written as \(G' = G - \{e_1, e_2, ...\}\), where \(\{e_1, e_2, ...\}\) is the set of edges being deleted. For instance, the edge-deleted subgraph in Figure 6.5 results from removing the six edges \(\{AB, AE, AC, CI, CE, GJ\}\) from the graph in Figure 6.1.
When you delete edges, the nodes that were connected by those edges remain in the graph. A subgraph created by removing only edges while leaving all original nodes intact is called a spanning subgraph.
A special case of edge deletion is the empty graph, which results from removing all edges from the original graph, leaving only the set of isolated nodes.
As we will see later, subgraphs (as well as vertex and edge deletion) are a useful concept for discussing levels at an “in-between” level, above the node level but “below” the whole network level: subgroups. 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, along with the edges connecting the nodes surrounding ego.