0

我想知道识别影响焦点节点 i 的介数中心性的节点（j，k）的最佳方法。由于介数基于通过 i 的 j 和 k 之间的测地线，因此一种方法是获取网络中的所有最短路径，仅选择那些包含 i 的路径，并获取这些路径上节点的 ID . 然而

library(igraph)    
test <- shortest_paths(sample_gnp(200,.001),from=1)

运行大约需要 9 秒，这仅适用于来自第一个节点的路径；据我了解，shortest_paths一次只会计算一个节点的路径。这涉及到很多不相关的信息，因为我真的只想要通过 i 的测地线。我假设中介函数本身使用广度优先搜索或其他算法以更有效的方式执行此操作，但我在 igraph 或 sna 的文档中看不到任何允许这样做的内容。我想避免在这里重新发明轮子。

简而言之，给定一个网络和一个焦点节点 i，找到 j 和 k 之间包括 i 的所有测地线的最佳方法是什么？

更新：这是我写的一个似乎可以解决问题的函数（虽然我还没有仔细检查过）。在具有 0.2 平局概率的 100 个节点的随机图上，它很慢，但不是不可行的。我相信有更好的方法来做到这一点。 

find.shortest.paths <- function(net,focus){
  nodes.on.path <- vector(mode="numeric")
  n <- length(V(net))
  for(i in 1:n){
    for(j in 1:n){
      if(i !=  focus & j != focus){
        p <- all_shortest_paths(net,i,j)
        if(focus %in% (unlist(p$res))==T){
          nodes.on.path <- unique(c(nodes.on.path,unlist(p$res)))
        }
      }
    }
  }  
  return(sort(nodes.on.path))
}

ex <- sample_gnp(100,.2)
#try e.g. node 14 as focal node
system.time(test <- find.shortest.paths(ex,focus=14))
4

0 回答 0