sf.apps.subgraph.search¶
-
search
(subgraphs, graph, min_size, max_size, max_count=10, node_select='uniform')[source]¶ Search for dense subgraphs within an input size range.
For each subgraph from
subgraphs
, this function resizes usingresize()
to the input range specified bymin_size
andmax_size
, resulting in a range of differently sized subgraphs. This function loops over all elements ofsubgraphs
and keeps track of themax_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 thenode_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]]]]