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

debugcn 发表于 Dev

金虫

我很惊讶networkx似乎没有内置函数来执行此操作，但是也许我错过了一些使用内置算法来执行此操作的聪明方法？

米哈尔·扬科（Michal Yanko）

您可以使用以下内置函数之一：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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。