在图中查找3个节点（或三角形）的周期 [英] Finding cycle of 3 nodes ( or triangles) in a graph

问题描述

我正在使用复杂的网络。我想找到一组节点，这些节点在给定图中形成3个节点（或三角形）的循环。由于我的图形包含大约一百万条边，因此使用简单的迭代解决方案（多个 for循环）不是很有效。

I am working with complex networks. I want to find group of nodes which forms a cycle of 3 nodes (or triangles) in a given graph. As my graph contains about million edges, using a simple iterative solution (multiple "for" loop) is not very efficient.

我正在使用python进行编程，如果这些是处理这些问题的一些内置模块，请让我知道。

I am using python for my programming, if these is some inbuilt modules for handling these problems, please let me know.

如果有人知道可以用于在图形中查找三角形的任何算法，请回复。

If someone knows any algorithm which can be used for finding triangles in graphs, kindly reply back.

推荐答案

假设其为无向图，则答案在于python的networkx库。
如果只需要计算三角形，请使用：

Assuming its an undirected graph, the answer lies in networkx library of python. if you just need to count triangles, use:

import networkx as nx
tri=nx.triangles(g)

但是如果您需要了解具有三角形（三重关系）关系的边列表，请使用

But if you need to know the edge list with triangle (triadic) relationship, use

all_cliques= nx.enumerate_all_cliques(g)

这将为您提供所有群体（k = 1,2,3 ...最大学位-1）

This will give you all cliques (k=1,2,3...max degree - 1)

仅过滤三角形，即k = 3，

So, to filter just triangles i.e k=3,

triad_cliques=[x for x in all_cliques if len(x)==3 ]

triad_cliques将仅给出三角形的边列表。

The triad_cliques will give a edge list with only triangles.

这篇关于在图中查找3个节点（或三角形）的周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！