sf.apps.subgraph.search

search(subgraphs, graph, min_size, max_size, max_count=10, node_select='uniform')

Search for dense subgraphs within an input size range.

For each subgraph from subgraphs, this function resizes using resize() to the input range specified by min_size and max_size, resulting in a range of differently sized subgraphs. This function loops over all elements of subgraphs and keeps track of the max_count number of densest subgraphs identified for each size.

In both growth and shrink phases of resize(), 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 = sample.postselect(s, 16, 30)
>>> s = sample.to_subgraphs(s, g)
>>> search(s, g, 8, 9, max_count=3)
{9: [(0.9722222222222222, [21, 22, 23, 24, 25, 26, 27, 28, 29]),
  (0.9722222222222222, [20, 21, 22, 24, 25, 26, 27, 28, 29]),
  (0.9444444444444444, [20, 21, 22, 23, 24, 25, 26, 27, 29])],
 8: [(1.0, [21, 22, 24, 25, 26, 27, 28, 29]),
  (1.0, [21, 22, 23, 24, 25, 26, 27, 28]),
  (1.0, [20, 21, 22, 24, 25, 26, 27, 29])]}

Parameters

• subgraphs (list[list[int]]) – a list of subgraphs specified by their nodes

• graph (nx.Graph) – the input graph

• min_size (int) – minimum size to search for dense subgraphs

• max_size (int) – maximum size to search for dense subgraphs

• max_count (int) – maximum number of densest subgraphs to keep track of for each size

• 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, each containing a list of densest subgraphs reported as a tuple of subgraph density and subgraph nodes, sorted in non-increasing order of density

Return type

dict[int, list[tuple[float, list[int]]]]

code/api/strawberryfields.apps.subgraph.search

 

Download Python script

 

Download Notebook

 

View on GitHub