Degree-based centrality algorithms identify important nodes in terms of their connections. But what happens to our graph if node 5 disappears? We end up with three disconnected components:
- Nodes 1, 2, 3, and 4
- Nodes 6, 7, and 8
- Nodes 9, 10, and 11
This new layout is illustrated in the following diagram:
As you can see, communication from one component to another will be completely impossible. Consider, for instance, nodes 1 and 10. There is no possible path between them anymore. In a telecommunication or road network, this situation can have serious consequences, from huge traffic jams to the impossibility of calling emergency services. It needs to be avoided at any cost, meaning that nodes such as node 5 in our test graph need to be identified in order to be better protected. For this reason, node 5 is called a critical (or bridging) node.
Fortunately, we have centrality algorithms to measure this kind of importance. We will group them together under...
