为二分图检测 r 中的双派系

Question

我正在尝试在 R 中重新创建 Biclique Communities 方法 (Lehmann, Schwartz, & Hansen, 2008)，它依赖于 Ka,b biclique 的定义。下面的示例显示了两个相邻的 K2,2 bicliques - 第一个 clique 是 {A,B,1,2}，第二个 clique 是 {B,C,2,3}。我希望能够使用 R 识别这些派系，以便我可以将其应用于更广泛的数据集。

到目前为止，我已经将我的尝试包含在 R 中，但我遇到了以下两个问题：

如果我使用标准 walktrap.community 它会识别社区但不允许集 {B,2} 属于两个集团
如果我使用更新的 clique.community 函数，这似乎无法识别派系或者我没有正确理解（或两者）

示例代码：

library(igraph)

clique.community <- function(graph, k) {
  clq <- cliques(graph, min=k, max=k)
  edges <- c()
  for (i in seq_along(clq)) {
    for (j in seq_along(clq)) {
      if ( length(unique(c(clq[[i]], clq[[j]]))) == k+1 ) {
        edges <- c(edges, c(i,j))
      }
    }
  }
  clq.graph <- simplify(graph(edges))
  V(clq.graph)$name <- seq_len(vcount(clq.graph))
  comps <- decompose.graph(clq.graph)

  lapply(comps, function(x) {
    unique(unlist(clq[ V(x)$name ]))
  })
}

users <- c('A', 'A', 'B', 'B', 'B', 'C', 'C')
resources <- c(1, 2, 1, 2, 3, 2, 3)
cluster <- data.frame(users, resources)
matrix <- as.data.frame.matrix(table(cluster))

igraph <- graph.incidence(matrix)

clique.community(igraph, 2)
walktrap.community(igraph)

Answer 1

我设法在 Sisob workbench

中找到了一个脚本

computeBicliques <- function(graph, k, l) {

  vMode1 <- c()
  if (!is.null(V(graph)$type)) {

    vMode1 <- which(!V(graph)$type)
    vMode1 <- intersect(vMode1, which(degree(graph) >= l))
  }

  nb <- get.adjlist(graph)

  bicliques <- list()

  if (length(vMode1) >= k) {

    comb <- combn(vMode1, k)
    i <- 1
    sapply(1:ncol(comb), function(c) {

      commonNeighbours <- c()
      isFirst <- TRUE

      sapply(comb[,c], function(n) {

        if (isFirst) {

          isFirst <<- FALSE
          commonNeighbours <<- nb[[n]]
        } else {

          commonNeighbours <<- intersect(commonNeighbours, nb[[n]])
        }
      })

      if (length(commonNeighbours) >= l) {

        bicliques[[i]] <<- list(m1=comb[,c], m2=commonNeighbours)
      }

      i <<- i + 1
    })
  }
  bicliques
}

Answer 2

请注意，由于 comb <- combn(vMode1, k) 变得非常大，即使对于小（密集）图和 k,l 值，上述解决方案也会很快变得效率低下。

可以在 https://github.com/YupingLu/biclique 正在开发的 "biclique" 包中找到更有效的解决方案。

为二分图检测 r 中的双派系

Detect bi-cliques in r for bipartite graph

r

clique-problem

igraph

bipartite

sna