3

我想k在无向图中找到所有大小的集团。这个问题描述了一个类似的问题；与链接问题中的 OP 不同，我对查找所有派系不感兴趣，只对 size 的派系感兴趣k。

到目前为止，我发现了两种方法。首先是按规模递增的顺序处理所有派系。第二个是计算所有最大派系，获取大小子集n并删除重复项。

每种方法都有缺点并且在某些情况下是不切实际的。有没有更好的方法来找到给定大小的所有派系？

方法 1：按大小递增的顺序遍历列表。

import networkx as nx
from itertools import combinations

# iterate over all cliques in order of increasing size
def find_all_cliques_of_size_k1(g, k):
  for c in nx.algorithms.clique.enumerate_all_cliques(g):
    if len(c) == k:
      yield c
    if len(c) > k:
      break

bad_case_1 = (nx.complete_graph(100), 98)
# find_all_cliques_of_size_k1(*bad_case_1) has to iterate over around 2^100 cliques

方法 2：生成最大派系并找到大小的唯一子集k。

# find all maximal cliques, take subsets and size k and remove duplicates
def find_all_cliques_of_size_k2(g, k):
  cliques = set()
  for c in nx.algorithms.clique.find_cliques(g):
    cliques.update(map(frozenset, combinations(c, k)))
  return [list(c) for c in cliques]

bad_case_2 = (nx.random_graphs.erdos_renyi_graph(100, 0.9), 2)
# find_all_cliques_of_size_k2(*bad_case_2) considers a huge number of maximal cliques
4

0 回答 0