rigraphisomorphism

How to return only one triangle from the set of isomorphic triangles?


The original question is here.

How to calcultate a probability that a graph with 6 vertices and 5 edges has a triangle?

I would like to make a simulation. I going to create the triangle graph then generate the 1,000 random graphs with n=6 vertecies and m=5 edges, and find the distibutions of triangles.

Now I created a g graph with one triangle, the subgraph_isomorphisms() function returns 6 isomorphic triangles. Then I used the unique() function in order to find one triangle. But the result is 6.

library(igraph) 

g          <- graph_from_literal( A--B, B--C, C--A, B--D, D--E, E--F)
triangle   <- graph_from_literal( A--B, B--C, C--A) 

ntriangles <- 0

iso <- subgraph_isomorphisms(triangle, g) 

motifs <- lapply(iso, function (x) { induced_subgraph(g, x) }) 
ntriangles <- length(unique(motifs))  
ntriangles

Question. How to return only one triangle from the set of isomorphic triangles?


Solution

  • One solution could be to aggregate the edgelist of each motif into a data.frame and use dplyr's distinct to filter the unique values:

    library(dplyr)
    edgelist <- do.call(rbind,
                        lapply(1:length(motifs), function(x) get.edgelist(motifs[[x]])))
    edgelist <- data.frame(edgelist) %>% distinct() %>% as.matrix()
    graph_from_edgelist(edgelist, directed = F)
    

    This returns:

    > graph_from_edgelist(edgelist, directed = F)
    IGRAPH e275587 UN-- 3 3 -- 
    + attr: name (v/c)
    + edges from e275587 (vertex names):
    [1] A--B A--C B--C
    

    EDIT Here is another approach, which is shorter and closer to the one OP proposed:

    motifs <- lapply(iso, function (x) { get.edgelist(induced_subgraph(g, x)) })   
    ntriangles <- length(unique(motifs))  
    ntriangles
    

    Here I simply extract the edgelist, which contains the vertices. Without the unique graph_id and the other information stored in the igraph-object, unique will return the following:

    > length(unique(motifs))
    [1] 1