Finding triangles in a k-NN graph

Question

JohnDapper 2016-6-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/292806-finding-triangles-in-a-k-nn-graph

评论： KSSV 2016-6-29

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?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

KSSV 2016-6-29

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/292806-finding-triangles-in-a-k-nn-graph#answer_227088

doc delaunay

2 个评论
显示无隐藏无

JohnDapper 2016-6-29

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.