计算二分 R igraph 中的 4 和 6 周期

Question

我想计算 R 中二分图的四循环数和六循环数。调整中的代码，我想出了这个解决方案：

> set.seed(1)
> library(igraph)
> G <- bipartite.random.game(10,10,p=.5)  #A random bipartite
> 
> cycles <- NULL  #List all cycles up to length 6 (2-cycles, 4-cycles, and 6-cycles)
> for(v1 in V(G)) {for(v2 in neighbors(G, v1)) {cycles <- c(cycles, lapply(all_simple_paths(G, v2, v1, cutoff = 5), function(p) c(v1,p)))}}
> fourcycles <- cycles[which(sapply(cycles, length) == 5)]  #Just four-cycles
> fourcycles <- fourcycles[sapply(fourcycles, min) == sapply(fourcycles, `[`, 1)]  #Unique four-cycles
> length(fourcycles)  #Number of four-cycles
[1] 406
> 
> sixcycles <- cycles[which(sapply(cycles, length) == 7)]  #Just six-cycles
> sixcycles <- sixcycles[sapply(sixcycles, min) == sapply(sixcycles, `[`, 1)]  #Unique six-cycles
> length(sixcycles)  #Number of six-cycles
[1] 5490

它有效，但对于稍微大一点的图来说是不切实际的，因为要枚举的循环可能呈指数级增长。有没有办法更有效地做到这一点，也许是利用图是二分的这一事实？谢谢！

Answer 1

您可以使用 igraph 的子同构函数计算循环数。例如，计算 5 个周期：

set.seed(123)
g <- sample_gnm(10,30)

> count_subgraph_isomorphisms(make_ring(5), g)
[1] 3500

由于每个 5 循环有 10 个自同构，因此 5 循环多计数 10。通常，n-cycles 有 2n 个自同构。因此真正的计数是 350.

> automorphisms(make_ring(5))$group_size
[1] "10"

也会很慢

在新发布的 igraph 1.3.0 中，我们可以使用 motif finder 功能，该功能现已扩展为可处理 5 和 6 顶点无向图。

由于基序是诱导的子图，但我们正在寻找所有循环，而不仅仅是诱导的循环，我们首先需要检查每个 5-基序有多少个 5-循环。注意在5个顶点上有34个non-isomorphic个图形，如you can look up e.g. in OEIS。还要注意像以前一样除以 10，以避免多算。

cycle5_per_motif <- sapply(0:33, function (c) count_subgraph_isomorphisms(make_ring(5), graph_from_isomorphism_class(5, c, directed=F)) / 10)

根据这些信息，我们可以运行基序查找器并计算最终循环计数：

> sum(motifs(g, 5) * cycle5_per_motif, na.rm=T)
[1] 350

这比使用 count_subgraph_isomorphisms 快得多，但目前最多只能使用 6 个周期。

计算二分 R igraph 中的 4 和 6 周期

Counting 4 and 6-cycles in bipartite R igraph

r

graph-theory

cycle

igraph