## 4 Design of a Capacity-Constrained Weighted Clustering Algorithm
### Network Partition
Where K represents the number of clusters to be partitioned, and \(N_{\text{max}}\) denotes the maximum capacity limit for each partition, both of which can be pre-set according to the actual task requirements. The algorithm achieves balanced control of cluster sizes by using a distance-based sorting method and a dynamic capacity relaxation strategy, ensuring allocation quality while maintaining balance. The pseudocode of the capacity-constrained partitioning algorithm is listed in Algorithm 1. In Algorithm 1, the analysis of time and space complexity is mainly divided into three stages: the initial partition center selection stage, the preliminary node allocation stage, and the dynamic allocation relaxation stage. In the initial partition center selection stage, K-means++ is used to select \(k\) centers from \(n\) nodes, with a time complexity of \(O(kn)\). In terms of space, it is necessary to maintain the cluster center index array, so the space complexity is \(O(k)\). In the preliminary node allocation stage, the first step is to settle the distance to the nearest center for all nodes, with a time complexity of \(O(kn)\). Then, sort the nodes based on distance, with a time complexity of \(O(n\log n)\). Finally, perform linear scan allocation on the nodes with a time complexity of \(O(n)\). So the total time complexity of this stage is \(O(kn+n\log n)\). In terms of space, it is necessary to maintain the distance array from the node to the nearest center and allocate the result array, so the space complexity is \(O(n)\). In the dynamic allocation relaxation stage, a constant number of allocation processes are executed for unallocated \(u\) nodes, so the time complexity of this stage is \(O(ku)\). In terms of space, it is necessary to maintain a node allocation state array, so the space complexity is \(O(n)\). Overall, for the capacity-constrained partitioning algorithm based on K-means++, the time complexity is \(O(kn)+O(kn+n\log n)+O(ku)=O(kn+n\log n+un)\), and the space complexity is \(O(k)+O(n)+O(n)=O(k+n)\). ```
Input: Total number of nodes \(numNodes\), number of partitions \(numClusters\), maximum number of nodes per partition \(maxNodes\), relaxation of constraints relaxation, maximum constraint relaxation \(maxRelaxation\) Output: Partition set \(P=\{partition_{1}\), \(partition_{2}\), \(\ldots\), \(partition_{numClusters}\}\) //K-means++ initialization 1 Randomly select a node as the first partition center fork = 2 to \(numClusters\)do 3 Select the next partition center based on distance endfor //Preliminary Node Allocation 5 Calculate the distance from each node to the nearest cluster center 6 Sort nodes by distance from smallest to largest in \(sortedNodeIndices\)[] forj = 1 to \(numNodes\)do \(i=sortedNodeIndices(j)\) Get the target partition 10 ifnumber of nodes in partition <\(maxNodes\)do 11 Allocate node \(i\) to the partition 12 endif if 13 endfor //Dynamic relaxation of allocation 14 ifunallocated nodes exist and \(relaxation\leq maxRelaxation\)do 15 Allow the number of nodes per partition to be \(maxNodesPerCluster\) + relaxation Attempt to reassign unallocated nodes again ifthere are still unallocated nodes do \(relaxation=relaxation+1\) endif endif endif returnPartition set \(P=\{partition_{1}\), \(partition_{2}\), \(\ldots\), \(partition_{numClusters}\}\)
```  
**Algorithm 1**Capacity-constrained partitioning algorithm based on K-means++