While attempting to write out an algorithm to find all triangles (a->b->c->a) from an adjacency matrix, I stumbled across functionality in the igraph library for R that makes this process trivial to implement for any pattern.

library(igraph) #create an arbitrary graph adjacency.graph <- erdos.renyi.game(100,0.1,directed=TRUE) #create the pattern to match triangle <- graph.ring(3,directed=TRUE) #find all matches adjacency.triangles <- graph.get.subisomorphisms.vf2(adjacency.graph,triangle) #define default formatting adjacency.graph.colored<-adjacency.graph V(adjacency.graph.colored)$shape = "none" V(adjacency.graph.colored)$label.font = 0.5 E(adjacency.graph.colored)$color="black" #map matches back to the original graph for (vec in adjacency.triangles) { V(adjacency.graph.colored)[c(vec)+1]$label.color="dark red" E(adjacency.graph.colored,path=c(vec,vec[1])+1)$color="red" } plot(adjacency.graph.colored,edge.arrow.size=0.2) |

Of particular note is the fact that the heavy lifting of this script is all done using a single command (graph.get.subisomorphisms.vf2()). Everything else in the script functions as a wrapper to pull data in or present the results.

Be cautious when executing the above script for large data sets. Since we are interested in triangles, the complexity of this algorithm scales with O(n^3) where n is the number of edges. On my machine, ~1000 edges took less than a second to process, but ~50000 edges took 35 seconds to process. Looking for more complex shapes would cause the complexity to further increase.

Comments (0)Trackbacks (0)