(local/nodal and global) 使用 igraph shortest.paths 函数的效率

Question

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

根据定义，顶点 v 的局部效率是 "global efficiency" 在 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

我知道我的标题并没有完全说明我的问题。所以我自己回答，因为我刚开始工作。

#Mean local efficiency (global efficiency for each node)
gn<-graph.neighborhood(my.graph,1) #list with subgraphs of directly connected graphs
names(gn)<-V(my.graph)$name
local.eff<-numeric(length(gn))
for (i in 1:length(gn)){
  gn[[i]]<-gn[[i]] - vertex(V(gn[[i]])[match(names(gn[i]),V(gn[[i]])$name)]) #MATCHES
  eff.gn<-1/(shortest.paths(gn[[i]]))
  eff.gn[!is.finite(eff.gn)]<-0
  eff.gn<-mean(eff.gn,na.rm=TRUE)
  local.eff[i]<-eff.gn
}
local.eff[local.eff %in% NaN]<-NA
mean.local.eff<-mean(local.eff, na.rm=TRUE)

Answer 2

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

代码见link:

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

Answer 3

如果有人需要python中的本地效率，这是我的代码：

Python版本

import numpy as np
from igraph import *
np.seterr(divide='ignore')


def nodal_eff(g):
    """
    This function calculates the nodal efficiency of a weighted graph object.
    Created by: Loukas Serafeim (seralouk), Nov 2017

    Args:
     g: A igraph Graph() object.
    Returns:
     The nodal efficiency of each node of the graph
    """

    sp = g.shortest_paths_dijkstra(weights = g.es["weight"])
    sp = np.asarray(sp)
    temp = 1.0 / sp
    np.fill_diagonal(temp, 0)
    N = temp.shape[0]
    ne = ( 1.0 / (N - 1)) * np.apply_along_axis(sum, 0, temp)

    return ne

(local/nodal and global) 使用 igraph shortest.paths 函数的效率

(local/nodal and global) Efficiency using igraph shortest.paths function

r

graph-theory

igraph

shortest-path

Python版本