计算顶点邻域中有多少个顶点在 R 的 igraph 中具有属性

Question

我在igraph中有一个很大的图（实际上是几个），大约有100000个顶点，每个顶点都有一个属性，要么是true，要么是false。对于每个顶点，我想计算有多少直接连接到它的顶点具有该属性。我目前的解决方案是以下函数，它以一个图作为参数。

attrcount <- function(g) {
  nb <- neighborhood(g,order=1)
  return(sapply(nb,function(x) {sum(V(g)$attr[x]}))
}

这将返回一个计数向量，对于具有该属性的顶点，该向量为1，但我可以很容易地调整它。

问题是，这运行得非常慢，而且似乎应该有一种快速的方法来做到这一点，因为例如，使用degree(g)计算每个顶点的阶实际上是瞬时的。

我这样做是不是很愚蠢？

举个例子，假设这是我们的图。

set.seed(42)
g <- erdos.renyi.game(169081, 178058, type="gnm")
V(g)$att <- as.logical(rbinom(vcount(g), 1, 0.5))

Answer 1

使用get.adjlist查询所有相邻顶点，然后在此列表上使用sapply（或tapply可能更快）来获取计数。还值得将属性存储在向量中，因为这样就不需要一直提取它。

与sapply

system.time({
  al <- get.adjlist(g)
  att <- V(g)$att
  res <- sapply(al, function(x) sum(att[x]))
})
#   user  system elapsed 
#  0.571   0.005   0.576 

带tapply

system.time({
  al <- get.adjlist(g)
  alv <- unlist(al)
  alf <- factor(rep(seq_along(al), sapply(al, length)),
                levels=seq_along(al))
  att <- V(g)$att
  res2 <- tapply(att[alv], alf, sum)
  res2[is.na(res2)] <- 0
})
#   user  system elapsed 
#  1.121   0.020   1.144 
all(res == res2)
# TRUE

这让我有些惊讶，但tapply解决方案实际上更慢。

如果这还不够，那么我想你仍然可以通过用C/C++编写它来加快速度。

Answer 2

为了更快的计算，请使用get.adjacency拉取邻接矩阵，然后使用%*%:将矩阵乘以属性向量

library(igraph)
set.seed(42)
g <- erdos.renyi.game(1000, 1000, type = "gnm")
V(g)$att <- as.logical(rbinom(vcount(g), 1, 0.5))
system.time({
  ma   <- get.adjacency(g)
  att  <- V(g)$att
  res1 <- as.numeric(ma %*% att)
})
#  user  system elapsed 
# 0.003   0.000   0.003 

与使用get.adjlist和sapply相比：

system.time({
  al   <- get.adjlist(g)
  att  <- V(g)$att
  res2 <- sapply(al, function(x) sum(att[x]))
})
#   user  system elapsed 
#  9.733   0.243  10.107

修改res1的类别后，结果向量相同：

res1 <- as.numeric(res1)
identical(res1, res2)
# [1] TRUE