在图中查找 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...max degree - 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屋！