# Dual Clustering-Based Method for Geospatial Knowledge Graph Partitioning
## 2 Methods
### Discovery of Graph Structure Based on Graph Clustering  
To avoid tightly connected nodes being assigned to different partitions, we further used a graph clustering method to identify the graph structure from the coarse graph obtained by Section 2.1, which can find the closely connected groups of nodes. Based on the graph structure, the coarse graph can be further comprised. Constructing partitions according to closely connected groups will be helpful for minimizing the number of cut edges or duplicated nodes. In this study, we use the Leiden algorithm [55] on the coarse graph to comprise the clustering result obtained by DPC. The Leiden algorithm was introduced by [PERSON] et al. [55] as an improvement over the Louvain algorithm [56]. The Leiden algorithm is one of the most advanced community detection algorithms in recent years and has been shown to achieve state-of-the-art performance on many graphs [57].  
The Leiden algorithm requires a pre-defined function to evaluate the quality of communities. GKGP-DC adopts modularity as the quality function for evaluating communities. Given a weighted graph \(G\) and a partition \(C=\{C_{1}C_{2},\ldots C_{n}\}\), the modularity is calculated as follows:  
\[Q=\frac{1}{2m}{\sum_{i,j}}\left[w_{ij}-\frac{K_{i}K_{j}}{2m}\right]\delta(C_{ i},C_{j}) \tag{3}\]  
Based on the definition of quality function of communities and the graph aggregated from the DPC results in Section 2.1, the Leiden algorithm is applied to detect community structures with tight internal connections and loose external connections. The graph is further aggregated based on these community structures. The detailed steps of the algorithm are as follows:  
Figure 4: Node agglomeration based on DPC.  
Figure 3: Decision diagram of DPC.  
(i) **Local Movement of Nodes.** Initially, each node is considered as a separate community (Figure 5a). Then, each node is moved to the community that yields the largest modularity gain (Figure 5b). In this phase, the Leiden algorithm uses a fast local movement strategy, only accessing nodes whose neighbors have moved to other partitions. This strategy enables the algorithm to perform local moves quickly and efficiently. The modularity gain from moving node \(i\) from community \(C_{j}\) to community \(C_{s}\) (where j \(\
eq\) k) can be calculated as follows:  
\[\triangle Q_{i}=\frac{1}{2m}\Big{[}K_{i,s}-K_{i,j}+\frac{K_{i}}{m}\big{(} \sum j,tot-\sum s,tot-K_{i}\big{)}\Big{]} \tag{4}\]  
where \(K_{i,s}\) and \(K_{i,j}\) represent the total weight of edges between node \(i\) and nodes in communities \(C_{s}\) and \(C_{j}\), respectively. \(\sum j,tot\) and \(\sum s,tot\) is the total weight of edges in \(C_{s}\) and \(C_{j}\), respectively. \(m\) denotes the total weight of all edges.  
(ii) **Refinement of Partitions.** After local movement, each node within a partition is treated as a separate community, and community merging is performed within each partition (Figure 5c). This merging does not necessarily maximize modularity gain but allows the random selection of a community that increases modularity. The larger the modularity increase, the higher the likelihood of selecting that community for merging. The randomness in selecting communities allows a broader exploration of the partitioning space and also accelerates the algorithm.  
(iii) **Graph Aggregation Based on Refined Partitions.** The graph is aggregated based on the refined partitioning results obtained by step (ii). Nodes in each partition are merged into a single node, and the corresponding edges are merged into a single edge (Figure 5d). The node weights are updated as the sum of the weights of the nodes in the partition, and the edge weights are set to the sum of the weights of the parallel edges. Then, step (i) and step (ii) are repeated on the aggregated graph (Figure 5e). The iteration will not stop until modularity can no longer be improved, and the graph will be the final result (Figure 5f).