计算相邻边列表的最快方法 (as_adj_edge_list)

Question

这个问题快把我逼疯了。首先说我有一个示例 directed 图，例如：

g <- sample_gnp(20000, 0.1, directed = T)

现在我想计算一个人所有出边的 "mutual edges" 的比例。这是我想到的最快的方法：

ael <- as_adj_edge_list(graph, mode = "out")
sapply(ael, function(x) {mean(which_mutual(g, x))})

然而，as_adj_edge_list函数似乎耗费了无穷无尽的时间。我的真实数据有大约 23k 个顶点和 110k 个边，所以我不能只是设置并等待代码完成。此外，通过搜索 SO 帖子，我发现 as_adj_edge_list 已经是迭代顶点或边的最快方法。那么我是在以愚蠢的方式使用它吗？提前谢谢了。

Answer 1

如果转换模式为 "mutual"，互边对应于图 g.dir 的无向版本 g.undir 的边。然后求出边中互边的比例为ratio

degree in g.undir / 'outgoing'-degree in g.dir

library(igraph)

g.dir <- sample_gnp(1000, 0.1, directed = T)

#-----------------------------------------

system.time(
{
  ael <- as_adj_edge_list(g.dir, mode = "out")
  A <- sapply(ael, function(x) {mean(which_mutual(g.dir, x))})

})

#-----------------------------------------

system.time(
{
  g.undir <- as.undirected(g.dir,mode="mutual")   
  d.dir <- degree(g.dir,mode="out")
  d.undir <- degree(g.undir)

  B <- d.undir/d.dir
})

identical(A,B)

.

> library(igraph)

> g.dir <- sample_gnp(1000, 0.1, directed = T)

> #-----------------------------------------
> 
> system.time(
+ {
+   ael <- as_adj_edge_list(g.dir, mode = "out")
+   A <- sapply(ael, function(x) { .... [TRUNCATED] 
   user  system elapsed 
  11.93    0.00   12.04 

> #-----------------------------------------
> 
> system.time(
+ {
+   g.undir <- as.undirected(g.dir,mode="mutual")   
+   d.dir <- degree(g.dir,mode .... [TRUNCATED] 
   user  system elapsed 
      0       0       0 

> identical(A,B)
[1] TRUE
>

计算相邻边列表的最快方法 (as_adj_edge_list)

the fastest way to compute adjacent edge list (as_adj_edge_list)

r

igraph