sf.apps.subgraph.search

search(subgraphs, graph, min_size, max_size, max_count=10)

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.

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

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