# sf.apps.subgraph¶

Tools for users to find dense subgraphs of different sizes.

The search heuristic in this module works by resizing a collection of starting subgraphs and keeping track of the densest identified. The starting subgraphs can be selected by sampling from GBS, resulting in candidates that are likely to be dense .

Dense Subgraphs

## Algorithm¶

The heuristic algorithm provided proceeds as follows. Each starting subgraph $$s$$ is resized to a range of sizes $$\{k\}_{k_{\min}}^{k_{\max}}$$, resulting in the subgraphs $$s_{k}$$. For a given size $$k$$, a collection of the densest $$n$$ subgraphs identified is recorded, meaning that $$s_{k}$$ is added to the collection only if it has sufficient density.

This algorithm returns a dictionary over the range of sizes specified, with each value being the collection of densest-$$k$$ subgraphs. This collection is a list of tuple pairs specifying the subgraph density and nodes.

## Subgraph resizing¶

The key element of the search() algorithm is the resizing of each subgraph, allowing a range of subgraph sizes to be tracked. Resizing proceeds by greedily adding or removing nodes to a subgraph one-at-a-time. Node selection is carried out by picking the node with the greatest or least degree with respect to to the subgraph, with ties settled uniformly at random.

This function returns a dictionary over the range of sizes specified, with each value being the corresponding resized subgraph.

Functions

 resize(subgraph, graph, min_size, max_size) Resize a subgraph to a range of input sizes. search(subgraphs, graph, min_size, max_size) Search for dense subgraphs within an input size range.