Maths in a minute: Who's a hub in network science?
Many real-life networks — from social media networks to transport networks — share a common feature: they contain quite a large number of hubs. These are nodes that have a comparatively large number of links to other nodes.
There's a plausible explanation for why hubs appear so frequently in networks. When a new node (e.g. a social media user or train station) enters a network (e.g. Instagram or a transport network), it is most likely to connect to existing nodes that already have a high number of links. That's because these nodes are more visible, interesting, or useful. In this way, highly connected nodes become ever more highly connected.
Hubs can be good or bad. If you want to spread information through a network, then hubs are good — they can quickly pass it on to many others. When it comes to a disease spreading through a network, then hubs are bad — remember the superspreaders from the COVID-19 pandemic.
For transport networks, hubs are good because they make journeys quicker. But they are also bad because they make the network vulnerable. If for some reason a hub fails, the entire network is thrown into disarray — just think of recent disruptions at Heathrow.
Hubs, then, are definitely important.
Not just hubs
But not all hubs are created equal. A hub that only connects to nodes which themselves link nowhere else is less hubby than a hub whose connections are themselves highly connected. An example would be a regional bus station which links up to a number of villages that don't have any other transport links. You'd want to protect this hub from disruption, but with limited resources Victoria Coach Station in London would probably take priority.
And what about a node that is not a hub, but is the only link between two large components of a network? If you were dealing with a virus spreading through a computer network, you'd definitely want to protect that node from infection, even if it doesn't have as many connections as others.
Nodes such as these may not be easy to spot, especially when your network is large or perhaps three-dimensional, so that it looks messy when drawn on paper or screen.
Luckily, mathematicians have come up with elegant ways of identifying both these kinds of nodes: k-shell centrality and betweenness centrality.
K-shell centrality
K-shell centrality measures the hunniness of a hub: to what extent the nodes it links to (directly or via other nodes) are themselves highly connected.
The number of links of a node is called the degree of the node. Hubs are nodes that have relatively high degree compared to all the others.
To define the nodes' k-shell centrality, proceed by successively peeling away nodes.
First you eliminate all nodes with degree 1 and give them a k-shell value of 1. This might have created new nodes with degree 1 (they previously had degree 2, but one of their links has now been eliminated). You eliminate these as well, also giving them a k-shell value of 1, until only nodes of degree 2 are left.
You repeat the entire process for nodes that now have degree 2, giving them a k-shell value of 2. Then repeat for nodes that now have degree 3, and so on, until no nodes are left and all the nodes in the original network have received a k-shell value.
The nodes who survived the longest have the highest k-shell value. They don't just have many links, but are connected to other nodes with many links, who are in turn connected to other nodes with many links, etc.
Betweenness centrality
The betweenness centrality of a node measures to what extent it serves as a bridge between other parts of a network. It is defined using the following process. First, for every pair of nodes in the network, find the shortest path (or paths) that link them up. That's the path that passes through the smallest number of other nodes. A large network has many pairs of nodes, so there are many paths to find, but luckily we have computers.
Now given a particular node, call it A, count the number of such shortest paths that run through it. Divide that number by the total number of shortest paths in your network. The result gives you the proportion of shortest paths that run through A. That number is the betweenness centrality of A.
A node with a high betweenness centrality plays an important role in connecting up the network. Without it, paths between many pairs of other nodes would become longer. A node with a low betweenness centrality doesn't play quite such an important role in these terms.
The three measures we've just explained — the degree of a node, its k-shell centrality and its betweenness centrality — play an important role in many contexts that involve networks. There are also other notions of centrality. See Wikipedia to find out more.
This article is part of our collaboration with JUNIPER, the Joint UNIversities Pandemic and Epidemiological Research network. JUNIPER is a collaborative network of researchers from across the UK who work at the interface between mathematical modelling, infectious disease control and public health policy. You can see more content produced with JUNIPER here.
