Partitioning#

Partitioning strategies for network clustering.

Geographical Partitioning#

class npap.partitioning.geographical.GeographicalConfig[source]

Bases: object

Configuration parameters for geographical partitioning.

random_state

Random seed for reproducibility in stochastic algorithms.

Type:: int

max_iter

Maximum iterations for iterative algorithms (K-means, K-medoids).

Type:: int

n_init

Number of initializations for K-means.

Type:: int

hierarchical_linkage

Linkage criterion for hierarchical clustering (‘ward’ for Euclidean, or ‘complete’/’average’/’single’).

Type:: str

infinite_distance

Value used to represent “infinite” distance between nodes in different AC islands. Using a large finite value instead of np.inf to avoid numerical issues in clustering algorithms.

Type:: float

random_state: int = 42

max_iter: int = 300

n_init: int = 10

hierarchical_linkage: str = 'ward'

infinite_distance: float = 10000.0

__init__(random_state=42, max_iter=300, n_init=10, hierarchical_linkage='ward', infinite_distance=10000.0)

Parameters:

random_state (int)
max_iter (int)
n_init (int)
hierarchical_linkage (str)
infinite_distance (float)

Return type:

None

class npap.partitioning.geographical.GeographicalPartitioning[source]

Bases: PartitioningStrategy

Partition nodes based on geographical distance.

This strategy clusters nodes based on their spatial coordinates using various clustering algorithms. It supports both Euclidean distance (for projected coordinates) and Haversine distance (for lat/lon coordinates).

AC-Island Awareness:

When the graph contains data with DC links (nodes have given ‘ac_island’ attribute), the strategy automatically respects AC island boundaries by assigning infinite distance between nodes in different AC islands.

Note: K-means and hierarchical with ‘ward’ linkage cannot support AC-island awareness because they use raw coordinates instead of precomputed distances. When AC islands are detected with these algorithms, a warning is issued recommending alternative algorithms.

Supported algorithms:

‘kmeans’: K-Means clustering (Euclidean only, fast, no AC-island support)
‘kmedoids’: K-Medoids clustering (any metric, robust to outliers, AC-island aware)
‘dbscan’: DBSCAN density-based clustering (automatic cluster count, AC-island aware)
‘hierarchical’: Agglomerative hierarchical clustering (AC-island aware except ward)
‘hdbscan’: HDBSCAN density-based clustering (automatic cluster count, AC-island aware)

Configuration can be provided at: - Instantiation time (via config parameter in __init__) - Partition time (via config or individual parameters in partition())

Partition-time parameters override instance defaults for that call only.

Attributes:

required_attributes: Required node attributes for geographical partitioning.

Methods

partition(graph, **kwargs)

Partition nodes based on geographical coordinates.

SUPPORTED_ALGORITHMS = ['kmeans', 'kmedoids', 'dbscan', 'hierarchical', 'hdbscan']

SUPPORTED_DISTANCE_METRICS = ['euclidean', 'haversine']

AC_ISLAND_AWARE_ALGORITHMS = ['kmedoids', 'dbscan', 'hdbscan']

__init__(algorithm='kmeans', distance_metric='euclidean', ac_island_attr='ac_island', config=None)[source]

Initialize geographical partitioning strategy.

Parameters:

algorithm (str, default 'kmeans') – Clustering algorithm (‘kmeans’, ‘kmedoids’, ‘dbscan’, ‘hierarchical’, ‘hdbscan’).
distance_metric (str, default 'euclidean') – Distance metric (‘haversine’, ‘euclidean’).
ac_island_attr (str, default 'ac_island') – Node attribute name containing AC island ID.
config (GeographicalConfig, optional) – Configuration parameters for the algorithm.

Raises:

ValueError – If unsupported algorithm or distance metric specified.

property required_attributes: dict[str, list[str]]: Required node attributes for geographical partitioning.

partition(graph, **kwargs)[source]

Partition nodes based on geographical coordinates.

Automatically detects and respects AC island boundaries when the graph contains voltage-aware data (nodes have ‘ac_island’ attribute). When AC islands are detected, infinite distance is assigned between nodes in different AC islands.

Parameters:

graph (nx.Graph) – NetworkX graph with lat, lon attributes on nodes.
**kwargs (dict) –
Additional parameters:
- n_clusters : Number of clusters (required for kmeans, kmedoids, hierarchical)
- eps : Epsilon (required for dbscan)
- min_samples : Minimum samples (required for dbscan)
- min_cluster_size : Minimum cluster size for HDBSCAN (default: 5)
- config : GeographicalConfig instance to override instance config
- random_state : Override config parameter
- max_iter : Override config parameter
- n_init : Override config parameter
- hierarchical_linkage : Override config parameter
- infinite_distance : Override config parameter

Returns:

Dictionary mapping cluster_id -> list of node_ids.

Return type:

dict[int, list[Any]]

Raises:

PartitioningError – If partitioning fails.

Electrical Distance Partitioning#

class npap.partitioning.electrical.ElectricalDistanceConfig[source]

Bases: object

Configuration parameters for electrical distance calculations.

Centralizes all magic numbers and tolerances used in the electrical distance partitioning algorithm for better maintainability and tuning.

zero_reactance_replacement

Reactance value used when edge reactance is zero.

Type:: float

regularization_factor

Small value added to B matrix diagonal for numerical stability. Set to 0.0 to disable regularization. Default 1e-10 provides mild regularization that prevents singular matrix issues.

Type:: float

infinite_distance

Value used to represent “infinite” distance between AC islands.

Type:: float

zero_reactance_replacement: float = 1e-05

regularization_factor: float = 1e-10

infinite_distance: float = 10000.0

__init__(zero_reactance_replacement=1e-05, regularization_factor=1e-10, infinite_distance=10000.0)

Parameters:

zero_reactance_replacement (float)
regularization_factor (float)
infinite_distance (float)

Return type:

None

class npap.partitioning.electrical.ElectricalDistancePartitioning[source]

Bases: PartitioningStrategy

Partition nodes based on electrical distance using PTDF in power networks.

This strategy uses the Power Transfer Distribution Factor (PTDF) approach to calculate electrical distances between nodes. The electrical distance is derived from the Euclidean distance between PTDF column vectors, which represents how similarly power injections at different nodes affect line flows.

Mathematical basis:

Build incidence matrix K from directed network topology
Remove slack bus column to get K_sba (slack-bus-adjusted)
Calculate susceptance matrix B = K_sba^T · diag{b} · K_sba
Compute PTDF = diag{b} · K_sba · B^(-1)
Electrical distance: d_ij = ||PTDF[:,i] - PTDF[:,j]||_2

Multi AC-Island Support:

Networks with multiple AC islands (AC zones connected via HVDC) are handled by computing PTDF matrices independently for each island: 1. Group nodes by AC island 2. Select/detect slack bus per island 3. Extract AC-only subgraph per island (lines + transformers, no DC links) 4. Compute PTDF and distances per island 5. Combine into block-diagonal distance matrix with infinite inter-island distances

This is physically correct because PTDF describes AC power flow behavior, and DC links decouple the AC dynamics between islands.

Configuration can be provided at:

Instantiation time (via config parameter in __init__)
Partition time (via config or individual parameters in partition())

Partition-time parameters override instance defaults for that call only.

Attributes:

required_attributes: Required attributes for electrical distance partitioning.

Methods

partition(graph, **kwargs)

Partition nodes based on electrical distance using PTDF.

SUPPORTED_ALGORITHMS = ['kmeans', 'kmedoids']

AC_EDGE_TYPES = {'line', 'trafo'}

__init__(algorithm='kmeans', slack_bus=None, ac_island_attr='ac_island', config=None)[source]

Initialize electrical distance partitioning strategy.

Parameters:

algorithm (str, default 'kmeans') – Clustering algorithm (‘kmeans’, ‘kmedoids’).
slack_bus (Any, optional) – Specific node to use as slack bus (applied to its island), or None for auto-selection per island.
ac_island_attr (str, default 'ac_island') – Node attribute name containing AC island ID.
config (ElectricalDistanceConfig, optional) – Configuration parameters for distance calculations.

Raises:

ValueError – If unsupported algorithm is specified.

property required_attributes: dict[str, list[str]]: Required attributes for electrical distance partitioning.

partition(graph, **kwargs)[source]

Partition nodes based on electrical distance using PTDF.

Parameters:

graph (nx.DiGraph) – NetworkX DiGraph with reactance data on AC edges and ac_island on nodes.
**kwargs (dict) –
Additional parameters:
- n_clusters : Number of clusters (required)
- random_state : Random seed for reproducibility
- max_iter : Maximum iterations for clustering
- config : ElectricalDistanceConfig instance to override instance config
- slack_bus : Override the slack bus for this partition call
- zero_reactance_replacement : Override config parameter
- regularization_factor : Override config parameter
- infinite_distance : Override config parameter

Returns:

Dictionary mapping cluster_id -> list of node_ids.

Return type:

dict[int, list[Any]]

Raises:

PartitioningError – If partitioning fails.
ValidationError – If ac_island attribute is missing.

Voltage-Aware Partitioning#

class npap.partitioning.va_geographical.VAGeographicalConfig[source]

Bases: object

Configuration for voltage-aware geographical partitioning.

voltage_tolerance

Tolerance for voltage comparison (kV). Nodes with voltages within this tolerance are considered the same voltage level. Default is 1.0 kV.

Type:: float

infinite_distance

Value used to represent “infinite” distance between nodes at different voltage levels or AC islands. Using a large finite value instead of np.inf to avoid numerical issues in clustering algorithms.

Type:: float

proportional_clustering

If False (default), runs clustering on full matrix with infinite distances between voltage levels. If True, clusters each voltage island independently with proportional cluster distribution.

Type:: bool

hierarchical_linkage

Linkage criterion for hierarchical clustering. Must be ‘complete’, ‘average’, or ‘single’. Note: ‘ward’ is NOT supported with precomputed distances. Default is ‘complete’ which works well with infinite distances (prevents cross-voltage merging).

Type:: str

voltage_tolerance: float = 1.0

infinite_distance: float = 10000.0

proportional_clustering: bool = False

hierarchical_linkage: str = 'complete'

__init__(voltage_tolerance=1.0, infinite_distance=10000.0, proportional_clustering=False, hierarchical_linkage='complete')

Parameters:

voltage_tolerance (float)
infinite_distance (float)
proportional_clustering (bool)
hierarchical_linkage (str)

Return type:

None

class npap.partitioning.va_geographical.VAGeographicalPartitioning[source]

Bases: PartitioningStrategy

Voltage-Aware Geographical Partitioning Strategy with AC Island Support.

This strategy partitions nodes based on geographical distance while respecting both AC island boundaries and voltage level boundaries.

Notes

Constraint Hierarchy

AC Islands: Nodes in different AC islands are assigned infinite distance. AC islands represent separate AC networks connected only via DC links.
Voltage Levels: Within each AC island, nodes at different voltage levels are also assigned infinite distance.

This ensures clustering only occurs within the same AC island AND the same voltage level, which is physically meaningful for power networks.

Clustering Modes

Two clustering modes are available:

Standard mode (default):

Builds full NxN distance matrix
Sets d(i,j) = inf if ac_island(i) != ac_island(j) OR voltage(i) != voltage(j)
Runs single clustering algorithm on entire matrix
Algorithm handles infinite distances to respect boundaries

Proportional mode:

Groups nodes by (ac_island, voltage_level) combination
Distributes n_clusters proportionally among groups
Runs clustering independently on each group
Guaranteed balanced distribution per group

Supported Algorithms

kmedoids: K-Medoids clustering (works naturally with precomputed distances)
hierarchical: Agglomerative clustering with precomputed distances (uses ‘complete’ linkage by default, configurable)

Configuration

Configuration can be provided at:

Instantiation time (via config parameter in __init__)
Partition time (via config or individual parameters in partition())

Partition-time parameters override instance defaults for that call only.

Attributes:

required_attributes: Required node attributes for voltage-aware geographical partitioning.

Methods

partition(graph, **kwargs)

Partition nodes based on AC island and voltage-aware geographical distance.

SUPPORTED_ALGORITHMS = ['kmedoids', 'hierarchical']

SUPPORTED_DISTANCE_METRICS = ['euclidean', 'haversine']

SUPPORTED_LINKAGES = ['complete', 'average', 'single']

__init__(algorithm='kmedoids', distance_metric='euclidean', voltage_attr='voltage', ac_island_attr='ac_island', config=None)[source]

Initialize voltage-aware geographical partitioning strategy.

Parameters:

algorithm (str, default 'kmedoids') – Clustering algorithm (‘kmedoids’, ‘hierarchical’).
distance_metric (str, default 'euclidean') – Distance metric (‘euclidean’, ‘haversine’).
voltage_attr (str, default 'voltage') – Node attribute name containing voltage level.
ac_island_attr (str, default 'ac_island') – Node attribute name containing AC island ID.
config (VAGeographicalConfig, optional) – Configuration parameters for the algorithm.

Raises:

ValueError – If unsupported algorithm, distance metric, or linkage.

property required_attributes: dict[str, list[str]]: Required node attributes for voltage-aware geographical partitioning.

partition(graph, **kwargs)[source]

Partition nodes based on AC island and voltage-aware geographical distance.

Parameters:

graph (nx.Graph) – NetworkX graph with lat, lon, voltage, and ac_island attributes.
**kwargs (dict) –
Additional parameters:
- n_clusters : Number of clusters (required)
- random_state : Random seed for reproducibility (default: 42)
- max_iter : Maximum iterations for clustering (default: 300)
- config : VAGeographicalConfig instance to override instance config
- voltage_tolerance : Override config parameter
- infinite_distance : Override config parameter
- proportional_clustering : Override config parameter
- hierarchical_linkage : Override config parameter

Returns:

Dictionary mapping cluster_id -> list of node_ids.

Return type:

dict[int, list[Any]]

Raises:

PartitioningError – If partitioning fails.

class npap.partitioning.va_electrical.VAElectricalConfig[source]

Bases: object

Configuration for voltage-aware electrical distance partitioning.

zero_reactance_replacement

Reactance value used when edge reactance is zero. Default is 1e-5.

Type:: float

regularization_factor

Small value added to B matrix diagonal for numerical stability. Set to 0.0 to disable regularization. Default 1e-10 provides mild regularization that prevents singular matrix issues.

Type:: float

infinite_distance

Value used to represent “infinite” distance between nodes in different voltage levels, AC islands, or disconnected components. Using a large finite value instead of np.inf to avoid numerical issues in clustering.

Type:: float

voltage_tolerance

Tolerance for voltage comparison (kV). Nodes with voltages within this tolerance are considered the same voltage level. Default is 1.0 kV.

Type:: float

hierarchical_linkage

Linkage criterion for hierarchical clustering. Options: ‘complete’, ‘average’, ‘single’. Default is ‘complete’.

Type:: str

zero_reactance_replacement: float = 1e-05

regularization_factor: float = 1e-10

infinite_distance: float = 10000.0

voltage_tolerance: float = 1.0

hierarchical_linkage: str = 'complete'

__init__(zero_reactance_replacement=1e-05, regularization_factor=1e-10, infinite_distance=10000.0, voltage_tolerance=1.0, hierarchical_linkage='complete')

Parameters:

zero_reactance_replacement (float)
regularization_factor (float)
infinite_distance (float)
voltage_tolerance (float)
hierarchical_linkage (str)

Return type:

None

class npap.partitioning.va_electrical.VAElectricalDistancePartitioning[source]

Bases: PartitioningStrategy

Voltage-Aware Electrical Distance Partitioning.

This strategy partitions nodes based on electrical distance (PTDF) computed over the complete AC network (lines AND transformers), while enforcing voltage level boundaries as hard clustering constraints via post-processing.

Notes

Physical Rationale

In power systems, PTDF (Power Transfer Distribution Factor) describes how power injections affect line flows within an AC network. This strategy:

Computes PTDF for the complete AC network (lines + transformers) per AC island, capturing full electrical coupling including through transformers.
Post-processes distances to enforce voltage level separation: nodes at different voltage levels receive infinite distance, ensuring they never cluster together.
Transformer edges and buses at different voltage levels are set to infinite distance, preserving voltage hierarchy in the partitioning.

This approach is physically meaningful because:

The full PTDF captures how power flows through the entire AC network
Voltage level boundaries are then enforced as hard clustering constraints
Transformers become inter-cluster edges after aggregation

Constraint Hierarchy

AC Islands: Nodes in different AC islands have infinite distance (computed via separate PTDF matrices).
Voltage Levels: Nodes at different voltage levels have infinite distance (enforced via post-processing).

Algorithm

Group nodes by AC island
For each AC island:
1. Extract full AC subgraph (lines + transformers, exclude DC links)
2. Select ONE slack bus for the entire AC island
3. Compute PTDF including ALL AC elements
4. Calculate electrical distances from PTDF columns
Combine into full distance matrix with infinite inter-island distances
Post-process: Set infinite distance for node pairs at different voltage levels
Run clustering algorithm on the distance matrix

Supported Algorithms

kmedoids: K-Medoids clustering (works with precomputed distance matrices)
hierarchical: Agglomerative clustering with precomputed distances