12 Graph Connectivity
12.1 Connected and Disconnected Graphs
Look at the graph shown in Figure 11.1 again. Are there any disconnected pairs of nodes in the graph? The answer is no. If you pick any pair of nodes, they are either directly connected or indirectly connected to one another via a path of some length. So, how can we disconnect two nodes in a simple undirected graph? The answer is that there has to be some kind of “gap” splitting the graph into two or more pieces, so that some set of nodes can no longer reach some of the other ones.
For instance, if you compare the undirected graphs Figure 12.1 (a) and Figure 12.1 (b) you can appreciate the difference between a connected graph and a disconnected graph. The difference between Figure 12.1 (a) and Figure 12.1 (b) is that the Figure 12.1 (b) graph is a subgraph of the Figure 12.1 (a) graph, in which the \(DF\) edge has been removed (an edge-deleted subgraph according to what we discussed in Section 6.9): \(G(b) = G(a) - DF\).
When we remove the \(DF\) edge the resulting graph \(G(b)\) is now disconnected. There is no way we can trace a path connecting any of the vertices in the \(\{F, G, H, I\}\) subset with any of the vertices in the \(\{A, B, C, D, E\}\) subset. This is different from Figure 12.1 (a), where we can trace a finite path between any two vertices, even if it is very long.
Thus, we can come up with a formal definition of graph connectivity:
A graph is connected if there exists a (finite) path between each pair of nodes.
A graph is disconnected if there does not exist a path connecting every pair of nodes.
Note that a graph is disconnected even if there is just one pair of nodes that cannot reach each other. In Figure 12.1 (b), for instance, the graph is disconnected because there is no path connecting any node in the \(\{F, G, H, I\}\) subset to any node in the \(\{A, B, C, D, E\}\) subset.
12.2 Components and the Giant Component
When a graph goes from connected (like Figure 12.1 (a)) to disconnected (like Figure 12.1 (b)), it is split into a number of subgraphs that are themselves connected. The pairs of nodes inside the subgraph can reach one another, but they can’t reach the nodes outside the subgraph.
For instance, in Figure 12.1 (b), the set of nodes \(\{A, B, C, D, E\}\) forms a connected subgraph of the larger disconnected graph. A connected subgraph within a larger disconnected graph is called a component of the larger graph. Disconnected graphs, by definition, have multiple components, with the smallest number of components being two. In Figure 12.1 (b), there are two components, one formed by the connected subgraph with node set \(\{A, B, C, D, E\}\), and the other formed by the connected subgraph with node set \(\{F, G, H, I\}\).
As we noted, it is possible to split a graph into multiple components, not just two. For instance, take a look at the unlabeled graph (see Chapter 6 for the distinction between unlabeled and labeled graphs) in Figure 12.2. If we were to generate a subgraph from Figure 12.2 by deleting the two red edges and the one purple edge, we would end up with the graph shown in Figure 12.3 (a). This graph is disconnected, and it features three separate components (connected subgraphs).
If we were to delete just the red edges from Figure 12.2 and keep the purple edge, we would end up with the graph shown in Figure 12.3 (b). Like Figure 12.3 (a), Figure 12.3 (b) is also disconnected, but it is split into two components, not three.
Note that one of the connected components in the graphs shown in Figure 12.3 (b), Figure 12.3 (c), and Figure 12.3 (d) is way larger than the other one. For instance, the larger connected component of the graph in Figure 12.3 (b) is of order 10, but the smaller component is only of order 4.
When a disconnected graph is split into multiple components, the component containing the largest number of nodes (the largest connected subgraph) is called the graph’s giant component. In Figure 12.3 (c) and Figure 12.3 (d), the giant component is the one with 9 nodes, while the smaller component has 5 nodes.
12.3 Edge Connectivity
We went from the connected graph shown in Figure 12.2 to the disconnected graphs in Figure 12.3 by removing specific edges, such as the red and purple ones in Figure 12.2.
These edges are clearly more important than the other edges colored blue in the graph, because they are responsible for keeping the whole graph together as a connected structure. Obviously, this property of edges has a name in graph theory.
In a graph, an edge cutset is any set of edges whose removal results in a graph going from being connected to disconnected.
For instance, in Figure 12.2 the set of two red edges is a cutset of the graph \(G\) since deleting these edges would disconnect the graph as shown in Figure 12.3 (b). In the same way, we can see that a subset that combines any one of the red edges with the purple edge is also a cutset of the graph in Figure 12.2, because removing any combination of these two links results in a disconnected graph, as shown in Figure 12.3 (c) and Figure 12.3 (d).
Generally, choosing a larger edge cutset results in more disconnected components. For instance, selecting both the red edges and the purple edge—a cutset of cardinality three—as the cutset results in a graph with three disconnected components, as in Figure 12.3 (a).
A minimum edge cutset of a graph is any edge cutset that also happens to be of the smallest size (in terms of cardinality) among all the possible cutsets. The cardinality of the minimum edge cutset in the graph is called the graph’s edge connectivity, and it is written \(\lambda(G)\).
The graph in Figure 12.2 has edge-connectivity \(\lambda(G) = 2\) because we need to remove at least two edges to disconnect it. As we saw earlier, these could be either the set of the two red edges or any combination that includes one of the red edges with the purple one.
When a graph has edge-connectivity larger than one, like Figure 12.2, it means that we could remove any one edge and the graph would still be connected.
For instance, looking at Figure 12.2, if we were to remove just the purple edge, the graph would still be connected and look like Figure 12.3 (e), which is a connected graph.
The same would happen if we removed just one of the red edges from Figure 12.2. If we were to do that, we would end up with the graph shown in Figure 12.3 (f), which is still connected.
12.3.1 Bridges
As you might imagine, the smallest edge connectivity a connected graph can have is \(\lambda(G) = 1\). A graph with edge-connectivity 1 has a special edge called a bridge. This is the single edge whose removal disconnects a graph with edge-connectivity equal to 1.
For instance, in Figure 12.1 (a), the \(DF\) edge is a bridge. When a graph is like the one shown in Figure 12.1 (a) and has a bridge (such as \(DF\)), that edge has two interesting properties (Buckley and Harary 1990, 17).
- First, if an edge is a bridge in graph \(G\), then that edge does not lie on any cycle of \(G\) (as defined in Chapter 11). That means that \(DF\) in Figure 12.1 (a) does not lie on any cycle of \(G\).
- Second, if an edge is a bridge, then there is at least one pair of nodes i and j such that the bridge is an edge on every path linking i and j. In Figure 12.1 (a), clearly condition (2) is the case for every node in the subset \(\{F, G, H, I\}\) relative to nodes in the subset \(\{A, B, C, D, E\}\). Every path linking nodes in the first subset to nodes in the second subset has to include the bridge \(DF\).
12.4 Node Connectivity
As you recall from Section 6.9, we can create subgraphs by removing either edges or nodes. In the same way, we can make a graph disconnected by removing either edges or nodes. In Section 12.3, we considered the case of removing edges to disconnect a graph. Here, we consider the case of removing nodes.
In a graph, a node cutset is any set of nodes whose removal results in a graph going from being connected to disconnected.
Figure 12.4 (a) shows a graph that is the same as the one in Figure 12.2, except that the nodes are labeled. In that graph, the set of nodes \(\{A, D\}\) is a cutset of the graph \(G\) since deleting these nodes disconnects the graph, as shown by the resulting node-deleted subgraph shown in Figure 12.4 (b). This graph is now disconnected, featuring a nine-node giant component and a smaller three-node component containing nodes \(\{B, C, E\}\)
In the same way, we can see that the set of nodes \(\{G, H\}\) is also a cutset of the graph, because removing these nodes would separate \(\{F, I, J\}\) from the rest of their friends, creating a graph with two separate components, as shown in Figure 12.4 (c).
Interestingly, the set formed by the single node \(K\) is also a cutset of the graph. As shown in Figure 12.4 (d), removing this one node disconnects the graph, separating \(\{L, M, N\}\) from the rest.
A minimum node cutset of a graph is any node cutset that also happens to be of the smallest size (in terms of cardinality). The cardinality of the minimum node cutset in the graph is called the graph’s node connectivity, and it is written \(\kappa(G)\).
The graph in Figure 12.4 (a) has node-connectivity (\(\kappa(G) = 1\)) because, as we have seen, all we need to do is remove \(K\) to disconnect it.
12.4.1 Articulation (Cut)Nodes
If a graph has a single node whose removal disconnects the graph, then that node is called the articulation node of the graph (also called a cutnode). The articulation node is the node equivalent of what a bridge is for edges. A single actor upon whom the entire connectivity of the network depends.
If a graph \(G\) has an articulation node, then by definition \(\kappa(G) = 1\). Any graph \(G\) with \(\kappa(G) > 1\), therefore, lacks an articulation node. It follows from this that if a graph has node-connectivity larger than one (\(\kappa(G) > 1\)), we could remove any one node and the graph would still be connected.
Articulation nodes have another interesting property related to indirect connectivity. If a graph has an articulation node u, there is at least one other node in the graph v such that u stands in the middle of every path (as an inner node) connecting v to the rest of the other nodes in the graph.
Finally, if a node in a graph has degree \(k = 1\) (that is, the node is an end-node), then it cannot be an articulation node. We can always remove an end-node from a connected graph, and the graph will stay connected.
The larger the graph connectivity (\(\kappa(G)\)) of a graph, the larger is the structural cohesion of the underlying social network represented by the graph (White and Harary 2001).
12.4.2 Graph Connectivity and Minimum Degree
An interesting mathematical relationship obtains between three graph properties: Minimum Degree (covered in Section 9.5) and the edge and node connectivities.
It goes as follows: In every graph the node connectivity is always smaller or equal to the edge connectivity, which is always smaller or equal to the minimum degree (Harary 1969, 43).
In mathese, for any graph \(G\):
\[ \kappa(G) \leq \lambda(G) \leq min(k) \tag{12.1}\]
Neat! These can be interpreted as three criteria that indicate how well-connected a whole graph, a subgraph, or a component of a larger graph is. Having a high minimum degree is the weakest, followed by high edge-connectivity, with high node-connectivity being the strongest criterion.
12.5 Local Bridges
In a classic paper on “The Strength of Weak Ties,” Mark Granovetter (1973) developed the concept of a local bridge. Recall from section Section 12.3.1 that a bridge is an edge that, if removed, would completely disconnect the graph.
Another way of thinking about this is that a bridge is an edge that, if removed, would increase the length of the shortest paths between two sets of nodes from a particular number to infinity since, in a disconnected graph, the length of the path between nodes that cannot reach one another is indeed infinity! (\(\infty\)).
There is another way to think about bridges in the context of shortest paths: ask what happens to the indirect connectivity between particular pairs of nodes in the graph when a specific edge is removed. Clearly, every time we remove an edge, this affects the indirect connectivity between a pair of nodes, for instance, by increasing their geodesic distance (the length of the shortest path linking them).
So even if a graph remains connected after removing an edge (because its edge-connectivity is greater than 1), removing that edge can affect how close two nodes in the network are. That is what the concept of a local bridge is intended to capture.
Formally, a local bridge is an edge that, if removed from the graph, would increase the length of the shortest path between a particular pair of nodes to a number that is higher than their current one but less than infinity. This number is called the degree of the local bridge in question. Because a local bridge is always defined with respect to a particular pair of nodes, it is a triplet, involving two nodes i and j and one edge uv.
For instance, in Figure 12.5 (a), consider the nodes \(H\) and \(K\). The edge \(HK\) (pictured in purple) is a local bridge of degree 4 for this pair. The reason for that is that, as shown in Figure 12.5 (b), when the edge \(HK\) is removed from the graph, the shortest path between nodes \(H\) and \(K\) increases from \(l_{HK} =1\) (\(H\) and \(K\) are adjacent in Figure 12.5 (a)) to \(l_{HK} = 4\), as given by the path \(H-G-A-D-K\) (pictured in red).
Note that from the perspective of nodes \(D\) and \(H\), the purple \(HK\) edge is a local bridge of degree three, because \(l_{DH} = 2\) in Figure 12.5 (a) and \(l_{DH} = 3\) when the edge \(HK\) is removed from the graph in Figure 12.5 (b).
12.6 Connectivity in Directed Graphs
Connectivity in directed graphs (digraphs) is more complex than in undirected graphs. Because edges have directionality, the fact that node \(u\) can reach node \(v\) does not guarantee that node \(v\) can reach node \(u\) (as we saw in Section 11.8).
To account for this asymmetry, graph theory distinguishes between three different hierarchical levels of connectivity for directed graphs: weak connectivity, unilateral connectivity, and strong connectivity.
12.6.1 Pairwise Connectivity States
To understand the connectivity of a whole directed graph, we must first look at the connectivity between individual pairs of nodes. For any pair of nodes \(u\) and \(v\) in a directed network, they can exist in one of several states:
- Pairwise Weakly Connected: Node \(u\) and \(v\) are connected by at least one semipath (connected if we ignore the arrow directions). They are part of the same general network, but there is no directed path starting from either node that can reach the other.
- Pairwise Unilaterally Connected: A directed path exists from \(u \rightarrow v\) OR from \(v \rightarrow u\). Information or influence can flow from one person to the other, but it is a one-way street; there is no mutual exchange.
- Pairwise Strongly Connected: A directed path exists from \(u \rightarrow v\) AND from \(v \rightarrow u\). Both nodes can mutually reach each other (mutual reachability), although the paths in each direction may use completely different intermediate nodes or channels.
- Pairwise Recursively Connected: A directed path exists from \(u \rightarrow v\) and \(v \rightarrow u\), AND the directed path in both directions shares the exact same set of intermediate nodes. The relationship can be traversed back-and-forth along the same closed, mutually symmetric cycle.
12.6.2 Whole Graph Connectivity
A whole graph’s overall level of connectivity is defined by the weakest pairwise connectivity state present in the network. Global graph connectivity is built on top of individual node-to-node pairwise states. If even a single pair drops to a lower state, the entire graph’s connectivity level drops!
12.6.2.1 1. Strongly Connected Graphs
A directed graph is strongly connected if every single pair of nodes in the graph is pairwise strongly connected. This means that there is a directed path from every node to every other node in the graph (complete mutual reachability).
In Figure 12.6, notice how the graph consists of a complete spanning cycle (\(1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 1\)) plus some additional chord arcs. Because of the continuous cycle, any node can reach any other node, ensuring complete mutual reachability.
12.6.2.2 2. Unilaterally Connected Graphs
A directed graph is unilaterally connected if for every pair of nodes, there is at least one directed path connecting them (every pair is at least pairwise unilaterally connected), but the graph fails to be strongly connected.
In Figure 12.7, the edges flow strictly forward (\(1 \rightarrow 2 \rightarrow 3 \dots \rightarrow 7\)). The feedback edge \(7 \rightarrow 1\) has been removed. Here, node 1 can reach node 7, but node 7 cannot reach node 1 (no mutual reachability). However, for every single pair you can pick, at least one directed pathway exists between them.
12.6.2.3 3. Weakly Connected Graphs
A directed graph is weakly connected if the graph is connected when we completely ignore the direction of the arrows (replacing all directed arcs with simple undirected edges). This means at least one pair of nodes in the graph is only pairwise weakly connected (they can’t reach each other via directed paths, but they are part of the same structure).
In Figure 12.8, there is no directed path from node 5 to node 7, nor is there a directed path from node 7 to node 5. Thus, \(\{5, 7\}\) is a mutually unreachable pair, violating unilateral connectivity. However, if we ignored the arrows, the graph is a single connected piece, making it weakly connected.
12.6.3 Directed Components
Just as undirected graphs are divided into connected components, directed graphs can be decomposed into:
- Weakly Connected Components (WCCs): Subgraphs that are connected when we ignore edge direction.
- Strongly Connected Components (SCCs): Subgraphs within which every node is mutually reachable from every other node.
Decomposing Figure 10.1 yields: * One Weakly Connected Component: All nodes \(\{A, B, C, D, E, F, G\}\) are part of a single, unified WCC. * Four Strongly Connected Components: 1. The close-knit core of mutually reachable nodes: \(\{A, B, D, F\}\). Within this subgraph, you can trace a directed path from any node to any other node (e.g., \(A \rightarrow F \rightarrow A\), and \(B \leftrightarrow D\)). 2. The singleton receiver component: \(\{C\}\). 3. The singleton transmitter component: \(\{E\}\). 4. The singleton transmitter component: \(\{G\}\).
Decomposing networks into strongly and weakly connected components has powerful applications. For example, in an information flow or gossip network, a strongly connected component represents a “rumor mill” where information can diffuse rapidly and completely to all members. On the other hand, nodes outside the SCC (like receivers or transmitters) either act as pure information sinks or pure information sources.