Load Balancing Refinement

Very Fortunate Descent (VFD): A local search algorithm for partition refinement under pairwise and balance constraints.

asunder.load_balancing.algorithms.VFD.very_fortunate_descent_legacy(wz, A, a, m, K=2, R=1, R_bounds=None, must_link=[], cannot_link=[], seed=42, fingerprint_decimals=6, allow_block_splitting=True, max_K_increase=0, restarts=6, local_iters=60, w_coassoc=0.05, clustering_Ks=None, clustering_seeds=(0, 1, 2), clustering_methods=('kmeans', 'gmm', 'spectral'), wz_is_C_node=False)

Legacy function for building a feasible decomposition column from co-association structure and local search.

Parameters:

  • wz (numpy.ndarray) – Input node-level matrix.

  • A (numpy.ndarray) – Original adjacency matrix.

  • a (numpy.ndarray) – Degree-like vector used in the modularity construction.

  • m (float) – Modularity scaling constant.

  • K (int or None) – Baseline number of communities.

  • R (int or None) – Width of the allowed cluster-size range. Also corresponds to the load balance tightness (smaller R implies tighter load balance). For a selected cluster count, the lower and upper bounds are computed from the corresponding balanced range rule.

  • R_bounds (tuple or None) – Lower and upper limits on the number of nodes in communities.

  • must_link (sequence of tuple of int) – Must-link pairs.

  • cannot_link (sequence of tuple of int) – Cannot-link pairs.

  • seed (int, default=0) – Random seed.

  • fingerprint_decimals (int, default=6) – Decimal rounding used to form fingerprint blocks.

  • allow_block_splitting (bool, default=True) – If True, allow refinement of coarse fingerprint blocks.

  • max_K_increase (int, default=0) – Maximum increase above the baseline K when the K-constraint is active.

  • restarts (int, default=6) – Number of constructive restarts.

  • local_iters (int, default=60) – Base local-search iteration parameter.

  • w_coassoc (float, default=0.05) – Weight of the co-association cohesion term in local decisions.

  • clustering_Ks (sequence of int or None, default=None) – Community counts used to build the co-association matrix.

  • clustering_seeds (sequence of int, default=(0, 1, 2)) – Seeds used during co-association construction.

  • clustering_methods (sequence of str, default=("kmeans", "gmm", "spectral")) – Clustering methods used during co-association construction.

  • wz_is_C_node (bool, default=False)

Returns:

A pair (Z_col, meta) if a feasible column is found, else None.

Return type:

tuple of (numpy.ndarray, dict) or None

asunder.load_balancing.algorithms.VFD.very_fortunate_descent(wz, A, a, m, K=2, R=1, R_bounds=None, must_link=[], cannot_link=[], seed=42, fingerprint_decimals=6, allow_block_splitting=True, max_K_increase=0, restarts=6, local_iters=60, w_coassoc=0.05, clustering_Ks=None, clustering_seeds=(0, 1, 2), clustering_methods=('kmeans', 'gmm', 'spectral'), wz_is_C_node=False, tabu_max_steps=60, shake_rounds=3, orbit_fallback=False)

Builds a feasible decomposition column from co-association structure and tabu local search. This version has escape mechanisms for common traps: it can swap for improvements, eject one item to unblock moves, use tabu steps to leave local optima, split coarse fingerprint blocks as needed, and shake/re-optimize to find missed solution basins.

Parameters:

  • wz (numpy.ndarray) – Input node-level matrix.

  • A (numpy.ndarray) – Original adjacency matrix.

  • a (numpy.ndarray) – Degree-like vector used in the modularity construction.

  • m (float) – Modularity scaling constant.

  • K (int or None) – Number of communities.

  • R (int or None) – Width of the allowed cluster-size range. Also corresponds to the load balance tightness (smaller R implies tighter load balance). For a selected cluster count, the lower and upper bounds are computed from the corresponding balanced range rule.

  • R_bounds (tuple or None) – Lower and upper limits on the number of nodes in communities.

  • must_link (sequence of tuple of int) – Must-link pairs.

  • cannot_link (sequence of tuple of int) – Cannot-link pairs.

  • seed (int, default=0) – Random seed.

  • fingerprint_decimals (int, default=6) – Decimal rounding used to form fingerprint blocks.

  • allow_block_splitting (bool, default=True) – If True, allow refinement of coarse fingerprint blocks.

  • max_K_increase (int, default=0) – Maximum increase above the baseline K when the K-constraint is active.

  • restarts (int, default=6) – Number of constructive restarts.

  • local_iters (int, default=60) – Base local-search iteration parameter.

  • w_coassoc (float, default=0.05) – Weight of the co-association cohesion term in local decisions.

  • clustering_Ks (sequence of int or None, default=None) – Community counts used to build the co-association matrix.

  • clustering_seeds (sequence of int, default=(0, 1, 2)) – Seeds used during co-association construction.

  • clustering_methods (sequence of str, default=("kmeans", "gmm", "spectral")) – Clustering methods used during co-association construction.

  • wz_is_C_node (bool, default=False) – If True, treat wz directly as the node-level co-association matrix.

  • tabu_max_steps (int, default=60) – Maximum tabu-search steps.

  • shake_rounds (int, default=3) – Number of perturb-and-improve rounds.

  • orbit_fallback (bool, default=False) – If True, build a fallback co-association proxy from orbits when needed.

Returns:

A pair (Z_col, meta) if a feasible column is found, else None.

Return type:

tuple of (numpy.ndarray, dict) or None

asunder.load_balancing.algorithms.VFD.refine_partition(A, partition, a, m, K=2, R=1, R_bounds=None, must_link=[], cannot_link=[], seed=42, fingerprint_decimals=6, allow_block_splitting=True, max_K_increase=0, restarts=6, local_iters=60, w_coassoc=0.05, clustering_Ks=None, clustering_seeds=(0, 1, 2), clustering_methods=('kmeans', 'gmm', 'spectral'), wz_is_C_node=False, tabu_max_steps=60, shake_rounds=3, orbit_fallback=False)

Wrapper function for very_fortunate_descent to make it compatible with existing partition refinement function structure.

Parameters:

  • A (ndarray)

  • partition (ndarray)

  • a (ndarray)

  • m (float)

  • K (int)

  • R (int)

  • R_bounds (tuple | None)

  • must_link (Sequence[Tuple[int, int]])

  • cannot_link (Sequence[Tuple[int, int]])

  • seed (int | None)

  • fingerprint_decimals (int)

  • allow_block_splitting (bool)

  • max_K_increase (int)

  • restarts (int)

  • local_iters (int)

  • w_coassoc (float)

  • clustering_Ks (Sequence[int])

  • clustering_seeds (Sequence[int])

  • clustering_methods (Sequence[str])

  • wz_is_C_node (bool)

  • tabu_max_steps (int)

  • shake_rounds (int)

  • orbit_fallback (bool)