不需要中间的二分图的二分投影

Question

我有一个描述二分图的data.frame，其中包含一个非常大（数百万）和一个相对较小（数百）的独立集。

我想要获得基于较小独立集的二分图投影，但不需要先创建大的二分图，尤其是到大独立集的巨大二分图投影。这种限制的原因是igraph segfault和内存限制（我只有8GB内存）。

例如，给定

data.frame(beg=c("a","a","b","b","c","c"),
           end=c("1","2","1","2","1","2"),
           weight=1:6)

我想要数据框

data.frame(beg=c("a","a","b"),
           end=c("b","c","c"),
           weight=c(1+3+2+4,1+5+2+6,3+5+4+6))

边缘的权重相加。

(在这个例子中，abc 是“较小”的集合，而 12 是“较大”的集合）。

- sds

---

我写了一个答案，然后发现我可能不理解你的意思。你所说的“不建立二分图”，是指你想避免构建其邻接矩阵吗？你假设这个图是稀疏的吗？ - amit

@amit：我的担忧纯粹是实用的：我想避免在igraph中耗尽RAM并崩溃（请参见编辑）。 - sds

每个模式有多少节点，双分图的预期密度是多少？如果使用稀疏矩阵无法解决问题（据我所知，igraph使用的就是稀疏矩阵），那么您在R中可能会遇到一些麻烦。 - ndoogan

@ndoogan：igraph的问题在于它会导致段错误。 - sds

@ndoogan：用户（3,234,178）x发布者（100）的二分图，共有4,775,955条边（密度为1.476714%）。 - sds

Answer 1

这里有一个看起来能满足我的需求的内容（关键是使用data.table进行快速连接）：

> library(igraph)
> library(data.table)
data.table 1.8.8  For help type: help("data.table")
> f <- data.frame(beg=c("a","a","b","b","c","c"),
                  end=c("1","2","1","2","1","2"),
                  count=1:6)
> f
   beg end count
1:   a   1     1
2:   b   1     3
3:   c   1     5
4:   a   2     2
5:   b   2     4
6:   c   2     6
> m <- f[f,allow.cartesian=TRUE]

> m
    end beg weight beg.1 weight.1
 1:   1   a      1     a        1
 2:   1   b      3     a        1
 3:   1   c      5     a        1
 4:   1   a      1     b        3
 5:   1   b      3     b        3
 6:   1   c      5     b        3
 7:   1   a      1     c        5
 8:   1   b      3     c        5
 9:   1   c      5     c        5
10:   2   a      2     a        2
11:   2   b      4     a        2
12:   2   c      6     a        2
13:   2   a      2     b        4
14:   2   b      4     b        4
15:   2   c      6     b        4
16:   2   a      2     c        6
17:   2   b      4     c        6
18:   2   c      6     c        6
> v <- m$beg == m$beg.1
> m <- f[f,allow.cartesian=TRUE]
> v <- m$beg == m$beg.1
> m$end <- NULL
> m$weight <- (m$count + m$count.1)/2
> m$count <- NULL
> m$count.1 <- NULL
> m
    beg beg.1 weight
 1:   a     a      1
 2:   b     a      2
 3:   c     a      3
 4:   a     b      2
 5:   b     b      3
 6:   c     b      4
 7:   a     c      3
 8:   b     c      4
 9:   c     c      5
10:   a     a      2
11:   b     a      3
12:   c     a      4
13:   a     b      3
14:   b     b      4
15:   c     b      5
16:   a     c      4
17:   b     c      5
18:   c     c      6
> ve <- data.table(vertex=m$beg[v], weight=m$weight[v], key="vertex")
> ve <- ve[, list(count = .N, weight = sum(weight)), by = "vertex"]
> ve
   vertex count weight
1:      a     2      3
2:      b     2      7
3:      c     2     11
> g1 <- graph.data.frame(m[!v,], vertices=ve, directed=FALSE)
> g1 <- simplify(g1, edge.attr.comb="sum")
> V(g1)$weight
[1]  3  7 11
> E(g1)$weight
[1] 10 14 18

- sds

Answer 2

以下是我会如何做（假设你的边缘在 df 中，而“小”集合在边缘的开头）

对于小集合中的每一对节点，我将使用以下方法：

do.pair = function(x,y) {
     tmp = intersect(df$end[df$beg==x],df$end[df$beg==y])
     res = sum(df$weight[(df$beg %in% c(x,y)) & (df$end %in% tmp)])
     return(res)
}

现在，您可以按照自己喜欢的方式创建一对列表（可以使用exapnd.grid或outer），然后使用相关的apply函数。在这里，我只是做了一个简单的嵌套循环，虽然不是非常高效，但易于阅读。

g.small = unique(df$beg)
n = length(g.small)
res = list()
cnt=0
for (i in 1:(n-1)) {
    for (j in (i+1):n) {
       cnt = cnt+1
       res[[cnt]] = list(beg=g.small[i],end=g.small[j],weight=do.pair(g.small[i],g.small[j]))
    }
}

do.call(rbind,res)

- amit