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_adj_matrix_new(A, worthy_edges=None, must_link=None, keep_self_loops=True, return_stats=False, 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.

  • return_stats (bool) – If True, return a dict of per-supernode stats.

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

  • comp2nodes (list[np.ndarray]) – Reverse mapping: nodes in each supernode.

  • stats (dict or None) – Per-supernode stats (only if return_stats=True).

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.contract_adj_matrix_cp(A, unworthy_edges=None, nonlinear_nodes=None, keep_self_loops=True, return_stats=False, degree_preserving=True)

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

Parameters:

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

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

  • nonlinear_nodes (set[int]) – Nonlinear nodes.

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

  • return_stats (bool) – If True, return a dict of per-supernode stats.

  • 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 (np.ndarray of int, shape (k, k)) – Contracted adjacency.

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

  • comp2nodes (list[np.ndarray]) – Reverse mapping: nodes in each supernode.

  • stats (dict or None) – Per-supernode stats (only if return_stats=True).

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)