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!
You can count cycles using igraph's subisomorphism functions. For example, counting 5-cycles:
set.seed(123)
g <- sample_gnm(10,30)
> count_subgraph_isomorphisms(make_ring(5), g)
[1] 3500
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.
> automorphisms(make_ring(5))$group_size
[1] "10"
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.
cycle5_per_motif <- sapply(0:33, function (c) count_subgraph_isomorphisms(make_ring(5), graph_from_isomorphism_class(5, c, directed=F)) / 10)
With this information, we can run the motif finder and compute the final cycle count:
> sum(motifs(g, 5) * cycle5_per_motif, na.rm=T)
[1] 350
This is much faster than using count_subgraph_isomorphisms, but it only works up to 6-cycles at this moment.