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")