Finding triangles in a k-NN graph

Hello,

I have a simple undirected graph represented by an adjacency matrix where (i,j)=1 if nodes i and j are connected, else (i,j)=0. I'd like to find all possible loops of three edges (triangles!) in the graph. Something like: node 1 to node 14, 14 to 50, and 50 to 1 (assuming node 1 is connected to 14, 14 to 50, and 50 to 1).

Are there any matlab tools available to do this?

Answer 1

[KSSV]

doc delaunay

[JohnDapper]

Hi Siva,

I don't think this is what I'm looking for. A naive algorithm to do what I want would be to start with a node, look at a neighbour, and then look at the neighbours of the neighbour -- if any of the latter connect to the original node, then a triangle has been found. Repeat for all nodes and neighbours. This would do the trick, but I'm wondering if something faster is available in matlab.

[KSSV]

You can search the neighbors using knnsearch....But what you said, the same thing Delaunay Triangulation does.