4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Are you looking for algorithms or software? $\endgroup$ – Paul Jan 14 '13 at 16:31
  • $\begingroup$ Cheers @Paul, I'm looking for either really. Ideally a Python library but otherwise anything that will get me started would be fantastic. $\endgroup$ – Name Jan 14 '13 at 16:34
  • $\begingroup$ Possibly found an algorithm: ieeexplore.ieee.org/xpl/… $\endgroup$ – Name Jan 14 '13 at 17:12
0
$\begingroup$

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})
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.