Finding triangles in a k-NN graph

2 次查看（过去 30 天）
JohnDapper
JohnDapper 2016-6-28
评论： 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?

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

回答（1 个）

KSSV
KSSV 2016-6-29
doc delaunay
  2 个评论
JohnDapper
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.
KSSV
KSSV 2016-6-29
You can search the neighbors using knnsearch....But what you said, the same thing Delaunay Triangulation does.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by