时间戳

首页 > 解决方案 > 为什么边缘介数和加权边缘介数结果完全相同？

r - 为什么边缘介数和加权边缘介数结果完全相同？

问题描述

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

我的理解是，通过使用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

标签： rigraphgraph-theory

解决方案

顶点的edge_betweeness 的定义是通过该顶点的最短路径的数量。对于 g1 和 g2，任何两个节点之间的最短路径都是相同的。由于您的权重，这些路径的长度不同，但边的顺序是相同的。

如果您希望看到加权图给出不同中间值的示例，则必须构建一个示例，其中无论某事物是否是最短路径，权重都会发生变化。

这是一个本着你精神的例子。

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。

推荐阅读