Identifying bottlenecks in networks
A large network, such as an infrastructure network or a social network, may contain highly connected regions that are linked to each other by bottlenecks. In order to understand the structure of the network, it is helpful to be able to identify where the bottlenecks are. The points marked in red in the picture above, which shows the UK road network between Birmingham and Nottingham, are examples of bottlenecks in the circular pink region. This means that if there is congestion at both red points in the network, it becomes impossible to cross from one side of the pink disc to the other without first leaving the area.
The same principles can be applied to any graph. A graph is a set of vertices, some of which are joined in pairs by edges. The 24 vertices of the graph above correspond to the pairs (a, b), where a is an integer satisfying 1 ≤ a ≤ 12 and b is 1 or 2, and there is an edge between (a, b) and (c, d) if a and c would be adjacent on a clock face (for example, if a=12 and c=1). The pink circular region covers the six vertices between 8 and 10 o’clock of the picture. The two red vertices at 9 o’clock form a bottleneck in this case, because it is not possible to move from one of the 8 o’clock vertices to one of the 10 o’clock vertices without either leaving the pink region or passing through one of the red vertices.
One way to study the structure of a graph is to study its highly interconnected regions, and these can be understood in terms of complete graphs. The complete graph Kn has n vertices, and all possible pairs of vertices are joined to each other. For example, the graphs K4, K5, and K6 are shown above.
In the “clock face” graph from earlier, the four vertices at 8 and 9 o’clock are all connected to each other, so they form a copy of a K4. The four vertices at 9 and 10 o’clock form another copy of a K4, and the two copies of K4 overlap in the two vertices at 9 o’clock. This gives rise to another graph, called the decomposition graph, shown above in blue. Each blue dot corresponds to a copy of K4, and two blue dots are joined if the corresponding copies of K4 overlap. In this case, the decomposition graph has 12 vertices joined in a cycle (a dodecagon in this case) and the edges in the blue graph correspond to darker grey areas and also to the bottlenecks in the original graph. Another example of a decomposition graph, shown below, is based on the structure of a caffeine molecule.
I found out about these constructions from the recent paper Canonical graph decompositions and local separations: From infinite coverings to a finite combinatorial theory by Johannes Carmesin, Raphael W. Jacobs, Paul Knappe, and Jan Kurkofka. The authors are interested in the problem of representing the connectivity structure of the highly connected regions of a graph at various resolutions, in such a way that the representation is canonical and can be computed relatively easily.
The basic idea is to unfold the graph as much as possible without disturbing the most tightly interconnected regions, and this is achieved by modifying the idea of a universal covering space in topology. The picture above shows an annulus, which is a two-dimensional ring shape, and its universal cover, which is an infinite helix-shaped strip. Any small patch of the helix is a copy of the small patch in the annulus, but any closed loop in the helix can be continuously shrunk to a point, which is not the case for the annulus. (In other words, the helix is simply connected, and the annulus is not.)
The paper explains how to do something similar for a graph in a canonical way, as in the example above. “Canonical” means that the unfolding of the graph can be carried out in a standard way that does not depend on arbitrary choices. However, the aforementioned procedure has drawbacks from a computational point of view: the construction is topological, and it involves infinite structures. The main result of the paper is to explain how to achieve essentially the same construction using only finite combinatorial methods. The paper is 59 pages long and the details are very technical, but the authors largely succeed in solving the problem of representing the bottlenecks in a graph and providing an algorithm to do so.
Picture credits and relevant links
The pictures of the complete graphs are by Koko90 and appear on Wikipedia.
The picture of the covering space is by Johannes Spielmann and appears on Wikipedia.
The diagram of the caffeine molecule appears on Wikipedia and is thought to be by Icey.
The other pictures come from the paper by Johannes Carmesin, Raphael W. Jacobs, Paul Knappe, and Jan Kurkofka.
Substack management by Buzz & Hum.