## 2 Methodology
### Efficient Evolutionary Spectral Clustering Algorithm
The time step \(s\) is used for an iterative process of the algorithm. The NMI is defined by [29]:  
\[NMI(C^{s},C^{s-1})=\frac{MI(C^{s},C^{s-1})}{\sqrt{H(C^{s})H(C^{s-1})}}, \tag{27}\]  
where the mutual information between the partitions \(C^{s}\) and \(C^{s-1}\) is defined as:  
\[MI(C^{s},C^{s-1})=\sum_{l=1}^{K}\sum_{l=1}^{K^{\prime}}\frac{n_{il}}{N}log \Bigg{(}\frac{n_{il}N}{|C_{i}^{s}|C_{l}^{s-1}|}\Bigg{)}, \tag{28}\]  
The term \(n_{il}\) represents the number of shared patterns between the clusters \(C_{i}^{s}\) and \(C_{l}^{s-1}\), and \(K^{\prime}\) is the number of clusters in partition \(C^{s-1}\). The entropy of the partition \(C^{s}\) is defined as:  
\[H(C^{s})=-\sum_{i=1}^{K}\frac{|C_{i}^{s}|}{N}log\Bigg{(}\frac{|C_{i}^{s}|}{N} \Bigg{)}. \tag{29}\]  
A higher NMI value means that the clustering algorithms generate identical partitions. The NMI value is bounded in (0,1), equaling 1 when the two partitions are identical and 0 when they are independent. Consequently, the ICD algorithm terminates when \(|NMI-1|<THR\), where \(THR\) is a user-defined threshold value. To make this procedure faster, we need to check the convergence of the cluster assignments only when the approximation of the similarity matrix is good enough. Thus, we stop the computation when the quality of the approximation of the similarity matrix is greater than a predefined threshold as follows:  
\[\text{min}(\tilde{\mathbf{d}})/\text{ max}(\tilde{\mathbf{d}})>THR_{deg}, \tag{30}\]  
where  
\[L_{t}=D_{t}^{-\frac{1}{2}}W_{t}D_{t}^{-\frac{1}{2}}. \tag{22}\]0Finally, to prevent the termination of the ICD algorithm too early with the poor and insufficient performance of clusters, we choose \(THR_{deg}=THR=10^{-6}\), which is a suitable choice through experiences. As a result, this criterion decreases the number of selected pivots and improves the computational complexity. This methodology outperforms the evolutionary spectral clustering and the normalized spectral clustering algorithm that is denoted by IND, which independently applies the spectral clustering algorithm on the speed of road segments in only the time step t and ignores all the historic data before t.  
It is shown that the computational complexity of the efficient evolutionary spectral clustering algorithm is \(O(N)\)[27]. On the other hand, the methods of the evolutionary spectral clustering have a complexity of \(O(N^{3})\) as a result of the fully eigen decomposition of the \(N\times N\) similarity matrices that are included at each time \(t\). Consequently, this method is an effective tool for dealing with large-scale clustering problems with a time complexity of \(O(N)\). The efficient evolutionary spectral clustering algorithm for the transportation network is given by Algorithm 3. ```
0: Similarity matrices \(\left\{W_{t}\right\}_{t=1}^{T}\in\mathbb{R}^{N^{t}\times N^{t}}\), thresholds \(\mathrm{THR}\) and \(\mathrm{THR}_{deg}\). 1:for t=2,...,T do
2: Compute the matrix \(W_{t}\) (Equations (23) and (24)), initialize the matrix \(P\) to zero and the matrices \(\mathbb{C}^{0}\) and \(Y\) to one. 3: Compute the number of clusters using density peaks. 4:while\(|\mathrm{NMI}^{s}-1|<THR\)do
5: Start incomplete Cholesky decomposition and update the matrices \(Y\), \(P\) and \(W_{t}\)[27; 28]. 6: Compute d using Equation (31). 7: Compute \(r_{\mathrm{deg}}=\frac{\min(\mathrm{d})}{\max(\mathrm{d})}\). 8:if\(r_{deg}>THR_{deg}\)then
9: Calculate the \(QR\) decomposition of \(\bar{D}^{-\frac{1}{2}}P\). 10: Evaluate the singular value decomposition of \(R=U\Sigma V^{T}\). 11: Obtain the approximated eigenvectors through \(\hat{G}=QU_{R,1:\max k}\). 12: Evaluate \(LQ\) factorization with row pivoting as \(D_{\hat{G}}\hat{G}=\Sigma LQ_{\hat{G}}\). 13: Compute cluster assignment for a data snake (Equation (26)). 14: Save the current assignments for the \(N\) data snakes in a vector \(\mathbb{C}^{s}\). 15: Calculate \(\mathrm{NMI}^{s}=\mathrm{NMI}\big{(}\mathbb{C}^{s-1},\mathbb{C}^{s}\big{)}\) according to the Equation (27).