The Search Guy
The Search Guy"s Blog

The Search Guy"s Blog

Centrality Algorithms- A bird"s eye view - Part 1

Photo by Omar Flores on Unsplash

Centrality Algorithms- A bird"s eye view - Part 1

The Search Guy's photo
The Search Guy
·Jan 9, 2022·

4 min read

Table of contents

  • What is centrality?

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).

Figure3_0.jpeg

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.

Figure3_1.jpeg

# 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.

Figure3_2.jpeg

# 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.

Figure3_3.jpeg

# 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

References:

  1. Jupyter notebook
  2. Documentation: Networkx centerality implementations
  3. Book: Network Analysis- Methodological foundations
 
Share this