CODEWITHSUNDEEP
networkx
0x90
0x90

Reputation: 40982

What does number_of_cliques and max_clique calculate?

I am not sure what max_clique does and what number_of_cliques does

from networkx.algorithms.approximation import clique
clique.max_clique(G)

and 

clique.number_of_cliques(G)

Not clear from the doc

Upvotes: 0

Views: 1381

Answers (2)

Mohammad Fatehi
Mohammad Fatehi

Reputation: 32

This is a sample:

import networkx as nx
G1 = nx.Graph()
edges = [(1, 2), (2, 3), (1, 3), (3, 4), (3, 0),(1, 4),(4, 2)]
G1.add_edges_from(edges)
nx.draw_networkx(G1)

enter image description here

res = nx.find_cliques(G1)
cliques = [item for item in res]
cliques = sorted(cliques, key=lambda item: -len(item))
for item in cliques:
    print(item)

enter image description here

max_clique(G1)

enter image description here

Upvotes: 0

Joel
Joel

Reputation: 23827

max_clique finds what is hopefully the largest (or a largest) clique in the graph. It will return a set of nodes which form a clique, with a reasonable likelihood that there is no larger clique in the network. It is approximate because the calculation itself is expensive (NP-complete). https://en.wikipedia.org/wiki/Clique_problem

number_of_cliques (at least in networkx v2.2) returns a dict whose keys are the nodes of the graphs and whose values are the number of maximal cliques that the given node is in. A maximal clique means that if 0-1, 0-2, 1-2 and 0-3 are edges, then the maximal cliques of node 0 are {0,1,2} and {0,3}. The clique {0,1} does not count because it is contained in a larger clique. Nodes 1 and 2 each have a single maximal clique {0,1,2} and node 3 has a single maximal clique {0,3}. So number_of_cliques returns the dict {0:2, 1:1, 2:1, 3:1}.

Upvotes: 2

Related Questions