Graph Utilities

Graph and partition utilities.

asunder.base.utils.graph.get_optimization_params_from_graph(n=None, graph_edges=None, G=None)

Build adjacency, degree vector, and volume from graph input.

Parameters:

  • n (int) – Number of nodes.

  • graph_edges (list[sequence[int]]) – List of graph edges.

  • G (nx.Graph) – NetworkX graph.

Returns:

  • adjacency_matrix (np.ndarray of int | float, shape (n, n)) – Adjacency / weight matrix.

  • degree_matrix (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.

asunder.base.utils.graph.group_nodes_by_community(z_matrix)

Extract community map and node groups from a partition matrix.

Parameters:

z_matrix (ndarray of int, shape (N, N)) – Partition mat.

Returns:

  • community_map (dict) – Map from node index to community index

  • communities (list) – List of different communities

asunder.base.utils.graph.map_community_labels(community_map, label_map)

Remap integer community ids to external node labels.

Parameters:

  • community_map (dict) – Map from node index to community index

  • label_map (Any) – Map from node index to node label in Graph.

Returns:

map from node label to community index

Return type:

dict[str, int]

asunder.base.utils.graph.partition_vector_to_2d_matrix(partition)

Convert a 1D label vector to a binary co-association matrix.

Parameters:

partition (array of int, shape (n,)) – 1D label vector.

Returns:

z – Binary co-association matrix.

Return type:

ndarray of int, shape (n, n)

asunder.base.utils.graph.partition_matrix_to_vector(Z)

Convert a symmetric 2D partition matrix Z into a 1D membership vector.

Parameters:

Z (ndarray of int, shape (n, n)) – Binary co-association matrix.

Returns:

labels – 1D label vector.

Return type:

array of int, shape (n,)

asunder.base.utils.graph.contract_node_pairs(pairs, node2comp, *, relation_name='node-pair', reject_internal=False)

Map original-node pairs to unique contracted-component pairs.

Parameters:

  • pairs (iterable[tuple[int, int]] or None) – Original-node pairs to map.

  • node2comp (ndarray of int, shape (N,)) – Mapping from original node index to component index.

  • relation_name (str) – Human-readable relation name used in validation errors.

  • reject_internal (bool) – If True, reject a pair whose endpoints contract into the same component. This is required for cannot-link constraints.

Returns:

Sorted, deduplicated component-level pairs.

Return type:

list[tuple[int, int]]

Raises:

ValueError – If a pair contains an invalid node index or becomes an internal pair while reject_internal is enabled.

asunder.base.utils.graph.contract_partition_matrix(partition, node2comp, *, atol=1e-08)

Convert a component-consistent partition to contracted dimensions.

A warm-start partition is representable after contraction only when every original node in a component has the same relationship to every other component. In particular, all nodes within a component must be together.

Parameters:

  • partition (ndarray) – Original (N, N) or already-contracted (C, C) co-association matrix.

  • node2comp (ndarray of int, shape (N,)) – Mapping from original nodes to C contracted components.

  • atol (float) – Absolute tolerance used for component-consistency checks.

Returns:

A copy of the partition with shape (C, C).

Return type:

ndarray

Raises:

ValueError – If the matrix has an incompatible shape, is asymmetric, lacks a unit diagonal, or separates nodes belonging to one contracted component.

asunder.base.utils.graph.contract_adj_matrix_new(A, worthy_edges=None, must_link=None, keep_self_loops=True, degree_preserving=True)

Contract A according to connected components induced by rule-graph (G_ml), and optionally keep self-loops to encode intra-block connectivity strength.

Parameters:

  • A (ndarray, shape (n, n)) – Graph adjacency (assumed symmetric, no self-loops.)

  • worthy_edges (set[tuple[int,int]] or None) – The edges that can connect different communities.

  • must_link (iterable[tuple[int,int]] or None) – Extra links to force-merge nodes into the same component.

  • keep_self_loops (bool) – If True, store intra-community weight on the diagonal of the coarse matrix.

  • degree_preserving (bool) – If True, we set diag(C,C) = 2 * intra_sum_C so that vol(supernode C) = sum_{i in C} deg(i). If False, diag = intra_sum_C.

Returns:

  • A_sup (ndarray, shape (k, k)) – Contracted adjacency.

  • node2comp (np.ndarray[int]) – Mapping from original node to supernode id.

asunder.base.utils.graph.expand_z_matrix(z, node2comp, dim=2)

Expand a supernode-level partition back to original node dimension.

Parameters:

  • z (np.ndarray[int]) – contracted 1D label vector or binary co-association matrix.

  • node2comp (np.ndarray[int]) – Mapping from original node to supernode id.

  • dim (int) – Dimension of input array (1 or 2).

Returns:

z_full – Expanded 1D label vector or binary co-association matrix.

Return type:

np.ndarray[int]

asunder.base.utils.graph.z_hamming_upper(Z1, Z2)

Compute Hamming distance on strict upper-triangle partition entries.

Parameters:

  • Z1 (np.ndarray) – Binary co-association partition matrix.

  • Z2 (np.ndarray) – Binary co-association partition matrix.

Returns:

Computed hamming distance.

Return type:

float

asunder.base.utils.graph.sufficiently_different(Z_new, Z_pool, dist_min)

Check whether a candidate partition differs sufficiently from a pool.

Parameters:

  • Z_new (np.ndarray) – Candidate partition.

  • Z_pool (list) – Pool of existing partitions.

  • dist_min (float) – Distance threshold.

Returns:

True if the candidate partition does not differ sufficiently from the pool.

Return type:

bool

asunder.base.utils.graph.proportions_to_partition(r, threshold=0.5)

Convert per-node probabilities into a binary co-association matrix.

Parameters:

  • r (np.ndarray) – Per-node probabilities.

  • threshold (float) – Threshold probability value.

Returns:

Binary co-association matrix.

Return type:

ndarray of int, shape (n, n)