# 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 in the resize() function 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 the subgraph. This function returns a dictionary over the range of sizes specified, with each value being the corresponding resized subgraph.

Whenever there are multiple candidate nodes with the same degree, there must be a choice of which node to add or remove. The supported choices are:

• Select among candidate nodes uniformly at random;

• Select the candidate node with the greatest node weight, settling remaining ties uniformly at random.

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.