I would like to find all cliques of size k in an undirected graph. A similar problem is described in this question; unlike the OP in linked question, I am not interested in finding all cliques, only those of size k.
I found two approaches so far. The first is to process all cliques in order of increasing size. The second is to compute all maximal cliques, take subsets of size n and remove duplicates.
Each method has drawbacks and is impractical in some cases. Is there a better way to find all cliques of a given size?
Approach 1: Iterate over lists in order of increasing size.
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
Approach 2: Generate maximal cliques & find unique subsets of size 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
