## 2 Methodology
### Evolutionary Spectral Clustering
#### 2.4.2 Preserving Cluster Membership (PCM)  
Consider that two partitions, \(Z_{t}\) and \(Z_{t}^{\prime}\), cluster the data at time period \(t\) equally well. However, when compared with the historic partition \(Z_{(t-1)}\), \(Z_{t}\) is preferred because it is more consistent with the historic partition. This idea is formalized by [18]:  
\[TotalCost=\alpha\,NC_{t}|_{Z_{t}}+(1-\alpha)\,TC, \tag{13}\]  
where \(NC_{t}|_{Z_{t}}\) is the snapshot cost. The temporal cost TC is expressed as the difference between the clustering result at time period \(t\) and the clustering result at time period \((t-1)\). One solution is the norm of the difference between the two projection matrices, which is expressed as:  
\[TC=\frac{1}{2}\left\|X_{t}X_{t}^{T}-X_{t-1}X_{t-1}^{T}\right\|^{2}, \tag{14}\]  
where \(X_{t}\) and \(X_{t-1}\) are the sets of top K-eigenvectors at time period \(t\) and \(t-1\), respectively. In this case, the evolutionary total cost can be expressed by:  
\[TotalCost =\alpha\,K-\alpha\,Tr\Big{[}X_{t}^{T}\Big{(}D_{t}^{-1/2}W_{t}D_{t }^{-1/2}\Big{)}\,X_{t}\Big{]} \tag{15}\] \[+\frac{(1-\alpha)}{2}\left\|X_{t}X_{t}^{T}-X_{t-1}X_{t-1}^{T} \right\|^{2}\] \[=K-Tr\Big{[}X_{t}^{T}\Big{(}\alpha\,D_{t}^{-1/2}W_{t}D_{t}^{-1/2} +(1-\alpha)\,X_{t-1}X_{t-1}^{T}\Big{)}\,X_{t}\Big{]}.\]  
The PCM framework consists of finding the optimal solution that minimizes the total cost. This problem can be converted to a trace maximization, where the solution is the matrix \(X_{t}\) whose columns are the top K-eigenvectors associated with the top K-eigenvalues of the evolutionary Laplacian matrix [18]:  
\[L_{pcm}=\alpha\,(D_{t}^{-1/2}W_{t}D_{t}^{-1/2})+(1-\alpha)\,(X_{t-1}X_{t-1}^{ T}). \tag{16}\]  
The final clusters can be attained by projecting data into \(span(X_{t})\) and then applying the K-means algorithm to obtain the final clusters. The two proposed frameworks can handle any variations in the number of clusters. In the PCQ framework, the temporal cost is only expressed by historic data, not by historic clusters, and therefore the computation at the current time is independent of the number of clusters at the previous time. Moreover, the PCM framework can be used without change when the partitions have a different number of clusters. In comparing the Laplacian graphs of both frameworks, we can see that they differ in terms of how they measure the historic partition. \(L_{pcq}\) and \(L_{pcm}\) have in common the first term, which refers to the current data expressed by the symmetric Laplacian at time \(t\). The difference between these two is found in the second term. For the PCQ framework, it is equal to the symmetric Laplacian at time \(t-1\), whereas for the PCM framework, it is expressed by the set of eigenvectors \(X_{t-1}X_{t-1}^{T}\) at time \(t-1\). The evolutionary spectral clustering algorithm for the transportation network is given by Algorithm 2. ```
0: Similarity matrix \(W\in\mathbb{R}^{N*N}\), Number of \(K-\) clusters to construct. 1: Compute the degree matrix \(D(i,i)=d_{i}\) for all \(1\leq i\leq N\). 2: Compute the Laplacian \(L\) matrix for PCQ or PCM using Equations (16) or (12). 3: Solve the the eigen equation \(Lu=\lambda u\). 4: Find the K top eigenvalues \(\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{K}\) and their corresponding eigenvectors \(u_{1},\cdots,u_{K}\) of \(L\). 5: Compute \(U\in\mathbb{R}^{N*K}\) as a matrix containing the vectors \(u_{1},\cdots,u_{K}\) as columns. 6: Create the Matrix \(U^{\prime}\) in \(\mathbb{R}^{N*K}\) from \(U\) by normalizing the rows by the norm 1. 7:for i=1,...,N do
8: let \(y_{i}\in\mathbb{R}^{K}\) be the normalizing vector corresponding to the \(i\)th row of \(U^{\prime}\). 9:endfor
10: Cluster the data points \((y_{i})_{i=1,\cdots,N}\) in \(\mathbb{R}^{K}\) with the K-means algorithm to obtain clusters \(C_{1},..,C_{K}\). ```  
**Algorithm 2** Evolutionary Spectral Clustering Algorithm  
We explain the steps of the evolutionary spectral clustering algorithm by considering the following example. Figure 6 shows two graphs at time periods \(t-1\) and \(t\).