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

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