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

Question

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

Answer 1

您可以使用以下内置函数之一:enumerate_all_cliques或 find_cliques为了得到无向图中的所有 k-clique。

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

选项 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