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?