1
$\begingroup$

I compared results from using the SNAP (Stanford Network Analysis Project) Python library and the iGraph R library for analyzing networks. The betweenness values for nodes seem to be rather different when using the two packages. I mostly analyzed directed networks of social interactions by using the default settings to calculate the network metrics.

Any idea where the difference might come from and which one is more accurate?

$\endgroup$
0
$\begingroup$

It is impossible to answer this question without a sample dataset, so we can do the calculation ourselves. Can you post one?

It could be that you simply made a mistake.

It could be that one of the packages has a bug. Have you tried comparing with a third one, such as networkx?

Normally, it doesn't make sense to ask which implementation is more accurate, as for betweenness they should all give the same result. However, there is one situation where accuracy does in fact come into play. If there are a very large number of shortest paths between the same vertices in a graph, there may be an overflow (or precision loss with floating point numbers). With such pathological graphs, many packages may return inaccurate, or completely wrong results. An easy example to test on is a large square lattice.

To combat this problem, igraph is able to use big integers for betweenness calculations. The tradeoff is that it will be slow. Check the manual for how to enable this (it differs between interfaces).

Here is an illustration (using igraph's Mathematica interface) of how the fast method and the bigint method gradually starts giving different results as the size of the lattice graph increases.

Table[
  With[{g = GridGraph[{k, k}]},
   {k, Max@BetweennessCentrality[g], 
    Max@IGBetweenness[g, Method -> "Fast"], 
    Max@IGBetweenness[g, Method -> "Precise"]}
   ], {k, 30, 40}] // 
 TableForm[#, 
   TableHeadings -> {None, {"size", "Mathematica", "igraph fast", 
      "igraph precise"}}] &

size    Mathematica igraph fast igraph precise
30      18980.5     18980.5     18980.5
31      21035.5     21035.5     21035.5
32      23125.8     23125.8     23125.8
33      25461.8     25461.8     25461.8
34      27834.6     27834.6     27834.6
35      30469.6     30470.3     30469.6
36      33142.8     33286.9     33142.8
37      36094.9     36602.8     36094.9
38      39086.6     40712.5     39086.6
39      42373.6     48169.2     42373.6
40      45701.7     78169.7     45701.7
$\endgroup$
  • $\begingroup$ Thanks @Szabolcs - I indeed made a mistake in the igraph function's parameters $\endgroup$ – Gabor Szalai Jul 3 '16 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.