Note

Click here to download the full example code

# Maximum Clique¶

*Technical details are available in the API documentation:* sf.apps.clique

Here we’ll explore how to combine GBS samples with local search algorithms to find large cliques in graphs. Let’s get started!

A clique is a special type of subgraph where all possible connections between nodes are present; they are densest possible subgraphs of their size. The maximum clique problem, or max clique for short, asks the question: given a graph \(G\), what is the largest clique in the graph? Max clique is NP-Hard, so finding the biggest clique becomes challenging for graphs with many nodes. This is why we need clever algorithms to identify large cliques!

To get started, we’ll analyze the 24-node TACE-AS graph used in [40]. This
is the *binding interaction graph* representing the spatial compatibility of atom pairs in a
protein-molecule complex. Cliques in this graph correspond to stable docking configurations, which
are of interest in determining how the molecule interacts with the protein.

The first step is to import the Strawberry Fields `apps`

module and external dependencies:

```
from strawberryfields.apps import data, plot, sample, clique
import numpy as np
import networkx as nx
import plotly
```

The adjacency matrix of the TACE-AS graph can be loaded from the `data`

module and the
graph can be visualized using the `plot`

module:

```
TA = data.TaceAs()
A = TA.adj
TA_graph = nx.Graph(A)
plot_graph = plot.graph(TA_graph)
plotly.offline.plot(plot_graph, filename="TACE-AS.html")
```