计算二分 R igraph 中的 4 和 6 周期
我想计算四循环的数量和二分部分中的六循环的数量。 - 全循环“> rigraph找到所有周期，我想出了这个解决方案：
> 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
它有效，但是对于稍大的图，它是不切实际的，因为可能有很多数倍的循环来枚举。有没有一种方法可以更有效地进行此操作，也许可以利用该图是两部分的事实？谢谢！
I want to count the number of four-cycles and the number of six-cycles in a bipartite igraph in R. Adapting the code in r igraph find all cycles, I've come up with this solution:
> 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
It works, but is impractical for even slightly larger graphs because there are potentially exponentially many cycles to enumerate. Is there a way to do this more efficiently, maybe exploiting the fact that the graph is bipartite? Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以使用 igraph 的亚同构函数来计算周期。例如，计算 5 个周期：
这会将 5 个周期多计数 10，因为每个 5 个周期有 10 个自同构。一般来说，n 圈有 2n 个自同构。因此真正的计数是 350。
它也会很慢。
在新发布的 igraph 1.3.0 中，我们可以使用主题查找器功能，该功能现已扩展为可处理 5 和 6 顶点无向图。
由于基序是诱导子图，但我们正在寻找所有循环，而不仅仅是诱导循环，因此我们首先需要检查每个 5-基序有多少个 5-循环。请注意，5 个顶点上有 34 个非同构图形，您可以在 OEIS 中查找。另请注意像以前一样除以 10，以避免计数过多。
有了这些信息，我们就可以运行主题查找器并计算最终的循环计数：
这比使用 count_subgraph_isomorphisms 快得多，但目前最多只能处理 6 个循环。
You can count cycles using igraph's subisomorphism functions. For example, counting 5-cycles:
This overcounts 5-cycles by 10 as each 5-cycle has 10 automorphisms. Generally, n-cycles have 2n automorphisms. Thus the true count is 350.
It will also be quite slow.
With the newly released igraph 1.3.0, we can use the motif finder functionality, which has now been extended to work with 5 and 6 vertex undirected graphs.
Since motifs are induced subgraphs, but we are looking for all cycles, not just induced ones, we first need to check how many 5-cycles each 5-motif has. Note that there are 34 non-isomorphic graphics on 5 vertices, as you can look up e.g. in OEIS. Notice also the division by 10, as before, to avoid overcounting.
With this information, we can run the motif finder and compute the final cycle count:
This is much faster than using
count_subgraph_isomorphisms, but it only works up to 6-cycles at this moment.