Finding maximal cliques and removing nodes?

Question

I am trying to find maximal cliques for a set of items.

Currently I am using networkx library of python and using find_cliques() function to find all the maximal cliques as below:

import newtworkx as nx

G = nx.Graph()
E = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [2,6], [2,5], [5,6]]

G.add_edges_from(E)
#G.edges()

lst = list(nx.find_cliques(G))
lst

Out [] : [[2, 1, 3, 4], [2, 5, 6]]

But what I am actually expecting is to find maximal cliques and then remove the nodes which were in the maximal clique graph, and then again find maximal clique out of the nodes left after previous removal.

For the above example, I am expecting to get [2, 1, 3, 4] and then remove these nodes, so only 5 and 6 would be left, which will be another clique [5, 6] .

Update

We can use G.remove_node(), it removes the node as well as all the adjacent edges as expected.

G = nx.Graph()
E = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [2,6], [2,5], [5,6], [3,5], [5,7]]
G.add_edges_from(E)

list1 = list(nx.find_cliques(G))
#list1   gives [[2, 3, 1, 4], [2, 3, 5], [2, 6, 5], [7, 5]]

n = nx.number_of_nodes(G)
#n

[G.remove_node(nd) for nd in list1[0]]
list2 = list(nx.find_cliques(G))
#list2    gives [[5, 6], [5, 7]]

[G.remove_node(nd) for nd in list2[0]]
list3 = list(nx.find_cliques(G))
#list3    gives [[7]]

But every time the nodes are removed, new maximal cliques are found and stored in a new list and so on. How can it be run in the while loop until there is no edge left in graph G i.e number of nodes is 0 or 1.

Readable

Slight confusion: as I understand, removing [2, 1, 3, 4] would still leave [5, 6], which is a technically a clique. – Supraliminal

@Supraliminal I am sorry, my bad. Have edited that part. – Readable

How about [G.remove_node(nd) for nd in lst[0]] to remove the nodes? Following this, another call of list(nx.find_cliques(G)) returns [[5, 6]] for your example data, as expected. – Supraliminal

@Supraliminal Yeah something like this, but with removing node, it should also remove all the edges that are contains either of the nodes from the list of nodes I want to remove i.e [2, 1, 3, 4], so it will remove all the edges other than [5,6] and then it will return [5,6] as another clique. Though above for loop returns None – Readable

I think this is exactly what happens here. From the docstring of Graph.remove_node: "Removes the node n and all adjacent edges." – Supraliminal

The above loop returns None but it deletes the nodes (and corresponding edges) from the graph G. When you call list(nx.find_cliques(G)) again after the above loop, it returns [[5, 6]]. – Supraliminal

@WholsJack Yes, it's working as expected. Thank you. But my actual data has much more cliques, so how can I keep my loop running again and again until no edge is left i.e no 0 or 1 node is left – Readable

Answer 1

You can use G.remove_node to remove the nodes (and the associated edges) from your graph.

How to remove all nodes of the first clique:

lst = list(nx.find_cliques(G))
[G.remove_node(nd) for nd in lst[0]]

To repeatedly remove the nodes of the first clique, until no cliques are left:

lst = list(nx.find_cliques(G))
while len(lst) > 0:
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

Note that this is not the same as removing all nodes that are in any maximal clique at each step, which would be:

lst = list(nx.find_cliques(G))
while len(lst) > 0:

    # This flattens the list of cliques into one list. `set` reduces to unique values.
    flattened = set([nd for cl in lst for nd in cl])

    [G.remove_node(nd) for nd in flattened]
    lst = list(nx.find_cliques(G))

Finally, if there is a certain order in which you would like to remove cliques (e.g. the maximum clique first), you could do this by sorting lst accordingly:

lst = list(nx.find_cliques(G))
while len(lst) > 0:
    lst.sort(key=len, reverse=True)       # Sort maximum clique to the front
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

Edit: for completeness sake, here's how one could store the cliques before deleting them (as per your comment, @Ankie):

out = []
lst = list(nx.find_cliques(G))
while len(lst) > 0:
    out.append(lst[0])
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

As an additional note it should be pointed out that these operations basically 'destroy' graph G. If the graph is needed again later on and takes a long time to construct, it makes sense to work on a copy of the graph so that the original is preserved. A copy can be made like this:

G2 = G.copy()

Supraliminal

@WholsJack Thank you, I figured out the While loop, storing the maximal cliques before deleting them i.e. lst[0] was little confusing. For that we can add a list say a1 which stores lst[0], just after the while statement, and then keep appending it. – Readable