在 python 中使用 networkx 计算无向图中大小为 k 的派系的最佳方法是什么？

Question

我很惊讶 networkx 似乎没有内置函数来执行此操作，但也许我缺少一些使用内置算法执行此操作的巧妙方法？

Answer 1

欢迎来到 SO。

基于这个reference，我认为目前没有现成的功能可以做到这一点。如果你想使用 nx 函数，你可以这样做：

def count_k_cliques(G, k):
    k_cliques_count = 0
    for clique in nx.enumerate_all_cliques(G): 
        if len(clique) > k: 
            break 
        elif len(clique) == k: 
            k_cliques_count += 1
    return k_cliques_count

编辑： 我建议考虑

中的选项 2

Answer 2

您可以使用以下内置函数之一：enumerate_all_cliques or find_cliques 以获取无向图中的所有 k-clique。

这些函数之间的区别是 enumerate_all_cliques 遍历了所有可能的派系，而 find_cliques 仅遍历了 maximal 派系。我们最终会看到它影响了运行时间。

选项 1 使用 enumerate_all_cliques:

import networkx as nx

def enumerate_all_cliques_size_k(G, k):
    i = 0
    for clique in nx.enumerate_all_cliques(G):
        if len(clique) == k:
            i += 1
        elif len(clique) > k:
            return i
    return i

选项 2 使用 find_cliques:

import networkx as nx
import itertools

def find_cliques_size_k(G, k):
    i = 0
    for clique in nx.find_cliques(G):
        if len(clique) == k:
            i += 1
        elif len(clique) > k:
            i += len(list(itertools.combinations(clique, k)))
    return i

第一个选项更直接，但运行时间有问题，因为我们遍历了最大团的所有可能子集，即使最大团大小小于 k。我们可以看到 enumerate_all_cliques_size_k 在大小为 20 的完整图上需要 10 倍的时间才能达到运行：

G = nx.complete_graph(20)


@timing
def test_enumerate_all_cliques_size_k(G,k):
    print(enumerate_all_cliques_size_k(G, k))

@timing
def test_find_cliques_size_k(G, k):
    print(find_cliques_size_k(G, k))

test_enumerate_all_cliques_size_k(G,5)
test_find_cliques_size_k(G,5)

# --------------------Result-----------------------

15504
test_enumerate_all_cliques_size_k function took 616.645 ms
15504
test_find_cliques_size_k function took 56.967 ms

Answer 3

使用 find_cliques 函数时，您需要仔细考虑所有可能性 (itertools.combinations) - 在某些情况下，您会多次计算同一个集团。例如，如果您有一个包含六个节点的图（我们将它们命名为 A-G）。其中四个全连接（A-D），E连接A-D，G也连接A-D（但E不连接G）。在这种情况下，您有两个共享 4 个节点（A、B、C、D、E 和 A、B、C、D、G）的 5 团。现在假设您要在这个建议的 garph 中寻找 4-cliques，通过使用 find_cliques 您将遍历两个 5-cliques，在每个 5-cliques 中，您将计算每个 4-cliques，其中包括4-clique A,B,C,D，所以会算两次(!).

这里是建议函数的一个版本，它通过使用 set 解决了这个问题，因此您只需对每个 clique 计数一次：

def find_cliques_size_k(G, k):
    all_cliques = set()
    for clique in nx.find_cliques(G):
        if len(clique) == k:
            all_cliques.add(tuple(sorted(clique)))
        elif len(clique) > k:
            for mini_clique in itertools.combinations(clique, k):
                all_cliques.add(tuple(sorted(mini_clique)))
    return len(all_cliques)

（如果你想要派系本身，你可以 return 'all_cliques' 本身）

在 python 中使用 networkx 计算无向图中大小为 k 的派系的最佳方法是什么？

What is the best way to count the cliques of size k in an undirected graph using networkx in python?

python

graph-theory

clique-problem

networkx