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
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 a subgraph to a range of input sizes. |
|
Search for dense subgraphs within an input size range. |