python - 在图中查找 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

非常简单明了的方法是使用 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

我不想听起来很苛刻，但你试过用谷歌搜索吗？第一个链接是一个非常快速的算法：http: //www.mail-archive.com/algogeeks@googlegroups.com/msg05642.html

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

另外，我可以想象一个基于团分解的三角形枚举方法，但我不知道它是否在某处描述过。

Answer 5

我正在研究在无向图上计算三角形数量的相同问题，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 6

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

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

拥有一个更快的算法会遗漏一些东西可能会比拥有一个更慢的算法更糟糕。

进行慢速测试后，您可以查看是否可以并行执行此操作，并查看性能提升是多少。

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

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

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

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

如果您不关心同一个三角形以不同顺序的多个副本，那么 3-tuples 列表可以工作：

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]是一种快速迭代或查找邻居的方法。

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

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

如果您不喜欢frozenset 并且想要一个集合列表，那么：

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 和 C 也直接连接。

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

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

Answer 10

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

确实，该enumerate_all_cliques方法networkx将返回图中的所有派系，无论它们的长度如何；因此循环它可能需要很多时间（尤其是对于非常密集的图形）。

此外，一旦为三角形定义，它只是一个参数化的问题来概括每个团长度的方法，所以这里有一个函数：

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)