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 [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]