sf.apps.clique.shrink

shrink(subgraph, graph, node_select='uniform')[source]

Shrinks an input subgraph until it forms a clique.

Proceeds by removing nodes in the input subgraph one at a time until the result is a clique that satisfies is_clique(). Upon each iteration, this function selects the node with lowest degree relative to the subgraph and removes it.

In some instances, there may be multiple nodes of minimum degree as candidates to remove from the subgraph. The method of selecting which of these nodes to remove is specified by the node_select argument, which can be either:

  • "uniform" (default): choose a node from the candidates uniformly at random;

  • A list or array: specifying the node weights of the graph, resulting in choosing the node from the candidates with the lowest weight, settling ties by uniform random choice.

Example usage:

>>> graph = nx.barbell_graph(4, 0)
>>> subgraph = [0, 1, 2, 3, 4, 5]
>>> shrink(subgraph, graph)
[0, 1, 2, 3]
Parameters
  • subgraph (list[int]) – a subgraph specified by a list of nodes

  • graph (nx.Graph) – the input graph

  • node_select (str, list or array) – method of settling ties when more than one node of equal degree can be removed. Can be "uniform" (default), or a NumPy array or list.

Returns

a clique of size smaller than or equal to the input subgraph

Return type

list[int]