All animals are equal, but some animals are more equal than others.
-George Orwell
What is centrality?
Centrality of a graph is based on the intuition that some vertices or edges are more central than the others. You can think of centrality as something that corresponds to "influence", "prestige" or "control". Calculating centrality is the process of assigning a real number to each vertex(or edge) to denote it"s relative importance in the graph.
There are different ways to calculate centrality index based on the use case.
- Reachability
- Shortest path based index
- Vitality
- Random processes
Reachability:
In this section we will discuss measures that evaluates the reachability of a vertex.
Degree Centrality:
Degree centrality is the simplest form of centrality. For a node v it is defined as the fraction of nodes it is connected to. In case of a directed graph we have two variants: in-degree centrality(fraction of nodes incoming edges are connected to) and out-degree centrality(fraction of nodes outgoing edges are connected to).
import networkx as nx
from networkx.algorithms.centrality import degree_centrality
G = nx.Graph()
nodes = list(range(7))
G.add_nodes_from(nodes)
G.add_edges_from([(0, 1), (0, 2),
(1, 2),(1, 3),
(2, 3), (2, 4),
(3, 5), (3,6)
])
# print(G)
print(degree_centrality(G))
"""
output:
{0: 0.33, 1: 0.5, 2: 0.66, 3: 0.66,
4: 0.16, 5: 0.16, 6: 0.16}
"""
Eccentricity(minimax):
The eccentricity of a node v is the maximum distance from v to all other nodes in G. Imagine that you want to set up a hospital in a town. Your goal is such that you should be able to serve majority of people in the vicinity. Your objective function would be to minimise the maximum response time that hospital provides to someone in case of emergency. This decision can be made by the measuring the eccentricity.
# eccentricity
import networkx as nx
from networkx.algorithms.distance_measures import eccentricity
G = nx.Graph()
nodes = list(range(20))
G.add_nodes_from(nodes)
G.add_edges_from([(0, 1), (0, 2),(0, 7), (0, 8),
(0, 9), (0, 10),(0, 11),
(1, 3),(1, 12),
(2, 3), (2, 13),
(3, 4),(3, 5), (3,6),
(12,14), (12,15), (12,16),
(13,17), (12,18), (12,19)
])
# print(G)
print(eccentricity(G))
"""
output:
{0: 3, 1: 4, 2: 4, 3: 3, 4: 4, 5: 4,
6: 4, 7: 4, 8: 4, 9: 4, 10: 4, 11: 4,
12: 5, 13: 5, 14: 6, 15: 6, 16: 6, 17: 6,
18: 6, 19: 6}
"""
Closeness centrality:
Closeness centrality of a node u is the reciprocal of the average shortest path distance to u over all n-1 reachable nodes. Imagine that you want to set up a shopping complex your objective is to draw as much crowd as possible you can do it by minimising the average distance people will need to travel to reach the complex.
# closeness
import networkx as nx
from networkx.algorithms.centrality import closeness_centrality
G = nx.Graph()
# prepare graph
nodes = list(range(12))
G.add_nodes_from(nodes)
G.add_edges_from([(0,1),(0,3), (0,6),
(1,2),
(2,5), (2,8),(2,9),
(3,4), (3,7),
(4,5),
(5,10), (5,11)
])
# calculate closeness
print(closeness_centrality(G))
"""
output:
{0: 0.42, 1: 0.46, 2: 0.5, 3: 0.42,
4: 0.46, 5: 0.5, 6: 0.30, 7: 0.30,
8: 0.34, 9: 0.34, 10: 0.34, 11: 0.34}
"""
Centroid value:
Centroid value measures the advantage of the location u compared to the other locations, that is the minimal difference of the number of customers which the salesman gains or looses if he selects u and a competitor chooses an appropriate vertex v different from u.
# centroid
import networkx as nx
G = nx.Graph()
# calculate advantage of node2 in comparison to node1
def calculate_competetive_advantage(G, node1, node2, shortest_path_lengths=None):
"""
# competetive advantage(x,y) = #nodes closer to y - #nodes closer to x
"""
if not shortest_path_lengths:
shortest_path_lengths =dict(nx.all_pairs_shortest_path_length(G))
node1_distances = shortest_path_lengths[node1]
node2_distances = shortest_path_lengths[node2]
all_nodes = [node for node in node1_distances.keys()]
node1_advantage = sum([1 for node in all_nodes
if node1_distances[node] < node2_distances[node]])
node2_advantage = sum([1 for node in all_nodes
if node1_distances[node] > node2_distances[node]])
competetive_advantage = node2_advantage - node1_advantage
return competetive_advantage
def get_centroid_values(G) -> dict:
centroid_dict = {}
shortest_path_lengths =dict(nx.all_pairs_shortest_path_length(G))
for preference_node in shortest_path_lengths.keys():
centroid_value = min([calculate_competetive_advantage(G, node, preference_node, shortest_path_lengths)
for node in shortest_path_lengths.keys() if node != 0])
centroid_dict[preference_node] = centroid_value
return centroid_dict
# prepare graph
nodes = list(range(12))
G.add_nodes_from(nodes)
G.add_edges_from([(0,1),(0,2), (0,3), (0,4),(0,5), (0,6),
(1,7), (2,7), (3,8), (4,8), (5,9), (6,9),
(7,10), (8,10), (9,10),
(10,11), (10,12)
])
c_dict = get_centroid_values(G)
print(c_dict)
"""
output:
{0: 1, 1: -3, 2: -3, 3: -3, 4: -3,
5: -3, 6: -3, 7: -5, 8: -5, 9: -5,
10: 0, 11: -11, 12: -11}
"""
In the next article we will cover:
- Shortest path based index
- Vitality
- Random processes