sf.apps.clique.search

search(clique, graph, iterations, node_select='uniform')

Local search algorithm for identifying large cliques.

This function implements a version of the local search algorithm given in [14] and [15]. It proceeds by iteratively applying phases of greedy growth and plateau search to the input clique subgraph.

Growth phase

Growth is achieved using the grow() function, which repeatedly evaluates the set \(C_0\) of nodes in the remainder of the graph that are connected to all nodes in the clique, and selects one candidate node from \(C_0\) to make a larger clique.

Search phase

Plateau search is performed with the swap() function, which evaluates the set \(C_1\) of nodes in the remainder of the graph that are connected to all but one of the nodes in the clique. The function then proceeds to select one candidate from \(C_1\) and swap it with its corresponding node in the clique.

Whenever the sets \(C_0\) and \(C_1\) used during growth and swapping have more than one element, there must be a choice of which node to add or swap. This choice is specified with the node_select argument, which can be any of the following:

• "uniform" (default): choose a node from the candidates uniformly at random;

• "degree": choose the node from the candidates with the greatest degree, settling ties by uniform random choice;

• A list or array: specifying the node weights of the graph, resulting in choosing the node from the candidates with the greatest weight, settling ties by uniform random choice.

Stopping

The iterative applications of growth and search are applied until either the specified number of iterations has been carried out or when a dead end has been reached. The function reaches a dead end when it is unable to perform any new swaps or growth.

Example usage:

>>> graph = nx.lollipop_graph(4, 1)
>>> graph.add_edge(2, 4)
>>> clique = [3, 4]
>>> search(clique, graph, iterations=10)
[0, 1, 2, 3]

Parameters

• clique (list[int]) – a subgraph specified by a list of nodes; the subgraph must be a clique

• graph (nx.Graph) – the input graph

• iterations (int) – number of steps in the algorithm

• node_select (str, list or array) – method of selecting nodes during swap and growth. Can be "uniform" (default), "degree", or a NumPy array or list.

Returns

the largest clique found by the algorithm

Return type

list[int]

code/api/strawberryfields.apps.clique.search

 

Download Python script

 

Download Notebook

 

View on GitHub