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.

Notes

For more information, see the reference paper:

Moore et al. (2026). netPCF: Geometry-aware Pair Correlation Functions for Spatial Biology. DOI: https://doi.org/10.64898/2026.07.02.736020

Examples

Compact volume partitioning can be used to create spatially contiguous and volume-balanced communities in a spatial network. Below is an example of how to use the compact_volume_partition function with a spatial network generated from the Spiral dataset. The resulting partition labels are added to the spatial network and visualised.

import spacenet as sn

# get data from the Spiral dataset
sprial_df = sn.datasets.load_dataset('spiral')
points = sprial_df[['x','y']].values

# generate a spatial network using the delaunay method and add labels
G = sn.utils.spatial_network_from_points(points,network_type='delaunay',max_edge_distance=75)

# compute a compact volume partition for the spatial network with 5 partitions
cv_partition = sn.partition.compact_volume_partition(G,k=5)

#get the labels and nodes associated with each partition
partition_label_dict = cv_partition.labels
nodes_partition,labels_partition = list(partition_label_dict.keys()),list(partition_label_dict.values())

# add the partition labels to the spatial network
sn.utils.add_node_labels(G,
                        labels=labels_partition,
                        nodes=nodes_partition,
                        node_label_name='volume_partition (5)')

# plot the spatial network with nodes coloured by their partition label
sn.utils.plot_spatial_network(G,node_label_name='volume_partition (5)')
On this page