Betweenness Centrality

Hi folks, I need to compute the betweenness centrality for all nodes in a graph.

Here’s my Python code using NetworkX for reference:

import networkx as nx
from networkx.algorithms.centrality import betweenness_centrality

if __name__ == "__main__":
    florence = nx.Graph()
    florence.add_edge("castellan", "peruzzi")
    florence.add_edge("peruzzi", "bischeri")
    florence.add_edge("bischeri", "guadagni")
    florence.add_edge("guadagni", "lambertes")
    florence.add_edge("guadagni", "albizzi")
    florence.add_edge("albizzi", "ginori")
    florence.add_edge("albizzi", "medici")
    florence.add_edge("medici", "acciaiuol")
    florence.add_edge("medici", "salviati")
    florence.add_edge("salviati", "pazzi")
    florence.add_edge("medici", "barbadori")
    florence.add_edge("barbadori", "castellan")
    florence.add_edge("castellan", "strozzi")
    florence.add_edge("strozzi", "peruzzi")
    florence.add_edge("strozzi", "bischeri")
    florence.add_edge("strozzi", "ridolfi")
    florence.add_edge("ridolfi", "tornabuon")
    florence.add_edge("tornabuon", "guadagni")
    florence.add_edge("tornabuon", "medici")
    florence.add_edge("ridolfi", "medici")
    florence.add_node("pucci")
    centrality_tuples = sorted(betweenness_centrality(florence).items(),
                               key=lambda kv: kv[1], reverse=True)
    for family, centrality in centrality_tuples:
        print(f"{family:12}: {centrality:.3f}")

The output:

medici      : 0.452
guadagni    : 0.221
albizzi     : 0.184
salviati    : 0.124
ridolfi     : 0.098
bischeri    : 0.090
strozzi     : 0.089
barbadori   : 0.081
tornabuon   : 0.079
castellan   : 0.048
peruzzi     : 0.019
lambertes   : 0.000
ginori      : 0.000
acciaiuol   : 0.000
pazzi       : 0.000
pucci       : 0.000

These numbers are for some reason completely different from the slide of the networks course where I got this data:

So maybe I made a mistake somewhere… Can’t find it though.

For those who are interested, the theory is that the Medici family rose to power because they strategically married families in such a way that those families would have to go through the Medici family to resolve disputes and enter trade deals. The Medici family appears on the shortest paths between two other families most often.

Anyway, is computing betweenness centrality possible with WOQL, or should I stick to NetworkX?

EDIT: In the first version of this post, I asked for an algorithm using breadth-first trees. This turned out to be the wrong choice for the problem because breadth-first search commits to one shortest path between two nodes when we want to be able to explore all shortest paths. In the second version, I was using breadth-first and depth-first tree generation to compute betweenness centrality myself before realizing that there was already a NetworkX library function that could do it in a single line.