The Closeness Centrality
Learn about the closeness centrality, a measure that finds nodes that are closer to all nodes in the network.
Let’s learn about a centrality measure that takes into account how close a node is to every other node in the network. For that, let’s learn about shortest path distances in a graph.
Shortest path distances
The concept of distance in a network usually talks about how many edges we need to walk on to go from one node to another. We call a path the sequence of edges we walk to traverse that distance.
So, for example, we can highlight a path between two nodes in the following graph:
Of course, if the edges are directed, then the path we can use is restricted to the direction the edges point at. If the edges are weighted, we sum the weight of the edges when calculating the distance.
This gives us the concept of the shortest path distance. There can be a lot of paths to go from one node to the other in a graph. Each path can have a different distance or cost. In this case, we’re interested in finding the path that has the lowest distance between these two nodes. This is the shortest path.
We can calculate the shortest path distance from every node to every other node in a network using the NetworkX nx.shortest_path_length() method.
import networkx as nx# Defining a random graphG = nx.random_geometric_graph(5, 0.7, seed=42)# Calculating the shortest path distanceprint('Shortest Path Length: ', dict(nx.shortest_path_length(G)))
Notice how the output of the method is a dictionary where, for each node, we have the shortest path distance to all other nodes in the graph, including itself.
Note: NetworkX has several implementations we can choose in its calculation for the shortest path length. Some options include the Dijkstra, Bellman-Ford and Floyd-Warshall algorithms.
It’s ...