Path-based centrality metrics

As we discussed in the first section of this chapter (Defining importance), the neighborhood approach is not the only way to measure importance. Another approach is to use a path within the graph. In this section, we will discover two new centrality metrics: closeness and betweenness centrality.

Closeness centrality

Closeness centrality measures how close a node is, on average, to all the other nodes in the graph. It can be seen as centrality from a geometrical point of view.

Normalization

The corresponding formula is as follows:

C_n = 1 / ∑ d(n, m)

Here, m denotes all the nodes in the graph that are different from n, and d(n, m) is the distance of the shortest path between n and m.

A node that is, on average, closer to all other nodes will have a low ∑ d(n, m), resulting in high centrality.

Closeness centrality prevents us from comparing values across graphs with different numbers of nodes since graphs with more nodes will have more terms in...