改进R中社会网络分析的处理性能

Question

我正在使用R中的igraph包进行社交网络分析，我正在处理近200万个顶点和边。还计算了近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

我不这么认为，但我很乐意被证明是错的。

你应该寻找优化正在运行的代码的其他方法。

如果你的数据是固定的，你可以计算一次距离，保存(可能相当大的)距离矩阵，并要求分离度。

如果你的分析不需要所有x顶点之间的距离，你应该考虑通过缩短t_ids$ID_from[x]来优化你的代码。只得到你需要的距离。不过，我怀疑你已经在这么做了。

distances()实际上计算相当快。在10000个节点(相当于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

我不认为可以从中得出任何结论，但它在Erdős-Rényi模型上运行。你的网络结构可能偏向于一种算法而不是另一种算法，但它们仍然不能给你所希望的性能提升。

代码如下:

# 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