R - 用 data.table 连接超过 2^31 行

Question

我有一个 igraph 网络图，其中包含 103,887 个节点和 4,795,466 个联系。

这可以构造为 data.table 中的边缘列表，其中包含近 900 万行。

根据@chinsoon12 的回答here，我可以找到这个网络中的共同邻居。请参阅下面的示例。

这适用于较小的网络，但在我的用例中遇到问题，因为合并导致超过 2^31 行。

问题：

是否有有效的替代方法来处理这个问题？
我可以拆分数据并分步计算吗？结果将用于查询共同邻居。

示例 - 根据@chinsoon12 的回答修改：

library(data.table)
library(igraph)

set.seed(1234)
g <- random.graph.game(10, p=0.10)

adjSM <- as(get.adjacency(g), "dgTMatrix")
adjDT <- data.table(V1=adjSM@i+1, V2=adjSM@j+1)

res <- adjDT[adjDT, nomatch=0, on="V2", allow.cartesian=TRUE
][V1 < i.V1, .(Neighbours=paste(V2, collapse=",")),
  by=c("V1","i.V1")][order(V1)]

res

   V1 i.V1 Neighbours
1:  4    5          8
2:  4   10          8
3:  5   10          8

Answer 1

common neighbors

Can I split the data and do the computation in steps?

你可以通过V1拆分来避免运行进入big-merge问题：

neighDT = adjDT[, if (.N > 1) {
    cb = combn(V2, 2)
    .(a = cb[1, ], b = cb[2, ])
}, by=.(neighbor = V1)]

这给出了

   neighbor a  b
1:        8 4  5
2:        8 4 10
3:        8 5 10

（OP 发现 gRbase::combnPrim 比 combn 快。）

How can we collapse all the common neighbors (separated with a comma) for the same combination into one observation?

neighDT_agg = neighDT[order(neighbor), 
  .(neighbors = toString(neighbor))
, keyby=.(a,b)]

order 确保字符串按字母顺序排序。 keyby 确保 table 按对 {a,b} 排序，并有助于一次简单快速地查找多个对：

# single query
neighDT_agg[.(4,10), neighbors]
# [1] "8"

# multi query
pairs_queryDT = data.table(a = c(4,5,8), b = c(5,10,10))
neighDT_agg[pairs_queryDT, neighbors]
[1] "8" "8" NA

I have an igraph network graph with 103,887 nodes and 4,795,466 ties.

每次调用 combn 都会生成一个 2×choose(.N, 2) 矩阵。如果一个节点连接到所有其他节点，那么它是所有其他节点对的公共邻居，您将面对这些对中的 choose(103887-1, 2)。我想这更多是问题定义方式的问题，而不是解决问题的方法问题。

The results will be used to query about common neighbors.

对于上述方法，您需要先计算完整邻居 table。

如果您只是有几个关于相交邻居的临时查询：

find_neighbors <- function(a, b){
    adjDT[.(c(a, b)), on=.(V1), V2[duplicated(V2)]]
}

find_neighbors(4, 10)
# [1] 8

这可以类似地包含在 toString 中以折叠值。

Answer 2

更新

如果你只是想查询共同的邻居，我不建议你建立一个巨大的查找table。相反，您可以使用以下代码获取查询结果：

find_common_neighbors <- function(g, Vs) {
  which(colSums(distances(g, Vs) == 1) == length(Vs))
}

这样

> find_common_neighbors(g, c(4, 8))
integer(0)

> find_common_neighbors(g, c(4, 5))
[1] 8

如果您需要查找 table，另一种方法是使用 Neighbours 作为搜索其关联节点的键，例如，

res <- transform(
  data.frame(Neighbours = which(degree(g) >= 2)),
  Nodes = sapply(
    Neighbours,
    function(x) toString(neighbors(g, x))
  )
)

上一个答案

我认为您可以直接使用 ego 而不是 g 来生成 res，例如

setNames(
  data.frame(
    t(do.call(
      cbind,
      lapply(
        Filter(function(x) length(x) > 2, ego(g, 1)),
        function(x) {
          rbind(combn(x[-1], 2), x[1])
        }
      )
    ))
  ),
  c("V1", "V2", "Neighbours")
)

这给出了

  V1 V2 Neighbours
1  4  5          8
2  4 10          8
3  5 10          8

R - 用 data.table 连接超过 2^31 行

R - joining more than 2^31 rows with data.table

r

merge

data.table

igraph

更新

上一个答案