spacenet.partition.compact_volume_partition#
- spacenet.partition.compact_volume_partition(G, k=None, T=None, distance_attr='Distance', alpha=0.5, p=2, max_iter=10, seed_samples=10, random_seed=0)#
A compact and volume-balanced partitioning algorithm for spatial networks with edge distances. The algorithm seeks to partition the graph into k communities that are spatially contiguous, have similar volumes (total edge lengths), and minimize the distance from nodes to their community medoids. Convergence is achieved when no single node can be moved to a different community to improve the combined objective of compactness and volume balance, or when the maximum number of iterations is reached.
- Parameters:
- Gnetworkx.Graph
The input graph to partition. Must be undirected.
- kint, optional
The desired number of communities. If None, a heuristic based on the number of nodes will be used.
- Tfloat, optional
The target volume for each community. If None, it will be estimated based on the total edge length and k.
- distance_attrstr, optional
The edge attribute to use as distance for the partitioning. Default is “Distance”.
- alphafloat, optional
The weight of the volume penalty in the objective function. Must be in [0, 1]. Default is 0.5.
- pint, optional
The exponent for the volume penalty. Default is 2 (squared penalty).
- max_iterint, optional
The maximum number of iterations for the local moving phase. Default is 10.
- seed_samplesint, optional
The number of samples to use when approximating medoids. Default is 10.
- random_seedint or None, optional
The random seed for reproducibility. If None, a random seed will be used. Default is 0.
- Returns:
- PartitionResult
A dataclass containing the partitioning results, including:
labels: A dictionary mapping each node to its assigned community.
community_lengths: A dictionary mapping each community to the total length of internal edges (W).
community_cut_lengths: A dictionary mapping each community to the total length of cut edges (B).
community_volumes: A dictionary mapping each community to its volume (V = W + B).
medoids: A dictionary mapping each community to its medoid node.
T: The target volume used in the partitioning.
k: The number of communities in the final partitioning.
objective: The final value of the objective function.
compactness: The final compactness component of the objective function.
volume_penalty: The final volume penalty component of the objective function.
total_cut_length: The total length of cut edges across all communities.
moves: The total number of node moves made during the local moving phase.
iterations: The number of iterations taken in the local moving phase until convergence or reaching max_iter.