Closeness Centrality

Problem

Compute the closeness centrality of every node in an undirected unweighted graph.

For each node, run BFS and let R be the number of reachable nodes excluding itself and S the sum of their distances. The centrality is R / S, or 0.0 when no other node is reachable.

Hint

A BFS from each node gives both the count and the sum of distances.

Test cases

case 1

in: [3,[[0,1],[1,2]]]

expected: [0.6666666666666666,1,0.6666666666666666]

case 2

in: [4,[[0,1],[0,2],[0,3]]]

expected: [1,0.6,0.6,0.6]

case 3

in: [3,[[0,1]]]

expected: [1,1,0]

case 4

in: [1,[]]

expected: [0]

Starter codePython

def closeness_centrality(n, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor