CODEWITHSUNDEEP
rigraph
Alex R.
Alex R.

Reputation: 1437

igraph finding all subgraphs of specified shape

I'm interested in finding all "V" subgraphs in a graph, i.e. all triples of vertices that would become triangles if you add an extra edge. Is there an efficient way of doing this with R's version of igraph?

Upvotes: 0

Views: 610

Answers (1)

paqmo
paqmo

Reputation: 3739

This is possible in the sna package; not sure if it is possible in igraph. In sna, the triad.classify will tell you the type of triad given any three vertices. To enumerate them all, you need to find all combinations of three vertices and pass this to triad.classify. Then, create a data frame where each row gives the triad and its classification. Then subset to the triads you care about. This will take a while if you have a lot of vertices! You can convert from igraph to network object using intergraph.

Here's an example using a random graph:

library(sna); library(igraph); library(intergraph)
g <- sample_gnp(25,0.25, directed = T)
g <- asNetwork(g)
triads <- combn(1:network.size(g),3, simplify = F)
triad_census <- lapply(1:length(triads), 
                       function(x) triad.classify(g,tri=triads[[x]]))
triads <- data.frame(matrix(unlist(triads), nrow=length(triads), byrow=T),
                     triad = unlist(triad_census))
triads <- triads[which(triads$triad == "021D" | 
                       triads$triad == "021U" | 
                       triads$triad == "021C" |
                       triads$triad == "111D" |
                       triads$triad == "111U" |
                       triads$triad == "201"),]

head(triads)
   X1 X2 X3 triad
3   1  2  5  021C
4   1  2  6  111U
6   1  2  8  021U
8   1  2 10  021C
10  1  2 12  021C
12  1  2 14  021U

Upvotes: 2

Related Questions