查找图中 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...最大度 - 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

非常简单明了的方法是使用 Networkx：

使用 Networkx，您可以通过 nx.cycle_basis(G) 然后选择有3个节点的

cycls_3 = [c for c in nx.cycle_basis(G) if len(c)==3]

，或者你可以通过find_cliques(G) ，然后选择您想要的（有 3 个节点）。派系是图表的一部分，其中所有节点都相互连接，这发生在具有 3 个节点的循环/循环中。

Answer 4

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

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

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

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

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

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

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

Answer 5

我不想听起来很刺耳，但是你试过用谷歌搜索一下吗？第一个链接是一个非常快速的算法：
http://www.mail-archive.com/[email protected]/msg05642.html

然后是关于 ACM 的这篇文章（您可以访问）：
http://portal.acm.org/itation.cfm?id=244866
（如果你没有访问权限，我相信如果你问一下写它的女士，你会得到一份副本。）

另外，我可以想象一种基于派系分解的三角形枚举方法，但我不这样做知道是否在某处描述过。

Answer 6

我正在研究计算无向图上三角形数量的相同问题，wisty 的解决方案在我的情况下效果非常好。我对其进行了一些修改，因此仅计算无向三角形。

    #### function for counting undirected cycles
    def generate_triangles(nodes):
        visited_ids = set() # mark visited node
        for node_a_id in nodes:
            temp_visited = set() # to get undirected triangles
            for node_b_id in nodes[node_a_id]:
                if node_b_id == node_a_id:
                    raise ValueError # to prevent self-loops, if your graph allows self-loops then you don't need this condition
                if node_b_id in visited_ids:
                    continue
                for node_c_id in nodes[node_b_id]:
                    if node_c_id in visited_ids:
                        continue    
                    if node_c_id in temp_visited:
                        continue
                    if node_a_id in nodes[node_c_id]:
                        yield(node_a_id, node_b_id, node_c_id)
                    else:
                        continue
                temp_visited.add(node_b_id)
            visited_ids.add(node_a_id)

当然，你需要使用字典，例如

    #### Test cycles ####

    nodes = {}

    nodes[0] = [1, 2, 3]
    nodes[1] = [0, 2]
    nodes[2] = [0, 1, 3]
    nodes[3] = [1]

    cycles = list(generate_triangles(nodes))
    print cycles

使用Wisty的代码，找到的三角形将是
[(0, 1, 2), (0, 2, 1), (0, 3, 1), (1, 2, 3)]

计算了三角形 (0, 1, 2) 和 (0, 2, 1）作为两个不同的三角形。根据我修改的代码，这些仅算作一个三角形。

我将其与一个相对较小的字典（少于 100 个键）一起使用，每个键平均有 50 个值。

Answer 7

惊讶地发现没有提及 Networkx 三角形函数。我知道它不一定返回形成三角形的节点组，但应该与许多发现自己在此页面上的人非常相关。

nx.triangles(G) # list of how many triangles each node is part of
sum(nx.triangles(G).values())/3 # total number of triangles

返回节点群的另一种方法是......

for u,v,d in G.edges(data=True):
    u_array = adj_m.getrow(u).nonzero()[1] # get lists of all adjacent nodes
    v_array = adj_m.getrow(v).nonzero()[1]
    # find the intersection of the two sets - these are the third node of the triangle
    np.intersect1d(v_array,u_array)

Answer 8

如果您不关心同一三角形以不同顺序的多个副本，则可以使用三元组列表：

from itertools import combinations as combos
[(n,nbr,nbr2) for n in G for nbr, nbr2 in combos(G[n],2) if nbr in G[nbr2]]

这里的逻辑是检查每个节点的每对邻居以查看它们是否连接。 G[n] 是一种迭代或查找邻居的快速方法。

如果你想摆脱重新排序，请将每个三元组变成一个冻结集并制作一组冻结集：

set(frozenset([n,nbr,nbr2]) for n in G for nbr, nbr2 in combos(G[n]) if nbr in G[nbr2])

如果你不喜欢冻结集并想要一个集合列表，那么：

triple_iter = ((n, nbr, nbr2) for n in G for nbr, nbr2 in combos(G[n],2) if nbr in G[nbr2])
triangles = set(frozenset(tri) for tri in triple_iter)
nice_triangles = [set(tri) for tri in triangles]

Answer 9

您需要找到“所有”“三角形”，还是只是“一些”/“任何”？
或者也许您只需要测试特定节点是否是三角形的一部分？

测试很简单 - 给定一个节点 A，是否有任何两个连接的节点 B 和 A。 C 也直接连接。

如果您需要找到所有三角形 - 具体来说，所有 3 个节点组，其中每个节点都与其他两个节点相连 - 那么您需要在一个非常长的运行“foreach”循环中检查每个可能的组。

唯一的优化是确保您不会两次检查同一个“组”，例如，如果您已经测试了 B & 组。 C 与 A 不在一组，则不检查 A 和 A 是否在一个组中。 C与B分在一组。

Answer 10

这是 Ajay M 答案 的更有效版本（我会评论它，但我没有足够的声誉）。

事实上，networkx 的 enumerate_all_cliques 方法将返回图中的所有 cliques，无论其长度如何；因此循环可能会花费很多时间（尤其是对于非常密集的图形）。

此外，一旦为三角形定义了，只需参数化即可概括每个团长度的方法，因此这里有一个函数：

import networkx as nx

def get_cliques_by_length(G, length_clique):
    """ Return the list of all cliques in an undirected graph G with length 
    equal to length_clique. """
    cliques = []
    for c in nx.enumerate_all_cliques(G) :
        if len(c) <= length_clique:
            if len(c) == length_clique:
                cliques.append(c)            
        else:
            return cliques
    # return empty list if nothing is found
    return cliques

要获取三角形，只需使用 get_cliques_by_length(G, 3) 。

警告：此方法仅适用于无向图。 networkx 中未提供有向图中的派系算法

Answer 11

我刚刚发现 nx.edge_disjoint_paths 可以计算包含某些边的三角形。比 nx.enumerate_all_cliques 和 nx.cycle_basis 更快。
它返回源和目标之间的边不相交路径。边不相交路径是不共享任何边的路径。
result-1 是包含某些边或源节点和目标节点之间的三角形的数量。

edge_triangle_dict = {}
for i in g.edges:
    edge_triangle_dict[i] = len(list(nx.edge_disjoint_paths(g, i[0], i[1]))-1)