4

我很惊讶networkx似乎没有内置函数来做到这一点，但也许我错过了一些使用内置算法来做到这一点的聪明方法？

4

3 回答 3

5

您可以使用以下内置函数之一：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
于 2019-11-09T18:09:29.850 回答
2

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

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

于 2021-03-30T07:12:46.527 回答
1

欢迎来到 SO。

基于这个参考，我认为目前没有现有的功能可以做到这一点。如果你想使用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

编辑：我建议在Michal 的回答 中考虑选项 2

于 2019-11-09T17:48:52.427 回答