# DELER: Distributed Clustering with Local Direction Centrality and Density Measure
## 1 Introduction  
Cluster analysis is a fundamental task in data mining [1], which involves partitioning data based on similarity without the need for labeled data. It has been widely applied in various fields, including image analysis [2, 3], information retrieval [4, 5], data compression [6, 7], disease diagnosis [8, 9], path planning [10], bioinformatics [11, 12, 13], and so on. Recently, [PERSON], [PERSON], and [PERSON]. [14] proposed a clustering method based on local direction centrality (Clustering by Measuring Local Direction Centrality, CDC), which has attracted considerable attention from researchers. The CDC method uses the Direction Centrality Metric (_DCM_) index to quantify the direction centrality of each data point \(o\). The _DCM_ value is essentially the variance of the \(k\) angles formed by point \(o\) and its \(k\)-nearest neighbors. A larger _DCM_ value indicates that the distribution of the \(k\)-nearest neighbors of point \(o\) is more uneven, suggesting that point \(o\) is likely situated on the edge of a cluster (and is hence referred to as a boundary point). Conversely, a smaller _DCM_ value suggests that point \(o\) is more likely to be located within the interior of a cluster (and is thus referred to as an interior point). As illustrated in Figure 1, \(p_{1}\), \(p_{2}\), \(p_{3}\), \(\ldots\), \(p_{k}\) represent the \(k\)-nearest neighbors of point \(o\), with the lines connecting \(o\) to these \(k\) points forming \(k\) angles. The variance of these \(k\) angles defines the _DCM_ value of \(o\), denoted as \(DCM_{o}\). In the case where the \(k\)-nearest neighborsare predominantly located on one side of point \(o\), the distribution is uneven, leading to a higher _DCM_ value and consequently a higher likelihood of point \(o\) being a boundary point. After determining the interior and boundary points based on the _DCM_ value, the CDC method separates the interior points into distinct groups, which are then divided by the boundary points. Groups of interior points that are not separated by boundary points are treated as belonging to the same cluster, and boundary points are assigned to the cluster of the nearest interior point, thus forming the final clustering result. Given a dataset \(P\) containing \(n\) data points \(\{p_{1},p_{2},\ldots,p_{n}\}\), the Direction Centrality Metric (_DCM_) is calculated for each data point \(p_{i}\) to evaluate its centrality within the cluster. A smaller _DCM_ value indicates that the data point is closer to the cluster center, while a larger _DCM_ value suggests proximity to the cluster's edge. For example, as illustrated in Figure 2, _DCM_ can be used to distinguish between interior and boundary points. Data points marked in purple have a relatively uniform distribution of neighboring points, resulting in a smaller variance in the angles between neighbors and thus a lower _DCM_ value, classifying them as interior points. In contrast, data points marked in green exhibit an uneven distribution of neighboring points skewed toward one side, leading to greater variance in neighboring angles and a higher _DCM_ value, identifying them as boundary points. While the CDC algorithm has demonstrated notable success, it remains challenged by issues in two critical areas, which undermine its effectiveness and efficiency:  
* The Challenge In Terms Of Effectiveness: The _DCM_ metric has both advantages and disadvantages. Replacing the density measure with the variance of \(k\)-nearest neighbor angles can address the shortcomings of density-based algorithms in identifying sparse clusters. However, this approach may lead to weak connectivity issues, where two high-density regions are mistakenly identified as a single region due to the presence of low-density connecting areas. As illustrated in Figure 3, points of different colors belong to different clusters, the CDC algorithm successfully identifies the green  
Figure 1: Illustration of boundary points. Figure 2: Scatter plot of weak connectivity.