r - (局部/节点和全局)使用 igraph Shortest.paths 函数的效率

Question

我正在尝试使用 igraph 包的shortest.paths 来计算图的局部效率。

根据定义，顶点 v 的局部效率是在 v 的所有直接邻居之间计算的“全局效率”(Latora & Machiori，2001)。 为了提高全局和局部效率，我想出了下面的代码。然而，后者在其计算中包括目标顶点。在上面的论文中，他们说必须删除目标顶点。

#Global Efficiency (average inverse shortest paths between all u--v vertices)
eff<-1/(shortest.paths(my.graph))
eff[!is.finite(eff)]<-0
gl.eff<-mean(eff,na.rm=TRUE)    

#Mean local efficiency (global efficiency for each node)
gn<-graph.neighborhood(my.graph,1) #list with subgraphs of directly connected graphs
names(gn)<-colnames(my.corr.matrix)
local.eff<-numeric(length(gn))
for (i in 1:length(gn)){
  gn[[i]]<-gn[[i]] - vertex(V(gn[[i]])[grep(names(gn[i]),V(gn[[i]]))]) #doesn't match
  eff.gn<-1/(shortest.paths(gn[[i]]))
  eff.gn[!is.finite(gleff.gn)]<-0
  eff.gn<-mean(eff.gn,na.rm=TRUE)
  local.eff[i]<-gleff.gn
  mean.local.eff<-mean(local.eff, na.rm=TRUE)
}

我试图将列表名称(列表的每个元素都是一个子图)与该子图中的顶点名称进行匹配。我正在尝试使用“grep()”，但未能正确使用。有人可以帮我吗？

提前致谢，

Answer 1

我已经编写了一个函数来执行此操作，它比您编写的速度快很多倍。看看以下内容是否能满足您的需求。对于较小的图形(或者如果您使用的是 Windows)，您可能需要将 simplify2array(mclapply(nodes,) 替换为 sapply(nodes,)，然后当然删除参数mc.cores=detectCores()。然而，这确实有助于大型图的性能。

您可以在以下链接中查看代码:

Local efficiency code

编辑:包括一些基准信息(其中函数f是你的，g是我上面粘贴的)。这是在 4 核 @2.10 GHz (Intel i3-2310m) 笔记本电脑上完成的。

g.rand <- sample_gnp(100, .1)
V(g.rand)$degree <- degree(g.rand)
compare <- microbenchmark(f(g.rand), g(g.rand), times=1e2)
compare
Unit: milliseconds
      expr      min        lq     mean   median       uq      max neval cld
 f(g.rand) 476.9853 4097.2202 4544.720 4539.911 4895.020 9346.873   100   b
 g(g.rand) 299.2696  329.6629 1319.377 1114.054 2314.304 3003.966   100  a