I'm looking for motifs of size 5 in graphs with less than 5000 nodes and less than 10000 edges. (everything uncolored)
To do this I use function provided in igraph library for R subgraph_isomorphisms using method vf2 (see example below). I use adjacency matrix to generate subgraph and edgelist to generate the graph itself.
A lot of isomorphic subgraphs that I find have extra edges. Is there any way to only find subgraphs with exact given structure? Looking for answers using igraph or any other library in R
See reproducible example below (looking at this example is way easier if you just draw graph given by this adjacency matrix on a piece of paper)
library(igraph)
subgraph <- matrix(
data = c(0, 1,
1, 0), ncol = 2)
graph <- matrix(
data = c(0, 1, 0, 0,
1, 1, 0, 1,
1, 0, 0, 1,
0, 0, 1, 0), ncol = 4)
subgraph <- graph_from_adjacency_matrix(subgraph, mode = "directed", weighted = T, diag = T)
graph <- graph_from_adjacency_matrix(graph, mode = "directed", weighted = T, diag = T)
subgraph_isomorphisms(subgraph, graph, method = "vf2")
Output gives you two pairs of (1,2) and (3,4), when in fact adjacency matrix of (1,2) looks like
(0 1)
(1 1)
Which is different from the one we were looking for
The answer to this question is in definitions of what I'm looking for and what I'm finding.
What I was looking for was network motifs of size 5. When I'm looking for network motifs from the graph theory perspective it means that I'm looking for induced subgraphs with given adjacency matrix.
What this function does is it finds subgraphs of a graph that are isomorphic to a given graph. The difference is I was looking for induced subgraph, whereas the function just gives subgraphs, so extra edges are allowed.
That is exactly the problem that I was experiencing. To deal with it I ended up just comparing adjacency matrix of subgraphs that I found with those of the motif. Hope it will be helpful to someone.