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, 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.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) – method of selecting nodes from \(C_0\) 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 or larger size than the input

Return type

list[int]