Using Strawberry Fields

Development

API

  1. Docs
  2. sf.apps
  3. sf.apps.subgraph
  4. sf.apps.subgraph.resize
  5. Show on GitHub

sf.apps.subgraph.resize

resize(subgraph, graph, min_size, max_size, node_select='uniform')[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, there may be multiple candidate nodes with equal degree to add to or remove from the subgraph. The method of selecting the node 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 highest weight (when growing) and lowest weight (when shrinking), settling remaining ties 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

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

Returns

a dictionary of different sizes with corresponding subgraph

Return type

dict[int, list[int]]

Previous
Next