sf.apps.subgraph.resize

resize(subgraph, graph, min_size, max_size)[source]

Resize a subgraph to a range of input sizes.

This function uses a greedy approach to iteratively add or remove nodes one at a time to an input subgraph to reach the range of sizes specified by min_size and max_size.

When growth is required, the algorithm examines all nodes from the remainder of the graph as candidates and adds the single node with the highest degree relative to the rest of the subgraph. This results in a graph that is one node larger, and if growth is still required, the algorithm performs the procedure again.

When shrinking is required, the algorithm examines all nodes from within the subgraph as candidates and removes the single node with lowest degree relative to the subgraph. In both growth and shrink phases, ties for addition/removal with nodes of equal degree are settled by uniform random choice.

Example usage:

>>> s = data.Planted()
>>> g = nx.Graph(s.adj)
>>> s = [20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
>>> resize(s, g, 8, 12)
{10: [20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
 11: [11, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
 12: [0, 11, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
 9: [20, 21, 22, 24, 25, 26, 27, 28, 29],
 8: [20, 21, 22, 24, 25, 26, 27, 29]}
Parameters
  • subgraph (list[int]) – a subgraph specified by a list of nodes

  • graph (nx.Graph) – the input graph

  • min_size (int) – minimum size for subgraph to be resized to

  • max_size (int) – maximum size for subgraph to be resized to

Returns

a dictionary of different sizes with corresponding subgraph

Return type

dict[int, list[int]]