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]