igraph betweenness depends on order of edges

Question

I have a question whether order of edges in graph should matter or not?

It seems that betweenness function produces slightly different results for different orderings of input file.

input file : http://preview.tinyurl.com/p9vlxnc

#1st run, with unordered edges
edges <- read.csv("example.csv", col.names=c("src", "dest"), colClasses = "character")

social.graph <- graph.edgelist(as.matrix(edges), directed=T)
social.graph <- graph.adjacency(get.adjacency(social.graph), weighted=TRUE)

E(social.graph)$weight <- 1 / E(social.graph)$weight

set.seed(1)
between1 <- betweenness(social.graph)

#2nd run, with now ordered edges
edges <- edges[order(edges[,1], edges[,2]),]

social.graph <- graph.edgelist(as.matrix(edges), directed=T)
social.graph <- graph.adjacency(get.adjacency(social.graph), weighted=TRUE)

E(social.graph)$weight <- 1 / E(social.graph)$weight
set.seed(1)

between2 <- betweenness(social.graph)

print(merge(data.frame(between1=between1, names=names(between1)),
            data.frame(between2=between2, names=names(between2))))

the results are slightly different for two nodes 1341 and 1352

   names   between1   between2
1   1284  0.5833333  0.5833333
2   1304  0.0000000  0.0000000
3   1320 21.7500000 21.7500000
4   1336  1.7500000  1.7500000
5   1341 15.0833333 14.0833333
6   1345  2.0000000  2.0000000
7   1350  0.7500000  0.7500000
8   1352 74.2500000 75.2500000
9   1356  0.0000000  0.0000000
10  1358  0.0000000  0.0000000
11  1387  1.8333333  1.8333333
12  1398 16.0000000 16.0000000
13  1405  0.5833333  0.5833333
14  1439  1.0000000  1.0000000
15  1960 34.0000000 34.0000000
16  3918  0.0000000  0.0000000

this is very weird as the adjacency matrices are the same (only have different order of columns/rows). Is this a bug or betweenness does depends somehow on the ordering of the edges?

Answer 1

The following is based on the response of Tamás under the bug report I filed for this.

Betweenness is a property of the graph, so it does not depend on representation details such as edge ordering.

Why does igraph's result depend on ordering then?

As part of betweenness calculations, we must do equality comparisons between the total weights of different paths. Your weights are fractional floating point numbers and equality comparison between floating point numbers are unreliable.

Your weights are 1, 1/2, 1/3, 1/4 and 1/5, i.e. fractions that tend to add up to integers. Some of these number are however not exactly representable in binary. When they are actually added up, we might get tiny deviations from exact integers. Furthermore, the result may depend on the order of the summation due to roundoff errors. Due to these tiny deviations, the equality test will in some cases fail (i.e. return false).

The solution

This problem can be avoided if you only use integer weights because integers are always exactly representable. Multiplying all weights by the same factor does not change the betweenness values. Since your weights are the inverses of 1,2,3,4 and 5, just multiply them by the least common multiple, i.e. 60, to get integers.

Change

E(social.graph)$weight <- 1 / E(social.graph)$weight

to

E(social.graph)$weight <- 60 / E(social.graph)$weight