Load Balancer

asunder.load_balancing.column_generation.LB.LoadBalancer(G, R=1, K=2, R_bounds=None, algorithm='greedy', package='networkx', ifc_generator='random', seed=42, must_link=[], cannot_link=[], refine_post_loop=True, projection_repair=False, projection_time_limit=15.0, max_iterations=None, disable_tqdm=False, verbose=-1)

Solve the load-balanced structure detection problem using Asunder’s column generation workflow.

Parameters:

  • G (nx.Graph) – NetworkX graph representing the relevant problem.

  • R (int) – 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.

  • K (int) – Number of communities.

  • R_bounds (tuple[int, int] | None) – Minimum and maximum number of nodes per community (community size constraint).

  • algo (str) –

    Name of heuristic subproblem used to replace the ILP subproblem. Third-party algorithms combine adjacency and dual information into a unified input while custom algorithms treat adjacency and duals as separate inputs. Supported third-party algorithms are listed under the package parameter. Available custom algorithm options include:

    "spectral":

    Modified iterative bisection algorithm based on Mark Newman’s eigenvector-based method.

    "full_louvain":

    Modified but Louvain-like algorithm.

    "RCCS":

    This means Reduced Cost Community Search and is a greedy and local search heuristic for finding communities that maximize the reduced cost.

    "qmetis":

    Uses the bundled modularity QMETIS library as a load-balancing pricing heuristic. Fractional dual-adjusted weights are safely quantized for QMETIS and every candidate is rescored using Asunder’s original floating-point reduced-cost objective.

  • package (str or None) –

    Package from which non-custom heuristic subproblem is selected. Package and algorithm options include:

    "networkx":

    "louvain", "greedy", "girvan_newman"

    "sknetwork":

    "louvain", "leiden", "lpa"

    "igraph":

    "leiden", "greedy", "infomap", "lpa", "multilevel", "voronoi", "walktrap", "cpm_leiden"

    "leidenalg":

    "leiden", "signed_leiden", "cpm_leiden", "surprise_leiden", "signed_surprise_leiden"

    None:

    "signed_louvain", "spinglass"

    Algorithms that start with "cpm", "signed", and "spinglass" are signed.

  • ifc_generator (str) – "random" if the initial feasible column should be randomly generated (default). "ordered" if the initial feasible column should be generated with some structure-based ordering.

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

  • must_link (list[tuple[int, int]]) – List of node pairs that must be together.

  • cannot_link (list[tuple[int, int]]) – List of node pairs that must not be together.

  • refine_post_loop (bool) – Whether to run post-loop refinement after column generation terminates.

  • projection_repair (bool) – If True, project the refinement input to the nearest feasible load-balanced partition when VFD refinement returns None.

  • projection_time_limit (float or None) – Best-effort solver time limit in seconds for projection_repair. Applied only to supported solver backends.

  • max_iterations (int or None) – Maximum number of column-generation iterations. None runs until convergence.

  • disable_tqdm (bool) – Whether to disable progress bar or not.

  • verbose (int or bool) – Controls the level of detail in the printed output. -1: No output False | 0: Minimal output True | 1: Detailed output

Returns:

Column generation result. The final co-clustering matrix is available as final_partition and load-balancing summaries are in metadata.

Return type:

DecompositionResult