What algorithm is igraph using to calculate betweenness centrality?

Development
,
1

Hi! I am using igraph (Python) to calculate betweenness centrality and was surprised by how fast it was – the betweeness centrality calculation for ~40k nodes and ~50k edges takes about 3 minutes, while it never finishes when I try to use networkx. I’m curious what algorithm igraph uses, and how is it so much faster?

2

This is likely not about the algorithm, but about Python simply being much, much slower than compiled languages such as C.

igraph uses Brandes’s algorithm, which is standard for calculating betweenness.

3

For completeness, betweenness calculation is implemented here:

@alyssa: If you like, you are welcome to submit a pull request that includes a reference to Brandes’s paper in the documentation. It’s probably good to mention it there.