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 [5].

See also

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.