为什么边介数和加权边介数结果完全一样？

Question

我有两个图 (g1 & g2) 从邻接矩阵 (mtx1 & mtx2) 创建，一个未加权 (g1)另一个是加权的（g2），我正在计算两个图的边缘介数。

我的理解是，通过使用 edge_betweenness(g, weights = E(g)$weight)，我可以将边权重合并到加权图的边介数计算中，但是当我这样做时，我得到的加权图和未加权图的结果完全相同。

为什么在边缘介数的计算中增加权重不会改变结果分数？

考虑以下示例

library(igraph)

# create non-weighted adjacency matrix (mtx1) and a weighted matrix (mtx2)        
mtx1 <- matrix(c(0,1,0,0,0,1,0,1,1,0,0,1,0,0,1,0,1,0,0,0,0,0,1,0,0), ncol = 5)
mtx2 <- matrix(c(0,2,0,0,0,1,0,2,2,0,0,1,0,0,2,0,1,0,0,0,0,0,1,0,0), ncol = 5)

# convert to igraph objects
g1 <- graph.adjacency(mtx1)
g2 <- graph.adjacency(mtx2, weighted = TRUE)

# calculate edge betweenness for the two graphs 
edge_betweenness(g1)
[1] 4 4 6 4 6 4 4 4

edge_betweenness(g2, weights = E(g2)$weight)
[1] 4 4 6 4 6 4 4 4

Answer 1

一个顶点的edge_betweeness的定义是最短路径的数穿过那个顶点。对于g1和g2，任意两个节点之间的最短路径是相同的。由于你的权重，那些路径的 lengths 不一样，但是边的顺序是一样的。

如果你想看到一个加权图给出不同介数的例子，你必须构造一个权重变化的例子某事是否是最短路径。

这里有一个符合你精神的例子。

mtx3 <- matrix(c(0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0), ncol=4)
mtx4 <- matrix(c(0,2,1,0,2,0,0,1,1,0,0,1,0,1,1,0), ncol=4)
g3 <- graph.adjacency(mtx3)
g4 <- graph.adjacency(mtx4, weighted = TRUE)

edge_betweenness(g3)
[1] 2 2 2 2 2 2 2 2
edge_betweenness(g4, weights = E(g4)$weight)
[1] 1 2 1 2 2 3 2 3

注意路径1->2->4是g3的最短路径，g4不是。

为什么边介数和加权边介数结果完全一样？

Why are edge betweenness and weighted edge betweenness results exactly the same?

r

graph-theory

igraph