# Common Nearest Neighbor Clustering--A Benchmark
## 3 Materials and Methods  
### Common Nearest Neighbor Algorithm  
The CNN algorithm [4] is a density-based cluster algorithm that yields a strict partitioning with outliers. CNN clustering depends on two parameters: the radius of the neighborhood \(R\) and the number of common nearest neighbors \(N\). \(R\) determines the neighborhood of a data point \(\mathbf{x}_{i}\); that is, all data points that are closer than this distance are the nearest neighbors of \(\mathbf{x}_{i}\) (Figure 4). Two data points \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) are density-reachable if they share at least \(N\) nearest neighbors. This condition serves as an approximation of the local data-point density in the region between the two data points (Figure 4b). Data points that are density-reachable from each other always belong to the same cluster. It is important to point out that not all nearest neighbors of \(\mathbf{x}_{i}\) are necessarily density-reachable from \(\mathbf{x}_{i}\). This is, for example, the case if no data points are located in the overlapping region of the two neighborhoods (Figure 4c). We consider a situation in which data point \(\mathbf{x}_{j}\) is density-reachable from \(\mathbf{x}_{i}\) and data point \(\mathbf{x}_{k}\) is density-reachable from \(\mathbf{x}_{i}\) but data points \(\mathbf{x}_{j}\) and \(\mathbf{x}_{k}\) are not density-reachable from each other. In CNN clustering, all three data points belong to the same cluster. In fact, the cluster is iteratively extended by adding data points that are density-reachable by at least one of the current cluster members. Thus, a given cluster member is not necessarily density-reachable from all other cluster members, but it must be density-connected to all other cluster members. Two data points are density-connected if they are connected via a sequence of density-reachable data points (Figure 4f). As a consequence, the algorithm can identify clusters of arbitrary shapes and sizes. The following is the CNN cluster algorithm:  
Choose \(R\) and \(N\). **Cluster initialization:** Choose an arbitrary data point \(\mathbf{x}_{i}\) from the set of unclustered data points \(U\) as the first member of the cluster \(C\). Set \(\mathbf{x}_{i}\) to \(\mathbf{x}_{\text{current}}\) (first line in Figure 4g). **Cluster expansion:**  
1. Add any unclustered data point within \(2R\) of \(\mathbf{x}_{\text{current}}\), which fulfils the density criterion with respect to \(\mathbf{x}_{\text{current}}\), to the cluster \(C\) (second line in Figure 4g) and remove it from \(U\). Keep a list \(L\) of the newly added data points. Figure 3: Molecular dynamics (MD) simulation trajectory of [PERSON] [33] (**a**) projected onto the first two principle components. Each core set (highlighted in different colors) represents a minimum of the potential energy surface spanned by the principle components and is linked to (**b**) a metastable state. (The core sets were identified by common nearest neighbor clustering, where the distance metric was the Euclidean distance in the space spanned by the first two principle components. A preprocessing of the MD dataset by principle component analysis is however not strictly necessary [4; 24]). (**c**) Distance distribution of the distance Met260-Gly290 (highlighted in (**b**) by orange spheres). 2. Choose a data point \(\mathbf{x}_{j}\) from \(L\) and set \(\mathbf{x}_{j}\) to \(\mathbf{x}_{\text{current}}\). 3. Repeat steps (a) and (b) until no further data point can be added to \(C\) (third and fourth line in Figure 4g). 4. Save \(C\) to file and reset \(C\) to an empty list \(C=\{\}\). 3. Repeat steps 1 and 2 until all data points are assigned to a cluster. We note that the CNN algorithm is not an optimization algorithm; it is a cluster growing algorithm [36]. The cluster memberships are completely defined by the parameters \(R\) and \(N\), which stay constant over the complete clustering. All data points that are density-connected will be assigned to one cluster (steps 1 and 2 in the described procedure).