CODEWITHSUNDEEP
pythonnetworkx
Peterxwl
Peterxwl

Reputation: 1123

Why the result is incorrect to find 3-cliques using networkx in Python?

I am trying to find all 3-cliques using networkx's find_cliques method. However, there should be far more than 2 as the result shows. Please help me to figure out why.

import networkx as nx
G = nx.Graph()
edges_fig_4 = [('a','b'),('a','c'),('a','d'),('a','e'),
           ('b','c'),('b','d'),('b','e'),
           ('c','d'),('c','e'),
           ('d','e'),('e','d'),
           ('f','b'),('f','c'),('f','g'),
           ('g','f'),('g','c'),('g','d'),('g','e')]
G.add_edges_from(edges_fig_4)
cliques = nx.find_cliques(G)
cliques3 = [clq for clq in cliques if 3<=len(clq)<= 3]

print(cliques3)

Upvotes: 2

Views: 2701

Answers (1)

Haochen Wu
Haochen Wu

Reputation: 1823

According to the document, find_cliques returns all maximal cliques. In your case there are cliques with size greater than 3 (abcde)(cdeg) and you will need to also have all possible 3-combination in that bigger clique. This is because each sub-clique of a clique is also a clique but it's not maximal.

EDIT: You will also need use set to avoid overlapped cliques.

Use the following code:

import itertools
cliques3 = set(sum([list(itertools.combinations(set(clq), 3)) for clq in cliques if len(clq)>=3],[]))

Alternatively, using enumerate_all_cliques will also give cliques of size (cardinality) k = 1, 2, 3, ..., maxDegree - 1. See the document here: http://networkx.github.io/documentation/development/reference/generated/networkx.algorithms.clique.enumerate_all_cliques.html

Upvotes: 5

Related Questions