如何使用 R 中的 igraph 包计算图形或网络中 2 星或楔形的数量

Question

igraph

包提供了非常有效的计算图形或网络中三角形数量的方法，即

count_triangles()

函数。

我无法使用

getAnywhere

找到该函数的源代码，因为对该函数的一个小修改会给我 2 星计数，我推测是这样。

是否有任何快速算法可以从图表中找到 2 星或楔形计数？

假设我们想从下图中找到楔子的数量

w3 <- matrix(c(c(0,1,1,1), c(1,0,1,0), c(1,1,0,0), c(1,0,0,0)), nrow = 4, ncol = 4)
w21 <- graph_from_adjacency_matrix(w3, mode = "undirected")

三角形计数结果如下 对于像

w3

这样的小图

triangle_cnt <- function(adj_mat){
  return(sum(diag(adj_mat %*% adj_mat %*% adj_mat)))
}# triangle count function

triangle_cnt.igraph <- function(adj_mat){
  adg_mat <- graph_from_adjacency_matrix(adj_mat)
  return(sum(count_triangles(adg_mat)) * 2)
}# triangle count function
microbenchmark::microbenchmark(triangle_cnt(w3), triangle_cnt.igraph(w3))

输出

> microbenchmark::microbenchmark(triangle_cnt(w3), triangle_cnt.igraph(w3))
Unit: microseconds
                    expr    min     lq     mean median      uq     max neval
        triangle_cnt(w3)  1.435  1.640  2.06394   2.05  2.1730  14.104   100
 triangle_cnt.igraph(w3) 57.400 58.999 63.25521  59.86 62.3815 254.692   100

但是对于具有1000+节点的大型图，以下性能变化巨大

> microbenchmark::microbenchmark(triangle_cnt(adj_mat), triangle_cnt.igraph(adj_mat))
Unit: milliseconds
                         expr      min       lq     mean   median       uq      max neval
        triangle_cnt(adj_mat) 651.1529 660.7670 669.5889 663.1095 665.9754 753.3584   100
 triangle_cnt.igraph(adj_mat) 180.1882 181.3038 195.4430 181.9534 182.6366 524.7692   100

其中

adj_mat

是具有1000个节点的图的邻接矩阵。您可以使用任何模型生成。

同样，我有以下用于网络中楔形计数的代码。

wedge_cnt <- function(adj_mat){
  return(sum(adj_mat %*% adj_mat))
}#Wedge count function

但正如我们预期的那样，对于大型网络来说速度要慢得多。任何形式的修改都是值得赞赏的。

Answer 1

我无法使用 getAnywhere 找到该函数的源代码，因为对该函数的一个小修改就会给我 2 星计数，我推测是这样。

就在这里，但我真的不认为这是你想要的......

https://github.com/igraph/igraph/blob/b4a65cfb83f110e0102bdeef70cca42da99f3010/src/properties/triangles.c#L426

是否有任何快速算法可以从图表中找到 2 星或楔形计数？

您可以使用 igraph 的主题计数器。示例：

> set.seed(123)
> g<-sample_gnm(10,20)
> motifs(g,3)
[1] NA NA 39 12

有 39 个二星形和 12 个三角形。请注意，这些被计为诱导子图。

---

您建议使用

sum(A^2)

进行两星计数，其中

A

是邻接矩阵。这有几个问题：

• 应排除对角线。由于

  Tr(A^2)

  是边数的两倍，因此您只需减去它即可。
• 此方法是对每两颗星进行计数，因此我们需要修正

  sum(A^2)/2 - E

  ，其中

  E

  是边缘计数。
• 此方法计算所有子图，而不仅仅是归纳子图。它将计算每个三角形中的 3 个两星。所以我们必须减去三角形的数量。

诱导两星数量的正确公式是

sum(A^2) / 2 - Tr(A^3) / 2 - E

只要您使用稀疏矩阵，这对于大型图来说是一种相当有效的方法。