4

すべての頂点を繰り返し処理し、隣接する頂点に基づいて新しい属性を計算するという単純なタスクを実行しています。SOを検索しましたが、これまでのところ、少なくとも3つの方法があることがわかっています。

  1. ad_adj_list を使用して adj リストを作成し、各要素を反復処理します。
  2. sapply を使用して、各頂点を直接反復します。

ただし、どちらの方法も、データの規模 (300k の頂点と 800 万のエッジ) に対して時間がかかりすぎます。頂点をループする高速な方法はありますか? ありがとう！

ベンチマークとして、次のサンプル データがあるとします。

set.seed <- 42
g <- sample_gnp(10000, 0.1)
V(g)$name <- seq_len(gorder(g)) # add a name attribute for data.table merge
V(g)$attr <- rnorm(gorder(g))
V(g)$mean <- 0 # "mean" is the attribute I want to compute

方法 1. のコードは次のとおりです。

al <- as_adj_list(g)
attr <- V(g)$attr
V(g)$mean <- sapply(al, function(x) mean(attr[x])) 
# took 28s
# most of the time is spent on creating the adj list

方法 2. のコードは次のとおりです。

compute_mean <- function(v){
    mean(neighbors(g, v)$attr)
}
V(g)$mean <- sapply(V(g), compute_mean)  # took 33s

私は、igraph-R が頂点の相互作用をそれほど遅くすべきではないと信じています。さもなければ、数百万のサイズの大きなグラフの分析が不可能になります。このタスクは、R ユーザーにとって非常に一般的なはずです!

アップデート

by@MichaelChirico のコメントによると、次のように、グラフ構造を data.table にインポートし、data.table構文で計算を行うという 3 番目の方法を思いつきました。

gdt.v <- as_data_frame(g, what = "vertices") %>% setDT() # output the vertices
gdt.e <- as_data_frame(g, what = "edges") %>% setDT() # output the edges
gdt <- gdt.e[gdt.v, on = c(to = "name"), nomatch = 0] # merge vertices and edges data.table
mean <- gdt[, .(mean = mean(attr)), keyby = from][, mean]
V(g)$mean <- mean 
# took only 0.74s !!

data.table の方法ははるかに高速です。ただし、その結果は最初の 2 つの方法の結果とまったく同じではありません。さらに、このような単純なタスクを実行するために別のパッケージに依存しなければならないことに非常に失望しています。これが igraph-R の強みであるはずです。私が間違っていることを願っています！

4

1 に答える 1

1

実際の問題がどこにあるのかわかりません...コードを再実行すると:

library(microbenchmark)
library(data.table)
library(igraph)
set.seed <- 42
g <- sample_gnp(10000, 0.1)
V(g)$name <- seq_len(gorder(g)) # add a name attribute for data.table merge
V(g)$attr <- rnorm(gorder(g))
V(g)$mean <- 0 # "mean" is the attribute I want to compute
gg <- g

...そして式で2つのメソッドを比較しe1、e2

e1 <- expression({
  al <- as_adj_list(gg)
  attr <- V(gg)$attr
  V(gg)$mean <- sapply(al, function(x) mean(attr[x]))  
})

e2 <- expression({
  gdt.v <- as_data_frame(g, what = "vertices") %>% setDT() # output the vertices
  gdt.e <- as_data_frame(g, what = "edges") %>% setDT() # output the edges
  gdt <- gdt.e[gdt.v, on = c(to = "name"), nomatch = 0] # merge vertices and edges data.table
  mean <- gdt[, .(mean = mean(attr)), keyby = from][, mean]
  V(g)$mean <- mean 
})

タイミングは次のとおりです。

microbenchmark(e1, e2)

## Unit: nanoseconds
##  expr min lq  mean median uq max neval cld
##    e1  47 47 51.42     48 48 338   100   a
##    e2  47 47 59.98     48 48 956   100   a

非常によく似ており、結果は

all.equal(V(g)$mean, V(gg)$mean)

## [1] TRUE

... 同じだ。

于 2015-10-26T13:04:35.543 に答える