Subproblem¶

Subproblem routines for CSD decomposition.

asunder.base.column_generation.subproblem.heuristic_subproblem(A, a, m, duals, algo='louvain', package='networkx', refine=False, refine_params=None, verbose=False, gamma=1, exact_rc=True, seed=42)¶

Solve pricing heuristically via selected clustering backend.

Parameters:

A (np.ndarray of int | float, shape (N, N)) – Adjacency / weight matrix.
a (np.ndarray of int | float, shape (N,)) – Degree-like vector; defaults to row sums of the symmetrized adjacency.
m (float) – Twice the total weight in the graph.
duals (Dict[str, np.ndarray or float]) – Dual terms used to modify the community detection objective. 2D, 1D and scalar dual values are supported. Missing entries are treated as zeros.
algo (str) – Name of third-party heuristic subproblem used to replace the ILP subproblem.
package (str) – Package from which third-party heuristic subproblem is selected. See CSD_decomposition for more detail.
refine (bool) – Boolean value that determines whether a refinement operation is run in the subproblem.
refine_params (dict[str, callable or dict]) – Refinement function and its corresponding arguments.
verbose (int or bool) – Controls the level of detail in the printed output. -1: No output False | 0: Minimal output True | 1: Detailed output
gamma (int) – Resolution parameter which controls the scale and size of the detected clusters. Should be left as default (1) if: algo is leiden and package is leidenalg" algo is greedy or multilevel and package is igraph algo is girvan_newman and package is networkx
seed (int or None) – Random seed value

Returns:

Computed result.

Return type:

Any

asunder.base.column_generation.subproblem.solve_subproblem(A, a, m, duals, use_augmented_adjacency=False, verbose=False, solver=None)¶

Solve pricing exactly as a binary ILP with transitivity constraints.

Parameters:

A (np.ndarray of int | float, shape (N, N)) – Adjacency / weight matrix.
a (np.ndarray of int | float, shape (N,)) – Degree-like vector; defaults to row sums of the symmetrized adjacency.
m (float) – Twice the total weight in the graph.
duals (Dict[str, np.ndarray or float]) – Dual terms used to modify the community detection objective. 2D, 1D and scalar dual values are supported. Missing entries are treated as zeros.
use_augmented_adjacency (bool) – Determines whether augmented adjacency is used with the ILP or not. Defaults to False.
verbose (int or bool) – Controls the level of detail in the printed output. -1: No output False | 0: Minimal output True | 1: Detailed output
solver (Any) – Solver object.

Returns:

Computed result.

Return type:

Any

asunder.base.column_generation.subproblem.custom_heuristic_subproblem(A, a, m, duals, algo='full_louvain', verbose=False, refine=False, refine_params=None, max_iterations=50, tolerance=1e-08, seed=42)¶

Run in-package custom pricing heuristics (spectral/modified Louvain).

Parameters:

A (np.ndarray of int | float, shape (N, N)) – Adjacency / weight matrix.
a (np.ndarray of int | float, shape (N,)) – Degree-like vector; defaults to row sums of the symmetrized adjacency.
m (float) – Twice the total weight in the graph.
duals (Dict[str, np.ndarray or float]) – Dual terms used to modify the community detection objective. 2D, 1D and scalar dual values are supported. Missing entries are treated as zeros.
algo (str) – Name of custom heuristic subproblem used to replace the ILP subproblem.
verbose (int or bool) – Controls the level of detail in the printed output. -1: No output False | 0: Minimal output True | 1: Detailed output
refine (bool) – Boolean value that determines whether a refinement operation is run in the subproblem.
refine_params (dict[str, callable or dict]) – Refinement function and its corresponding arguments.
max_iterations (int) – Maximum number of iterations.
tolerance (float) – Tolerance value.
seed (int or None) – Random seed value

Returns:

Computed result.

Return type:

Any