在图中查找3个节点(或三角形)的循环

Question

我正在使用复杂的网络.我想找到一组节点,它们在给定的图形中形成3个节点(或三角形)的循环.由于我的图形包含大约百万个边缘,因此使用简单的迭代解决方案(多个"for"循环)效率不高.

我正在使用python进行编程,如果这些是用于处理这些问题的内置模块,请告诉我.

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

Answer 1

假设它是一个无向图，答案在于python的networkx库。如果您只需要计算三角形，请使用：

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

但是如果你需要知道具有三角形（三元）关系的边列表，使用

all_cliques= nx.enumerate_all_cliques(g)

这会给你所有的派系 (k=1,2,3...max degree - 1)

所以，只过滤三角形，即 k=3，

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

triad_cliques 将给出一个只有三角形的边列表。

Answer 2

一百万条边非常小。除非你做了数千次，否则只需使用一个简单的实现。

我假设您有一个 node_ids 字典，它指向一系列邻居，并且该图是有向的。

例如：

nodes = {}
nodes[0] = 1,2
nodes[1] = tuple() # empty tuple
nodes[2] = 1

我的解决方案：

def generate_triangles(nodes):
    """Generate triangles. Weed out duplicates."""
    visited_ids = set() # remember the nodes that we have tested already
    for node_a_id in nodes:
        for node_b_id in nodes[node_a_id]:
            if nod_b_id == node_a_id:
                raise ValueError # nodes shouldn't point to themselves
            if node_b_id in visited_ids:
                continue # we should have already found b->a->??->b
            for node_c_id in nodes[node_b_id]:
                if node_c_id in visited_ids:
                    continue # we should have already found c->a->b->c
                if node_a_id in nodes[node_c_id]:
                    yield(node_a_id, node_b_id, node_c_id)
        visited_ids.add(node_a_id) # don't search a - we already have all those cycles

检查性能：

from random import randint
n = 1000000
node_list = range(n)
nodes = {}
for node_id in node_list:
    node = tuple()
    for i in range(randint(0,10)): # add up to 10 neighbors
        try:
            neighbor_id = node_list[node_id+randint(-5,5)] # pick a nearby node
        except:
            continue 
        if not neighbor_id in node:
            node = node + (neighbor_id,)
    nodes[node_id] = node

cycles = list(generate_triangles(nodes))
print len(cycles)

当我尝试它时，构建随机图比计算周期花费的时间更长。

不过，您可能想对其进行测试；) 我不保证它是正确的。

您还可以查看 networkx，它是大型 Python 图形库。

Answer 3

尽管效率不高，但您可能想要实现一个解决方案，因此请使用循环。编写一个测试，以便您了解需要多长时间。

然后，当您尝试新方法时，您可以做两件事：1）确保答案保持不变。2）看看有什么改进。

拥有更快的算法而错过一些东西可能会比拥有更慢的算法更糟糕。

一旦进行了慢速测试，您就可以看看是否可以并行执行此操作，并查看性能提升情况。

然后，您可以看看是否可以标记所有少于 3 个顶点的节点。

理想情况下，您可能希望首先将其缩小到 100 左右，这样您就可以绘制它，并以图形方式查看发生了什么。

有时，您的大脑会看到一种在查看算法时并不那么明显的模式。