Find / Detect / Enumerate all Cliques or Independent Sets

Question

What are generally best choices for enumerating all k-cliques (or independent sets of size k)? The graphs I am looking at probably won't have more than ~ 100 nodes.

Presently I code in Python with NetworkX, so if you know of any Python packages that could help me that would be fantastic.

Your help is much appreciated!

Answer 1

Here's my implementation of the algorithm described in the above link. I'm giving my implementation for the example described in Fig. 4 in the aforementioned reference but should be adaptable quite easily to whatever you need, in case anyone asks themselves the same question as I did.

Note that the code provided below (hopefully) outputs all cliques (of all sizes k >= 2) in graph G. Output the nodes of your graph for k = 1.

import networkx as nx
from matplotlib import pylab as pl

def greater_neighbors(G, a_node):
    nodes_sorted = sorted(G.nodes())
    a_node_index = nodes_sorted.index(a_node)

    neighbors_of_a_node = []

    for another_node_index, another_node in enumerate(nodes_sorted):
        if another_node_index > a_node_index and another_node in G.neighbors(a_node):
            neighbors_of_a_node.append(another_node)

    return tuple(neighbors_of_a_node)

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'),
               ('f','b'),('f','c'),('f','g'),
               ('g','f'),('g','c'),('g','d'),('g','e')]
pos = {
      'b': (0,4), 'f': (0,0),
      'c': (2,2),
      'a': (4,6),
      'd': (6,2),
      'e': (8,4), 'g': (8,0)
      } 

G.add_edges_from(edges_fig_4)

#pl.figure()
#nx.draw(G, pos=pos)
#pl.show()

# sorted list of nodes in graph
nodes_sorted = sorted(G.nodes())

# starting point: build all 2-clique sublists
clique_sublists = []
for a_node_index, a_node in enumerate(nodes_sorted):
clique_sublist = {}
# sublist base, sb
clique_sublist['sb'] = tuple(a_node)
# common neighbors, cn
clique_sublist['cn'] = greater_neighbors(G, a_node)
clique_sublists.append(clique_sublist)


while clique_sublists:
    a_sublist = clique_sublists.pop(0)
    for node_added in a_sublist['cn']:
        neighbors_of_node_added = greater_neighbors(G, node_added)

        current_sublist_base = a_sublist['sb']+tuple(node_added)
        current_sublist_cn = tuple(sorted(set(neighbors_of_node_added).intersection(a_sublist['cn'])))

        print 'clique: '+str(current_sublist_base)

        for node in current_sublist_cn:
            new_sublist_base = current_sublist_base+tuple(node)
            new_sublist_cn = tuple(sorted(set(current_sublist_cn).intersection(greater_neighbors(G, node))))

            if len(new_sublist_cn) == 0:
                print 'clique: '+str(new_sublist_base)
            elif len(new_sublist_cn) == 1:
                print 'clique: '+str(new_sublist_base)
                print 'clique: '+str(new_sublist_base+new_sublist_cn)
            else:
                print 'candidate sublist: '+str([new_sublist_base, new_sublist_cn])
                clique_sublists.append({'sb': new_sublist_base, 'cn': new_sublist_cn})