Betweenness centrality in NetworkX: logical error

Question

I calculate betweenness centrality for the Florentine Families Graph by:

import networkx as nx

# build up a graph
G = nx.florentine_families_graph()
bw_centrality = nx.betweenness_centrality(G, normalized=False)

Excerpt from the description of betweenness_centrality(...) in networkx,

Betweenness centrality of a node v is the sum of the fraction of all-pairs shortest paths that pass through v:

Therefore, betweenness centrality should be less than 1. However, I got the result: (the betweenness centrality of the red node, 'Medici', is 47.5)

The way I calculate the betweenness centrality is as follows,

node_and_times = dict.fromkeys(G.nodes(), 0) # a dict of node : the number of shortest path passing through node
sum_paths = 0

for s, t in itertools.product(G.nodes(), repeat=2): # all pair of nodes <s, t>
    paths = nx.all_shortest_paths(G, s, t) # generator of lists
    for path in paths:
        sum_paths += 1

        # stats nodes passing through shortest path
        for node in path[1:-1]: # intermediate nodes
            node_and_times[node] += 1

bw_centrality = {k : v*1.0/sum_paths for k, v in node_and_times.items()}

and I got the following result,

Am I right?

As mentioned by the answerers, removing normalized=False got the following result which is not consistent with my calculation.

'As mentioned by the answerers, removing normalized=False got the following result which is not consistent with my calculation.' - thats because Your calculations are wrong, You are not calculating betweenness centrality. — Tony Babarino
@TonyBabarino you are right. I misunderstand the definition of betweenness centrality as the ratio of the number of shortest paths passing through v to the total number of shortest paths. — SparkAndShine
Yep, exactly. I tried to explain how to calculate it in my answer, I hope You can understand my explanation. Cheers! — Tony Babarino

Tony Babarino Tony Babarino · Accepted Answer · 2016-03-25T11:31:21

The definition of betweenness centrality doesn't imply that it's value is less than 1. The sum of fractions doesn't have to be less than 1.

Consider following example:

The shortest paths and the nodes that they go through are:

A -> B: None
A -> C: B
A -> D: B, C
A -> E: B, C, D
B -> C: None
B -> D: C
B -> E: C, D
C -> D: None
C -> E: D
D -> E: None

So calculating betweenness centrality for 'B' from formula:

we get:

shortest paths A -> C that go through B = 1
shortest paths A -> C = 1
shortest paths A -> D that go through B = 1
shortest paths A -> D = 1
shortest paths A -> E that go through B = 1
shortest paths A -> E = 1
1/1 + 1/1 + 1/1 = 3

Therefore betweenness centrality for all nodes:

A: 0
B: 3
C: 4
D: 3
E: 0

And calculated in Python:

import networkx as nx

# build up a graph
G = nx.Graph()
G.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
G.add_edges_from([('A', 'B'), ('B','C'), ('C', 'D'), ('D', 'E')])
bw_centrality = nx.betweenness_centrality(G, normalized=False)

print bw_centrality
# returns {'A': 0.0, 'C': 4.0, 'B': 3.0, 'E': 0.0, 'D': 3.0}

So, If You want to get the values less than 1, You have to use normalized=True (wiki about normalization).

Example taken from here.

Betweenness centrality in NetworkX: logical error

2 Answers