sf.apps.clique.swap

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, with node selection based on uniform randomness and node degree supported. Degree-based node selection involves picking the node with the greatest degree, with ties settled 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]
Parameters
  • 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) – method of selecting nodes from \(C_1\) during growth. Can be either "uniform" for uniform random selection or "degree" for degree-based selection. Defaults to "uniform".

Returns

a new clique subgraph of equal size as the input

Return type

list[int]