sf.apps.clique.search¶

search
(clique, graph, iterations, node_select='uniform')[source]¶ Local search algorithm for identifying large cliques.
This function implements a version of the local search algorithm given in [41] and [42]. 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, with node selection based on uniform randomness and node degree supported. Degreebased node selection involves picking the node with the greatest degree, with ties settled 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) – method of selecting nodes during swap and growth. Can be either
"uniform"
for uniform random selection or"degree"
for degreebased selection. Defaults to"uniform"
 Returns
the largest clique found by the algorithm
 Return type
list[int]
Downloads