r - R，igraph，大数据：使用非常大的网络计算顶点到顶点的最短距离

Question

我有一个基于 100K 唯一顶点和 500M 边的非常大的网络（注意：边都是距离 1（二进制）且无向）。

我需要创建每个顶点对之间最短距离的 100K x 100K 矩阵。

我正在使用命令，它可以通过igraph以下distances()方式创建我想要的内容：

distance_mat <- distances(network, v=V(network), to=V(network), weights=NA)

但是，这种规模的网络会变得非常慢 - 目前估计我的代码需要超过 10 天才能在具有 16GB RAM 的 2.5 GHz i7 Mac 上完成。

有没有人优化过一个例程来在如此大的网络上做这样的事情，或者有关于如何加快这个速度的想法？

下面是一些示例代码，用于构建一个大型（但不是全尺寸）网络，如果有帮助，可以练习：

require(igraph)

n_id <- 100000
n_connect <- 100000000
id1 <- sample(1:n_id,n_connect,replace=T)
id2 <- sample(1:n_id,n_connect,replace=T)
nbr <- rep(1,n_connect)
idall <- unique(c(id1,id2))
df <- as.data.frame(cbind(id1,id2,nbr))

network <- graph_from_data_frame(d=df, vertices=idall, directed=F)

Sys.time()
dist_df <- distances(network, v=V(network)[1:1000], to=V(network)[1:1000], weights=NA)
Sys.time()

标签： rbigdataigraph