1. Betweenness centrality
Great work! I hope you had fun figuring out those exercises! Let's now revisit our notions of what it means to be an "important node", but this time leveraging what we know about paths. We're now going to learn about betweenness centrality, but before we talk about that, we need to extend our knowledge with one key concept -
2. All shortest paths
that of "all shortest paths". In the previous section, we learned about how to find the shortest path between any pair of nodes, using the breadth-first search algorithm. Imagine now we used the BFS to find every shortest path between every pair of nodes. What we would get back is the set of "all shortest paths" in a graph. In other words, "all shortest paths" are the set of paths in a graph, such that each path is the shortest path between a given pair of nodes, done for all pairs of nodes. Now we can introduce
3. Betweenness centrality
the definition of betweenness centrality. Betweenness centrality is defined as the number of shortest paths in a graph that pass through a node divided by the number of shortest paths that exist between every pair of nodes in a graph. This metric captures a different view of importance - in essence, it captures bottleneck nodes in a graph, rather than highly connected nodes; this will become much clearer as we go on. Where might betweenness centrality useful? One example would be individuals that bridge between two communities, say, an individual bridging liberal-leaning and conservative-leaning Twitter users. Alternatively, consider the internet, where there are crucial links that bridge two networks of computers. If we removed those crucial nodes in the internet, then information will not flow (or at least not as easily) between subnetworks.
4. Examples
Let's look at the Singapore subway system to make this more concrete. Take a look at two sets of stations that I have highlighted. In the south, there's a cluster of stations in the central business district that serve as connectors between different lines, but there's also this other station called Jurong East, which is only connected to three other stations, but serves as a major transit connector point between the red and the green lines.
5. Example
Let's have a look at the code for computing betweenness centrality. Let's say we have a graph G that is a barbell graph. We can create this graph
6. Betweenness centrality
by using one of NetworkX's graph generators, nx-dot-barbell_graph, with m1 being the number of nodes in the barbell ends, and m2 being the number of nodes in the barbell bridge. To get the betweenness centrality, we can call on NetworkX's betweenness_centrality function, which takes in a graph object G as an argument. What that function returns is a dictionary, just like the degree_centrality function, in which the nodes are the keys and their betweenness centrality scores are the values.
7. Betweenness centrality
You might notice that some of the nodes here have betweenness centrality scores of "0". That's because they are located at the ends of the barbell graph, and the nodes within each end are fully connected with one another. Therefore, with the exception of the bridge node and the two other nodes it is connected to, there's no shortest path that has to run through any of those nodes to get to other nodes.
8. Let's practice!
Alrighty! Let's move on to the exercises. Not only will you get a chance to practice using the betweenness_centrality function, you will also be given two deep dives into a Twitter network that should give you more practice with the content from this chapter as well.