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. Degreebased 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 degreebased selection. Defaults to"uniform"
.
 Returns
a new clique subgraph of equal size as the input
 Return type
list[int]
Downloads