Spectral Algorithms

Dual-adjusted spectral bisection and partition refinement routines.

asunder.base.algorithms.spectral.make_dual_adjusted_matrix(A, a, m, dualW, symmetrize=True)

Build the dual-adjusted modularity matrix used by the subproblem.

Parameters:

  • A (array_like of float, shape (N, N)) – Adjacency or weighted adjacency matrix.

  • a (array_like of float, shape (N,)) – Degree-like vector used in the modularity term.

  • m (float) – Positive graph normalization constant.

  • dualW (array_like of float, shape (N, N)) – Matrix of dual contributions aligned with the partition matrix.

  • symmetrize (bool, optional) – If True, replace the matrix by its symmetric part. This is appropriate because the partition matrix is symmetric.

Returns:

B – Dual-adjusted objective matrix.

Return type:

np.ndarray of float, shape (N, N)

asunder.base.algorithms.spectral.group_vector_to_matrix(s)

Convert a two-way group vector into a partition matrix.

Parameters:

s (array_like of int, shape (N,)) – Two-way assignment vector. Positive entries are treated as one group; non-positive entries are treated as the other group.

Returns:

P – Binary matrix where P[i, j] = 1 when nodes i and j are in the same group.

Return type:

np.ndarray of int, shape (N, N)

asunder.base.algorithms.spectral.matrix_to_group_vector(P)

Convert a two-community partition matrix into a local {-1, 1} vector.

Parameters:

P (array_like of int or float, shape (N, N)) – Binary two-community partition matrix.

Returns:

s – Group vector whose first node’s community is labeled 1 and whose other community is labeled -1.

Return type:

np.ndarray of int, shape (N,)

asunder.base.algorithms.spectral.vector_to_communities(s)

Convert a two-way group vector into nonempty local communities.

Parameters:

s (array_like of int, shape (N,)) – Two-way assignment vector.

Returns:

communities – Nonempty sets of local node indices.

Return type:

list[set[int]]

asunder.base.algorithms.spectral.relabel_consecutive(labels)

Relabel community assignments to consecutive integers.

Parameters:

labels (array_like of hashable, shape (N,)) – Community label for each node.

Returns:

relabeled – Consecutive integer labels preserving equality structure.

Return type:

np.ndarray of int, shape (N,)

asunder.base.algorithms.spectral.partition_objective(B, z)

Evaluate the dual-adjusted partition objective.

Parameters:

  • B (array_like of float, shape (N, N)) – Dual-adjusted objective matrix.

  • z (array_like of int or float, shape (N, N)) – Partition matrix.

Returns:

objective – Value of sum(B * z).

Return type:

float

asunder.base.algorithms.spectral.restricted_modularity_matrix(B, group)

Build the row-sum-corrected matrix for splitting one community.

Parameters:

  • B (array_like of float, shape (N, N)) – Dual-adjusted objective matrix.

  • group (Iterable[int]) – Node indices in the community being split.

Returns:

B_g – Restricted matrix whose row sums are zero.

Return type:

np.ndarray of float, shape (k, k)

asunder.base.algorithms.spectral.compute_modularity_from_vector(B_g, s)

Evaluate a local two-way split under a restricted objective matrix.

Parameters:

  • B_g (array_like of float, shape (k, k)) – Restricted matrix for the community being split.

  • s (array_like of int, shape (k,)) – Two-way assignment vector.

Returns:

objective – Local split value sum(B_g * z_s).

Return type:

float

asunder.base.algorithms.spectral.flip_vertex(s, vertex)

Flip one vertex in a two-way group vector.

Parameters:

  • s (array_like of int, shape (N,)) – Two-way assignment vector.

  • vertex (int) – Local vertex index to flip.

Returns:

s_new – Assignment vector after the flip.

Return type:

np.ndarray of int, shape (N,)

asunder.base.algorithms.spectral.refine_two_way_split(B_g, s_init, tol=1e-10)

Refine a two-way split by Kernighan-Lin-style single-node flips.

Parameters:

  • B_g (array_like of float, shape (k, k)) – Restricted matrix for the community being split.

  • s_init (array_like of int, shape (k,)) – Initial two-way assignment vector.

  • tol (float, optional) – Minimum improvement required to accept a sweep.

Returns:

  • s (np.ndarray of int, shape (k,)) – Refined two-way assignment vector.

  • value (float) – Local value of the refined split.

asunder.base.algorithms.spectral.modularity_maximization_matrix(G, B_g=None, initial_partition_matrix=None, tol=1e-10)

Refine a two-way partition matrix under a local objective.

Parameters:

  • G (object) – Graph-like object with number_of_nodes. Only the node count is used.

  • B_g (array_like of float, shape (N, N)) – Restricted objective matrix for the local split.

  • initial_partition_matrix (array_like of int or float, shape (N, N), optional) – Initial two-way partition matrix. If omitted, all vertices start in one community.

  • tol (float, optional) – Minimum improvement required to accept a move sweep.

Returns:

final_partition_matrix – Refined two-way partition matrix.

Return type:

np.ndarray of int, shape (N, N)

asunder.base.algorithms.spectral.modularity_maximization_matrix_subset(G, B_g, subset, initial_partition_matrix=None, tol=1e-10)

Refine a two-way split for a specified subset of graph nodes.

Parameters:

  • G (object) – Graph-like object with nodes. Used only to form a global label map.

  • B_g (array_like of float, shape (k, k)) – Restricted matrix ordered according to subset.

  • subset (Iterable[int]) – Node indices in the same order used by B_g.

  • initial_partition_matrix (array_like of int or float, shape (k, k), optional) – Initial two-way partition matrix for the subset.

  • tol (float, optional) – Minimum improvement required to accept a move sweep.

Returns:

  • refined_partition_matrix (np.ndarray of int, shape (k, k)) – Refined partition matrix for the subset.

  • global_partition (dict) – Dictionary mapping nodes to {-1, 0, 1}, where nodes outside the subset receive 0.

asunder.base.algorithms.spectral.apply_group_split(z, group, s)

Apply a local two-way split to a global partition matrix.

Parameters:

  • z (array_like of int or float, shape (N, N)) – Current global partition matrix.

  • group (Iterable[int]) – Global node indices being split.

  • s (array_like of int, shape (k,)) – Local two-way assignment vector ordered according to group.

Returns:

z_new – Updated global partition matrix.

Return type:

np.ndarray of int, shape (N, N)

asunder.base.algorithms.spectral.spec_part_extra_bisect(A, a, m, dualW, z_curr, group, refinement=False, verbose=False, tol=1e-10)

Propose and accept one dual-adjusted spectral bisection if it improves value.

Parameters:

  • A (array_like of float, shape (N, N)) – Adjacency or weighted adjacency matrix.

  • a (array_like of float, shape (N,)) – Degree-like vector used in the modularity term.

  • m (float) – Positive graph normalization constant.

  • dualW (array_like of float, shape (N, N)) – Matrix of dual contributions aligned with the partition matrix.

  • z_curr (array_like of int or float, shape (N, N)) – Current global partition matrix.

  • group (Iterable[int]) – Current community to bisect.

  • refinement (bool, optional) – If True, run local two-way flip refinement before testing acceptance.

  • verbose (bool, optional) – If True, print accepted and rejected split diagnostics.

  • tol (float, optional) – Minimum objective improvement required to accept the split.

Returns:

  • gp (np.ndarray of int, shape (k,)) – Local two-way assignment vector ordered according to group.

  • sub_obj_val (float) – Objective value after the accepted split, or the current value if the split is rejected.

  • z_out (np.ndarray of int, shape (N, N)) – Updated global partition matrix if accepted; otherwise z_curr.

asunder.base.algorithms.spectral.best_single_node_move(B, labels, current_obj, allow_singletons=True, tol=1e-10)

Find the best improving single-node move across existing communities.

Parameters:

  • B (array_like of float, shape (N, N)) – Dual-adjusted objective matrix.

  • labels (array_like of int, shape (N,)) – Current community labels.

  • current_obj (float) – Objective value of the current labeling.

  • allow_singletons (bool, optional) – If True, also test moving a node into a new singleton community.

  • tol (float, optional) – Minimum improvement required to accept a move.

Returns:

  • best_labels (np.ndarray of int, shape (N,)) – Labels after the best move, or the original labels if no move improves.

  • best_obj (float) – Objective value after the best move.

  • improved (bool) – True if an improving move was found.

asunder.base.algorithms.spectral.greedy_global_refinement(B, z_init, allow_singletons=True, tol=1e-10, max_moves=None)

Refine a full partition by greedy single-node moves.

Parameters:

  • B (array_like of float, shape (N, N)) – Dual-adjusted objective matrix.

  • z_init (array_like of int or float, shape (N, N)) – Initial partition matrix.

  • allow_singletons (bool, optional) – If True, allow moving a node into a new singleton community.

  • tol (float, optional) – Minimum improvement required to accept a move.

  • max_moves (int, optional) – Maximum number of accepted moves. If omitted, at most N ** 2 moves are accepted.

Returns:

  • z (np.ndarray of int, shape (N, N)) – Refined partition matrix.

  • obj (float) – Objective value of the refined partition.

  • changed (bool) – True if at least one node move was accepted.

asunder.base.algorithms.spectral.full_spectral_bisection(A, a, m, dualW, refinement=False, global_refinement=True, allow_singletons=True, max_outer_passes=None, tol=1e-10, verbose=False)

Build a dual-adjusted partition using repeated spectral bisection.

Parameters:

  • A (array_like of float, shape (N, N)) – Adjacency or weighted adjacency matrix.

  • a (array_like of float, shape (N,)) – Degree-like vector used in the modularity term.

  • m (float) – Positive graph normalization constant.

  • dualW (array_like of float, shape (N, N)) – Matrix of dual contributions aligned with the partition matrix.

  • refinement (bool, optional) – If True, refine each proposed two-way split before acceptance.

  • global_refinement (bool, optional) – If True, run global single-node-move refinement after each bisection pass. This permits correction of earlier splits.

  • allow_singletons (bool, optional) – If True, global refinement may move a node into a singleton community.

  • max_outer_passes (int, optional) – Maximum number of bisection passes. If omitted, at most N passes are run.

  • tol (float, optional) – Minimum improvement required to accept a split or move.

  • verbose (bool, optional) – If True, print accepted and rejected move diagnostics.

Returns:

  • z_curr (np.ndarray of int, shape (N, N)) – Final partition matrix.

  • sub_obj_val (float) – Final dual-adjusted subproblem objective value.