sf.apps.clique.grow

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

Iteratively adds new nodes to the input clique to generate a larger clique.

Each iteration involves calculating the set \(C_0\) (provided by the function c_0()) with respect to the current clique. This set represents the nodes in the rest of the graph that are connected to all of the nodes in the current clique. Therefore, adding any of the nodes in \(C_0\) will create a larger clique. This function proceeds by repeatedly evaluating \(C_0\) and selecting and adding a node from this set to add to the current clique. Growth is continued until \(C_0\) becomes empty.

Whenever there are multiple nodes within \(C_0\), 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.complete_graph(10)
>>> clique = [0, 1, 2, 3, 4]
>>> grow(clique, graph)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
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, list or array) – method of selecting nodes from \(C_0\) during growth. Can be "uniform" (default), "degree", or a NumPy array or list.

Returns

a new clique subgraph of equal or larger size than the input

Return type

list[int]