ソーシャルネットワーク分析のためのRの処理性能を改善する

Question

Rでigraphパッケージを使用してソーシャルネットワーク分析を行っています.2百万近くの頂点とエッジを処理しています。また、約800万の頂点とエッジである分離度を計算します。通常、実行には2〜3時間かかりますが、それはあまりにも高すぎます。このパフォーマンスを向上させるために、いくつかの提案と提案が必要です。以下は私が使用しているサンプルコードです：

g <- graph.data.frame(ids, directed = F) # ids contains approximately 2 million records 
distances(graph = g, v = t_ids$ID_from[x], to = t_ids$ID_to[x], weights = NA) 
# t_ids contains approximately 8 million records for which degrees of separation is to be calculated using Shortest Path Algorithms 

ありがとうございます！

Answer 1

私はそうは思いませんが、私は間違っていることが判りました。

実行中のコードを最適化する他の方法を検討する必要があります。

データが修正されている場合は、距離を1回計算して（おそらくかなり大きい）距離行列を保存し、分離度を求めることができます。

あなたの分析ははすべてx頂点間の距離を必要としない場合は、t_ids$ID_from[x]を短くすることによって、あなたのコード内の最適化を行うことになっているはずです。必要な距離だけを取得します。私はあなたがすでにこれをやっていると思う。

distances()は、実際にはかなり迅速に計算されます。 10,000ノード（4,99 * 10^6の無指定距離に相当）で、私の気味悪いマシンは、数秒で700MBの大規模な距離行列を取得します。

私は最初にdistances()で選択できるさまざまなアルゴリズムについて考えましたが、今はそれらがあなたを助けるとは思っていません。私はあなたにそれらのどれかをお勧めできるかどうかを確認するために、さまざまなアルゴリズムの速度テストを実行しましたが、それらはすべて同じ速度で実行されるようです（結果は、使用される自動アルゴリズムを使用して計算する時間）上記のコードの中で：

sample automatic unweighted dijkstra bellman-ford johnson 
1  10   1 0.9416667 0.9750000 1.0750000 1.0833333 
2 100   1 0.9427083 0.9062500 0.8906250 0.8958333 
3 1000   1 0.9965636 0.9656357 0.9977090 0.9873998 
4 5000   1 0.9674200 0.9947269 0.9691149 1.0007533 
5 10000   1 1.0070885 0.9938136 0.9974223 0.9953602 

私は何もこのことから結論付けることができるとは思わないが、それはオルドス・レーニイモデルで実行されています。あなたのネットワーク構造が別のアルゴリズムよりも1つのアルゴリズムを優先する可能性はありますが、ではなく、はあなたが期待しているパフォーマンス向上の近くにいます。

コードはここにある：

# igrpah 
library(igraph) 

# setup: 
samplesizes <- c(10, 100, 1000, 5000, 10000) 
reps <- c(100, 100, 15, 3, 1) 
algorithms = c("automatic", "unweighted", "dijkstra", "bellman-ford", "johnson") 
df <- as.data.frame(matrix(ncol=length(algorithms), nrow=0), stringsAsFactors = FALSE) 
names(df) <- algorithms 

# any random graph 
g <- erdos.renyi.game(10000, 10000, "gnm") 

# These are the different algorithms used by distances: 
m.auto <- distances(g, v=V(g), to=V(g), weights=NA, algorithm="automatic") 
m.unwg <- distances(g, v=V(g), to=V(g), weights=NA, algorithm="unweighted") 
m.dijk <- distances(g, v=V(g), to=V(g), weights=NA, algorithm="dijkstra") 
m.belm <- distances(g, v=V(g), to=V(g), weights=NA, algorithm="bellman-ford") 
m.john <- distances(g, v=V(g), to=V(g), weights=NA, algorithm="johnson") 

# They produce the same result: 
sum(m.auto == m.unwg & m.auto == m.dijk & m.auto == m.belm & m.auto == m.john) == length(m.auto) 


# Use this function will be used to test the speed of distances() run using different algorithms 
test_distances <- function(alg){ 
     m.auto <- distances(g, v=V(g), to=V(g), weights=NA, algorithm=alg) 
     (TRUE) 
} 

# Build testresults 
for(i.sample in 1:length(samplesizes)){ 
     # Create a random network to test 
     g <- erdos.renyi.game(samplesizes[i.sample], (samplesizes[i.sample]*1.5), type = "gnm", directed = FALSE, loops = FALSE) 

     i.rep <- reps[i.sample] 

     for(i.alg in 1:length(algorithms)){ 
       df[i.sample,i.alg] <- system.time(replicate(i.rep, test_distances(algorithms[i.alg])))[['elapsed']] 
     } 
} 

# Normalize benchmark results 
dfn <- df 

dfn[,1:length(df[,])] <- df[,1:length(df[,])]/df[,1] 
dfn$sample <- samplesizes 
dfn <- dfn[,c(6,1:5)] 
dfn