# Applying Spectral Clustering to Decode Mobility Patterns in Athens, Greece
## 2 Data and Methods
### Spectral Clustering Analysis
After creating the distance matrix, the computation of the similarity matrix follows. To do so, the Gaussian similarity function is utilized (see Equation (2)). This mathematical process requires the definition the parameter \(\sigma\). This parameter gives the similarity scale between points and determines the influence that one point has on others in terms of similarity. A common practice for calculating \(\sigma\) is to use the median of the distances between all pairs of points in the dataset. This method provides a good balance as the median represents a central tendency of the distances, avoiding extreme values that could distort the scale of similarity. \[S(p,q)=exp\left(-\frac{d(p,q)^{2}}{2\sigma^{2}}\right) \tag{2}\]  
where  
\(S(p,q)\): similarity level between trip \(p\) and \(q\),  
\(\sigma\): scale parameter; in this case, it is equal to the median of Manhattan distances  
In the third step, the Laplacian matrix is constructed. Initially, a degree matrix was created by calculating the sum of each row of the similarity matrix and placing these sums on the diagonal of a diagonal matrix. The degree matrix is a diagonal matrix where each diagonal element represents the degree of point \(p\), i.e., the sum of the similarity values of all edges connected to this point:  
\[d_{p}=\sum_{q=1}^{Q}S(p,q) \tag{3}\]where  
\(d_{p}\): the degree of trip \(p\),  
\(Q\): the total trips included in the set  
The next step is computing the Laplacian matrix by subtracting the similarity matrix from the degree matrix, as shown below:  
\[L=D-S \tag{4}\]  
where  
\(D\): the degree matrix  
\(S\): the similarity matrix  
\(L\): the Laplacian matrix  
Through the Laplacian matrix, the eigenvalues and eigenvectors of the matrix were calculated. The Laplacian matrix is symmetric, ensuring optimal performance of the calculations. From the set of eigenvectors, the first (smallest) k eigenvectors were selected, where k is the number of desired clusters. The eigenvectors were chosen based on their eigenvalues and used to transform the data into a new space with fewer dimensions. This transformation ensures that closely situated points fall within the same cluster, while those distanced from each other are categorized into separate clusters. Subsequently, the rows of the matrix containing the selected eigenvectors were normalized so that each row has unit length. This assists in preparing the data for clustering. Finally, the normalized data were clustered using the k-means method, as presented above. The algorithm was executed on the normalized data with centers being the selected k smallest eigenvectors of the Laplacian matrix. Both the Gap Statistic Method and Silhouette scores were utilized to determine the optimal number of clusters and to iterate the process as needed. In the first method, this achieved by comparing the within-cluster variation in the actual data to the expected variation from a null reference distribution. This distribution represents random data without any inherent structure [33]. In the second method, the selection of the optimal number of clusters is performed by estimating the Silhouette score [34]. Equation (5) gives its formula. A rate close to +1 indicates that the data point is well placed within its cluster, while a score close to \(-1\) suggests that the data point is misclassified. \[SL(q)=\frac{\beta(q)-a(q)}{\max(a(q),\beta(q))} \tag{5}\]  
where  
\(SL(q)\): the Silhouette score of trip \(q\),  
\(a(q)\): the average distance (similarity level) between a point \(q\) and all the points in the same cluster  
\(\beta(q)\): the average distance (similarity level) between a point \(q\) and all the points in the nearest different cluster.