igraph：有效计算多组顶点之间的边数

Question

我想计算给定图的边计数矩阵，并将该图划分为组。我目前的解决方案不适用于大型图，我想知道是否可以加快计算速度。

我想为此使用

igraph

R 包，因此对于图

G

和两组顶点

set1

，

set2

我目前使用 igraph 计算从一组到另一组的边数

%->%

运算符。

el <- E(G)[set1 %->% set2]
length(el)

我想知道是否有更快的方法可以在

igraph

中本地执行此操作或通过自制一些解决方案（也许使用

Rcpp

）？

示例代码

library(igraph)

# Set up toy graph and partition into two blocks
G <- make_full_graph(20, directed=TRUE)
m <- c(rep(1,10), rep(2,10))

block_edge_counts <- function(G, m){
  # Get list of vertices per group.
  c <- make_clusters(G, m, modularity = FALSE)
  # Calculate matrix of edge counts between blocks.
  E <- sapply(seq_along(c), function(r){
    sapply(seq_along(c), function(s){
      # Iterate over all block pairs
      el <- E(G)[c[[r]] %->% c[[s]]] # list of edges from block r to block s
      length(el) # get number of edges
    })
  })
}

block_edge_counts(G, m)
#>      [,1] [,2]
#> [1,]   90  100
#> [2,]  100   90

基准示例

#> install.packages("bench")

results <- bench::press(
  Nsize = c(10,100,1000),
  {
    G <- make_full_graph(Nsize, directed=TRUE)
    m <- c(rep(1,.5*Nsize), rep(2,.5*Nsize))
    bench::mark(block_edge_counts(G,m))
  }
)
#> Running with:
#>   Nsize
#> 1    10
#> 2   100
#> 3  1000
#> Warning: Some expressions had a GC in every iteration; so filtering is disabled.
results
#> # A tibble: 3 × 7
#>   expression              Nsize      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr>              <dbl> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 block_edge_counts(G, m)    10   1.24ms   1.31ms    752.     39.97KB     12.6
#> 2 block_edge_counts(G, m)   100   3.24ms   3.37ms    284.      4.11MB     32.1
#> 3 block_edge_counts(G, m)  1000 262.73ms 323.61ms      3.29  408.35MB     34.2

---

解决方案

现在我要和

block_edge_counts <- function(graph, partition) {
  CG <- contract(graph, partition)
  E <- as_adjacency_matrix(CG, sparse=FALSE)
}

Answer 1

一种方法是将两个集合收缩为单个顶点，然后计算它们之间的边。

收缩两个集合，获取第一个集合的顶点 ID 1 和第二个集合的顶点 ID 2：

CG <- contract(G, m)

现在数一下

1 -> 2

和

2 -> 1

边：

> count_multiple(CG, get.edge.ids(CG, c(1,2, 2,1)))
[1] 100 100

---

如果您对图进行了完整分区，那么您可以使用

来计算分区内边的分数

modularity(G, m, resolution = 0)

您的示例已完全划分为两个集合，因此您可以获得这两个集合之间的边数

> ecount(G)*(1 - modularity(G, m, resolution = 0))
[1] 200

Answer 2

通过提取图的邻接矩阵并直接使用它，您可以获得更好的结果。

block_edge_counts_adj <- function(G, m) {
  # Get list of vertices per group.
  c <- make_clusters(G, m, modularity = FALSE)
  am <- as_adjacency_matrix(G, sparse=F)
  # Calculate matrix of edge counts between blocks.
  sapply(seq_along(c), function(r){
    sapply(seq_along(c), function(s){
      # Iterate over all block pairs
      sum(am[c[[r]], c[[s]]]) # number of edges from block r to block s
    })
  })
}

sparse=T

的

as_adjacency_matrix

参数在这里至关重要，因为如果没有它，函数将返回一个稀疏矩阵，其计算时间会更长。也许对于稀疏图来说，这在内存使用方面是有益的，但在像您示例中的完整图上，它会导致更长的计算时间。

block_edge_counts_adj2 <- function(G, m) {  # using sparse matrix
  # Get list of vertices per group.
  c <- make_clusters(G, m, modularity = FALSE)
  am <- as_adjacency_matrix(G)
  # Calculate matrix of edge counts between blocks.
  sapply(seq_along(c), function(r){
    sapply(seq_along(c), function(s){
      # Iterate over all block pairs
      sum(am[c[[r]], c[[s]]]) # number of edges from block r to block s
    })
  })
}

results <- bench::press(
  Nsize = c(10, 100, 1000, 3000),
  {
    G <- make_full_graph(Nsize, directed=TRUE)
    m <- c(rep(1, .5*Nsize), rep(2, .5*Nsize))
    bench::mark(block_edge_counts(G, m),
                block_edge_counts_adj(G, m),
                block_edge_counts_adj2(G, m),
                min_iterations=5)
  }
)

results
# A tibble: 12 x 14
#    expression                   Nsize      min   median `itr/sec` mem_alloc `gc/sec` n_itr
#    <bch:expr>                   <dbl> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int>
#  1 block_edge_counts(G, m)         10   2.44ms   2.88ms   301.      39.97KB    2.06    146
#  2 block_edge_counts_adj(G, m)     10   1.43ms   1.61ms   560.        1.8KB    2.05    273
#  3 block_edge_counts_adj2(G, m)    10   3.41ms   3.94ms   233.      14.46KB    2.05    114
#  4 block_edge_counts(G, m)        100   6.26ms    7.2ms   135.       4.11MB    0        68
#  5 block_edge_counts_adj(G, m)    100   2.26ms   2.46ms   376.     208.59KB    2.05    183
#  6 block_edge_counts_adj2(G, m)   100   4.82ms   5.32ms   181.       1.34MB    0        91
#  7 block_edge_counts(G, m)       1000 380.86ms 412.24ms     2.43   408.35MB    3.64      2
#  8 block_edge_counts_adj(G, m)   1000  25.85ms  27.46ms    36.0     15.71MB    2.25     16
#  9 block_edge_counts_adj2(G, m)  1000 114.91ms 133.71ms     7.71   130.09MB    1.93      4
# 10 block_edge_counts(G, m)       3000    3.78s    3.88s     0.260    3.59GB    1.92      5
# 11 block_edge_counts_adj(G, m)   3000 197.01ms 218.48ms     4.47   138.75MB    0.894     5
# 12 block_edge_counts_adj2(G, m)  3000    1.19s    1.25s     0.809    1.14GB    2.10      5