Bad news :-(

Mathematica also gives incorrect results for the betweenness centrality of large graphs, most likely due to integer overflow. (Update: Fixed in recent versions.) How do I know that Mathematica is wrong?

Well, here it is:

Let's make a grid graph, which has lots and lots of shortest paths of the same length, and is thus a good stress test.

In[36]:= g = GridGraph[{30, 30}];

In[37]:= Max@BetweennessCentrality[g] - Max@IGBetweenness[g, "UseBigInt" -> False]
Out[37]= 0.

igraph and Mathematica agree perfectly. Good. Now let's make a bigger grid graph.

In[33]:= g = GridGraph[{40, 40}];

In[34]:= Max@BetweennessCentrality[g] - Max@IGBetweenness[g, "UseBigInt" -> False]
Out[34]= -46909.

That's a huge difference. So someone is wrong. But who? igraph is documented to have integer overflows with the "UseBigInt" -> False option (although it's very fast with it). Let's use bigints to avoid the overflow.

In[40]:= Max@BetweennessCentrality[g] - Max@IGBetweenness[g, "UseBigInt" -> True]
Out[40]= -14441.

They still disagree. So let's try a third package, networkx:

In [16]: g=nx.grid_2d_graph(40,40);

In [17]: bc=nx.betweenness_centrality(g, normalized=False);

In [18]: max(bc.values())
Out[18]: 45701.730220604535

Comparing Mathematica and igraph:

In[42]:= {Max@BetweennessCentrality[g], Max@IGBetweenness[g, "UseBigInt" -> True]}
Out[42]= {31260.7, 45701.7}

So networkx and igraph agree. Mathematica must be wrong.

Sean, could you please bring this to the attention of the developers?