Skip to content

Finding all triangles in a graph

2 messages · Taral, Albyn Jones

Taral
# 
I have the adjacency matrix of a graph. I'm trying to find all
triangles (embeddings of C_3). This doesn't work:

index = function(l) seq(l)[l]
pairs = do.call(rbind, lapply(seq(nrow(adj)), function(x) cbind(x,
index(adj[x,]))))
triangles = do.call(rbind, apply(pairs, 1, function(x) cbind(x,
index(adj[x[1],] & adj[x[2],]))))

I'm absolutely certain I've gone down the wrong path here. O great R
gurus, your guidance would be most welcome.
Albyn Jones
# 
Taral

The general problem of finding subgraphs with a given structure ("motifs")
is hard (ie computationally expensive).  There is some literature...

have you looked at the package igraph, function graph.motifs()?

albyn

Quoting Taral <taralx at gmail.com>: