igraph 介数取决于边的顺序

机器算法验证 图形
2022-04-08 00:49:17

我有一个问题,图中边的顺序是否重要?

似乎中介函数对输入文件的不同顺序产生略有不同的结果。

输入文件: 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))))

两个节点 1341 和 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

这很奇怪,因为邻接矩阵是相同的(只有列/行的顺序不同)。这是一个错误还是中间性确实取决于边缘的顺序?

1个回答

以下内容基于我为此提交的错误报告中Tamás的回复。

介数是图的一个属性,因此它不依赖于表示细节,例如边排序。

为什么 igraph 的结果取决于排序呢?

作为介数计算的一部分,我们必须在不同路径的总权重之间进行相等比较。您的权重是分数浮点数,浮点数之间的相等比较是不可靠的。

您的权重是 1、1/2、1/3、1/4 和 1/5,即倾向于加起来为整数的分数。然而,其中一些数字不能完全用二进制表示。当它们实际相加时,我们可能会得到与精确整数的微小偏差。此外,由于舍入误差,结果可能取决于求和的顺序。由于这些微小的偏差,相等性测试在某些情况下会失败(即返回假)。

解决方案

如果只使用整数权重,则可以避免这个问题,因为整数总是可以精确表示的。将所有权重乘以相同的因子不会改变介数值。由于您的权重是 1、2、3、4 和 5 的倒数,只需将它们乘以最小公倍数,即 60,即可得到整数。

改变

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

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