检查 R igraph 中节点之间的连接时的时间复杂度问题

Question

我想查看给定图中每个节点的哪些一级节点连接到哪些二级节点。假设我生成一个有 1000 个节点的图。

library(igraph)
g <- erdos.renyi.game(1000, 0.2)

当我为图中的每个节点计算相邻节点和二度节点的集合时，没有问题。

代码运行速度非常快，不受网络规模的影响。一旦我添加了一个 if 语句来检查两个节点是否连接为：

for(j in adjacent){
      for(k in secondDegreNodes){
             if(  are.connected(g, j, k) ){

             }
         }
      }

我的代码需要永远。我面临的确切复杂性问题是什么？有没有更好的方法来进行这个操作？

确实发生了一些奇怪的事情。即使是下面的代码块也不会收敛，尽管它是最简单的操作。

g <- erdos.renyi.game(1000, 0.3)
A <- as_adjacency_matrix(g)
from<- 1
to <- nrow(A)
for(i in from:to){
  for(j in i:to){
    if(A[i,j] == 1){
      #do nothing
    }

  }
}

编辑：我相信 igraph 包可能存在一些问题。我在 R igraph 中生成了图表，并用 Java 语言对所有内容进行了编码，并且成功了。如我所料，该算法没有复杂性问题。但是，我不知道 igraph 有什么问题。

Answer 1

在您给出的示例中，在 for 循环中重复索引矩阵 A 是相当低效的。在这个特定的例子中，这是由于 A 属于包 Matrix 的 class dgCMatrix。

当您比较将 A 转换为另一个 class 前后的性能时，您会注意到差异。对于 N = 300 个节点，一旦我转换为标准矩阵 class，for 循环的持续时间在我的机器上从 23.5 秒减少到 0.1 秒。此外还有 (N^2 + N) / 2 次比较。平方项意味着从 300 个节点增加到 3 x 300 = 900 个节点将使计算时间大致增加九倍（至少）。

如果您进一步 Rprof 归档代码，您将看到在对 class dgCMatrix（即 A[i, j]）的对象进行子集化时，还有许多其他 R 函数被调用，而函数 [ 直接在 C 中为基本矩阵 class 实现。另外，dgCMatrix来自S4对象系统。这意味着 i.a。找到用于 [ 的正确方法比平时要贵一些。

最后，如果您依赖 R，那么（通常）使用 向量化操作 会更好。这些通常会避免进一步（低效的）R 函数的深层调用堆栈，并且通常会在 C 中实现。使用邻接矩阵，您可以通过检查 A_2 = A %*% A 快速找到二阶节点，这也非常快（或我怀疑尤其如此）对于 class dgCMatrix.

的对象

时间：

library(igraph)

N <- 300
g <- erdos.renyi.game(N, 0.3)
A <- as_adjacency_matrix(g)
from<- 1
to <- nrow(A)

class(A)
# [1] "dgCMatrix"
# attr(,"package")
# [1] "Matrix"

# run through matrix via for loop
# 23.5 seconds
system.time({
  for(i in from:to){
    for(j in i:to){
      if(A[i,j] == 1) {}
    }
  }
})

# change class
A <- as.matrix(A)

class(A)
# [1] "matrix"

# run for loop again
# 0.097 seconds
system.time({
  for(i in from:to){
    for(j in i:to){
      if(A[i,j] == 1) {}
    }
  }
})

检查 R igraph 中节点之间的连接时的时间复杂度问题

time complexity issue when checking the connectivity between nodes in R igraph

performance

r

graph-theory

time-complexity

igraph