swap(clique, graph, node_select='uniform')[source]

If possible, generates a new clique by swapping a node in the input clique with a node outside the clique.

Proceeds by calculating the set \(C_1\) of nodes in the rest of the graph that are connected to all but one of the nodes in the clique. If this set is not empty, this function randomly picks a node and swaps it with the corresponding node in the clique that is not connected to it. The set \(C_1\) and corresponding nodes in the clique are provided by the c_1() function.

Whenever there are multiple nodes within \(C_1\), one must choose which node to add to the growing clique. This function allows a method of choosing nodes to be set 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.

Example usage:

>>> graph = nx.wheel_graph(5)
>>> graph.remove_edge(0, 4)
>>> clique = [0, 1, 2]
>>> swap(clique, graph)
[0, 2, 3]
  • clique (list[int]) – a subgraph specified by a list of nodes; the subgraph must be a clique

  • graph (nx.Graph) – the input graph

  • node_select (str, list or array) – method of selecting incoming nodes from \(C_1\) during swapping. Can be "uniform" (default), "degree", or a NumPy array or list.


a new clique subgraph of equal size as the input

Return type