``````

In [1]:

import clique_detection as cd

``````
``````

In [2]:

``````

This loads the large dolphin social network into a graph \$G\$.

``````

In [3]:

bound = cd.bound_clique_size(graph)

``````

Since this bound is small enough, one could check all 7-membered or smaller subgraphs of the graph \$G\$ to see if they were complete and get a clique. But one can do better, presumably.

``````

In [4]:

clique_size = 7

``````
``````

In [5]:

valid_nodes = cd.find_possible_clique_member_nodes(clique_size, graph)

``````
``````

In [6]:

print(cd.get_cliques(clique_size, valid_nodes, graph))

``````
``````

[]

``````
``````

In [7]:

print(cd.find_maximum_clique(graph))

``````
``````

[(6, 9, 13, 17, 57), (18, 21, 29, 45, 51), (18, 24, 29, 45, 51)]

``````

This was a terrible idea. Should have gone with Bronn-Kerbosch, which finds all maximal cliques. It works by starting off with 2-cliques, and expanding them, until no more cliques can be expanded. Why didn't I think of that?

Let's try Bronn-Kerbosch along with the naive bound on maximal clique size.

``````

In [8]:

``````
``````

In [9]:

small_clique = (0,1)

``````
``````

In [10]:

print(cd.get_clique_extensions(small_clique, graph2))

``````
``````

[(0, 1, 2)]

``````
``````

In [11]:

print(cd.get_two_cliques(graph2))

``````
``````

[(0, 1), (0, 2), (0, 3), (0, 5), (1, 2), (1, 4), (1, 6), (2, 3), (2, 4), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]

``````
``````

In [12]:

cd.find_maximal_cliques(graph)

``````
``````

Out[12]:

{(6, 9, 13, 17, 57), (18, 21, 29, 45, 51), (18, 24, 29, 45, 51)}

``````
``````

In [13]:

%timeit cd.find_maximal_cliques(graph)

``````
``````

100 loops, best of 3: 6.7 ms per loop

``````
``````

In [14]:

%prun cd.find_maximal_cliques(graph)

``````
``````

``````
``````

In [ ]:

``````