# ConDPC: Data Connectivity-Based Density Peak Clustering
## 3 Proposed Algorithm
### Steps of the Proposed Algorithm  
The algorithm can be divided into three steps: (1) determine the connectivity relationship between points; (2) calculate \(\delta\) value according to the connectivity relationship and assign neighbors; (3) determine cluster centers and assign labels. Step 1: Determine the connectivity relationship between points. In the first step, connected groups are constructed to determine the connectivity between points. The algorithm idea is summarized, as shown in Algorithm 1. ```
Input: input dataset; cutoff distance Output: connected groups
1. Mark all points as ungrouped;
2. For each point \(i\) that has not been grouped
3. Create a new group G, mark point \(i\) as grouped in G, and add its directly connectable point set \(DNeis(i)\) to G;
4. For each point \(i\) in G that has not been grouped
5. Mark point \(j\) as grouped in G, and add its directly connectable point set \(DNeis(j)\) to G;
6. End For
7. End For
8. Return connected groups;
```  
**Algorithm 1** Calculate connected groups  
Step 2: Calculate \(\delta\) and neighbor assignment based on connectivity. The original algorithm does not consider the connectivity relationship between two points, directly calculates the distance between point \(i\) and its big neighbors, selects the minimumvalue as the \(\delta\) value of \(i\), and takes point \(j\) with the minimum distance as the neighbor of point \(i\). According to the connectivity relation, the proposed algorithm considers whether two points are connectable to each other when choosing neighbors and calculating neighbor distance. If there is a point with a higher density than point \(i\) in the connected group, that is, \(N-link_{i}\) is not empty, then the nearest point in \(N-link_{i}\) to point \(i\) is taken as its neighbor, and the distance between the two points is the neighbor distance of \(i\). If the density of point \(i\) in the connected group is the largest, then select the nearest point in \(N_{i}\) to point \(i\) as its neighbor, and the distance is updated to the maximum value of the distance between any two points. The formula for calculating \(\delta\) is adjusted as follows:  
\[\delta_{i}=\left\{ \begin{array}{l}\min(d_{i(N-link_{i})}),N-link_{i}\text{ \ is not }null\\ maxd,otherwise\end{array} \right. \tag{8}\]  
where \(maxd\) is the maximum value of the distance matrix. ```
Input: local density matrix; distance matrix; connected groups Output: \(\delta\) and neighbor assignment matrix
1. Sort all points in descending order of density;
2. For each point \(i\) that has no neighbors assigned
3. In the set \(N_{i}\) of all points with a density larger than point \(i\), if there is a subset \(N-link_{i}\) connectable to point \(i\) (that is, there are big neighbors of point \(i\) in the same connected group as \(i\)), select the point \(j\) closest to point \(i\) in \(N-link_{i}\) as the neighbor of point \(i\), and update \(\delta_{i}\) to \(d_{ij}\);
4. In the set \(N_{i}\), if there is no point connectable to point \(i\) (that is, there is no big neighbor in the same connected group as point \(i\)), select the point \(j\) closest to point \(i\) in \(N_{i}\) as the neighbor of point \(i\), and update \(\delta_{i}\) to the maximum value;
5. End For
6. Return \(\delta\) and neighbor assignment matrix;
```  
**Algorithm 2** Calculate \(\delta\) and neighbor assignment  
Step 3: Identifying cluster centers and Label assignment. ConDPC calculates the \(\gamma\) value based on the local density and neighbor distance calculated above. The decision graph is drawn to find the appropriate clustering centers. The remaining points are assigned to the corresponding clusters according to the neighbor assignment result obtained in Algorithm 2. The specific algorithm is described in Algorithm 3. ```
Input: input dataset Output: clustering result
1. Normalize the dataset;
2. Calculate distance matrix \(D^{n\times n}=\left\{d_{ij}\right\}^{n\times n}\);
3. Calculate the local density of each point according to Formula (1);
4. Call Algorithm 1 to obtain connected groups;
5.