找出节点 u 和 v 之间经过节点 g 的最短路径总数

Question

我有以下生成无向网络图的矩阵：

  a b c d e f g h i j
a 0 1 1 0 0 0 0 0 0 0
b 1 0 1 0 0 0 0 0 0 0
c 1 1 0 1 1 0 1 0 0 0
d 0 0 1 0 1 0 0 0 0 0
e 0 0 1 1 0 1 0 0 0 0
f 0 0 0 0 1 0 1 0 0 0
g 0 0 1 0 0 1 0 1 0 0
h 0 0 0 0 0 0 1 0 1 1
i 0 0 0 0 0 0 0 1 0 0
j 0 0 0 0 0 0 0 1 0 0

m <- structure(c(0L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 1L, 
0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 0L, 1L, 1L, 0L, 1L, 0L, 0L, 
0L, 0L, 0L, 1L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 0L, 
1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 1L, 0L, 0L, 0L, 0L, 
0L, 1L, 0L, 0L, 1L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 
0L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 
0L, 0L, 0L, 0L, 1L, 0L, 0L), .Dim = c(10L, 10L), .Dimnames = list(
    c("a", "b", "c", "d", "e", "f", "g", "h", "i", "j"), c("a", 
    "b", "c", "d", "e", "f", "g", "h", "i", "j")))

library(igraph)
g3n <- graph.adjacency(m)

我对手动计算节点'g'的betweeness很感兴趣，这需要在所有可能的节点中找到最短路径作为分母和分子，因为最短路径的数量包含节点[=23] =].

我使用以下代码生成所有节点之间的最短路径的长度：

shortest.paths(g3n, v=V(g3n), to=V(g3n))

最短路径矩阵：

  a b c d e f g h i j
a 0 1 1 2 2 3 2 3 4 4
b 1 0 1 2 2 3 2 3 4 4
c 1 1 0 1 1 2 1 2 3 3
d 2 2 1 0 1 2 2 3 4 4
e 2 2 1 1 0 1 2 3 4 4
f 3 3 2 2 1 0 1 2 3 3
g 2 2 1 2 2 1 0 1 2 2
h 3 3 2 3 3 2 1 0 1 1
i 4 4 3 4 4 3 2 1 0 2
j 4 4 3 4 4 3 2 1 2 0

有没有一种方法可以计算 2 个节点之间的最短路径包含节点 'g' 作为矩阵或仅以 R 中的任何其他方式包含的次数？

Answer 1

所以，我不确定这个解决方案有多优雅，但以下应该可行：

#initialize a list to populate with all the shortest paths in the graphy
allpaths <- list()


#Assuming this is an undirected graph, we don't want to calculate both a %--% b and b %--% a  
for(x in V(g3n)$name){
  for(y in V(g3n)$name){
    if(x < y){
      shortest_path_options <- all_shortest_paths(g3n, x, y)$res

      #sometimes there are multiple shortest paths, we will include them all
      for(z in shortest_path_options){
        allpaths[[length(allpaths)+1]] <- z$name
      }
    }
}

#create a boolean of whether a shortest path contains 'g' or not
allpaths_bool <- sapply(allpaths, function(x){
  ('g' %in% x) & (head(x, 1) != 'g') & (tail(x, 1) != 'g')
  })

#Show all the paths that contain 'g'
allpaths[allpaths_bool]

您可以通过将所有内容包装到 sapply 函数中来计算每个顶点。

sapply(V(g3n)$name, function(x){
  temp_bool <- sapply(allpaths, function(y){
    (x %in% y) & (head(y, 1) != x) & (tail(y, 1) != x)
  })
  length(allpaths[temp_bool])
})

一定有更简单的方法，但我不太确定。可能有一种方法可以通过使用提供中间中心性测量的 betweeness 函数来推断此信息，但我对图论的了解并不多。

找出节点 u 和 v 之间经过节点 g 的最短路径总数

Find total number of shortest paths between nodes u and v that pass through node g

r

igraph

network-analysis