## 2 Methodology
### Efficient Evolutionary Spectral Clustering Algorithm  
A major issue of the evolutionary spectral clustering algorithm is its computational and memory cost. If we denote by \(N\) the number of the data snakes at a given time, solving the eigenvalue problem has a complexity \(O(N^{3})\) and the \(N\times N\) evolutionary Laplacian does not fit into the main memory when \(N\) is large. To solve this problem, we define the following eigenvalue problem involving the smoothed Laplacian as follows [27]:  
\[L_{t}\;\mathbf{g}_{l,t}=\lambda_{l,t}\mathbf{g}_{l,t}, \tag{21}\]  
where  
\[L_{t}=D_{t}^{-\frac{1}{2}}W_{t}D_{t}^{-\frac{1}{2}}. \tag{22}\]  
This similarity matrix for PCQ is defined as:  
\[W_{t}=\alpha W_{t}+\beta W_{t-1}+...+\beta_{t-1}W_{1}. \tag{23}\]  
Notice that, in contrast to evolutionary spectral clustering, we consider all the previous time steps before the actual time point using an iterative process because of the low computation of the efficient evolutionary spectral clustering algorithm. However, the computation of the similarity matrix for PCM is not adopted for the efficient evolutionary spectral clustering algorithm. Thus, in the objective to make a comparative study with the PCM framework, we propose a similarity matrix for PCM defined as follows:  
\[W_{t}=\alpha W_{t}+D_{t}^{\frac{1}{2}}(\beta X_{t-1}^{T}X_{t-1}+...+\beta_{t- 1}X_{1}^{T}X_{1})D_{t}^{\frac{1}{2}}. \tag{24}\]  
The second term of the equation is multiplied by \(D_{t}^{\frac{1}{2}}\) in order to reduce the term \(D_{t}^{-\frac{1}{2}}\) to the identity matrix when the smoothed Laplacian is computed. To achieve the reduction of the eigenvalue problem, the similarity matrix \(W_{t}\) is replaced with its incomplete Cholesky decomposition (ICD) [28]. An ICD of a matrix \(W_{t}\in\mathbb{R}^{N\times N}\) allows us to compute a low-rank approximation of accuracy \(\tau\) of \(N\times N\) matrix \(W_{t}\), where \(||W_{t}-PP^{T}||<\tau\) with \(P\in\mathbb{R}^{N\times m}\), such that \(m\ll N\)The value of \(m\) is computed by the incomplete Cholesky decomposition algorithm [28]. The ICD selects the rows and columns of \(W_{t}\), which are called pivots considering that the ranks of approximation are close to the rank of the original matrix. The first step in solving the problem with efficient evolutionary spectral clustering is to reduce the eigenvalue problem of both PCQ and PCM. Thus, we obtain \(L_{t}\simeq D_{t}^{-\frac{1}{2}}PP^{T}D_{t}^{-\frac{1}{2}}\). After that, we replace \(D_{t}^{-\frac{1}{2}}P\) with its \(QR\) factorization and substitute \(R\) with its singular value decomposition. As a result, we will obtain the following equation:  
\[L_{t}\simeq QU_{R}(\Sigma_{R}^{2})U_{R}^{T}Q^{T}, \tag{25}\]  
where \(Q\in\mathbb{R}^{N\times m}\) and \(R\in\mathbb{R}^{m\times m}\) such that \(R=U_{R}\Sigma_{R}V_{R}^{T}\) and \(U_{R}\Sigma_{R}\), \(V_{R}\in\mathbb{R}^{m\times m}\). We have to solve an eigenvalue problem of size \(m\times m\), involving the matrix \(RR^{T}\) that is smaller than the size \(N\times N\) of the original problem. In addition, the eigenvectors problem can be estimated as \(g_{l}=QU_{R,l}\), where the related eigenvalues are \(\lambda_{l}=\sigma_{R,l}^{2}\). At last, the cluster assignment for the \(i\)th data points are obtained from the pivoted LQ factorization of matrix \(G=[g_{1},...,g_{K}]\):  
\[C_{i}=argmax_{l=1,..,K}(|X_{il}|)\text{ where }X=YLQ_{G}, \tag{26}\]  
such that \(Y\in\mathbb{R}^{N\times N}\) is a permutation matrix as defined in [27], \(L\in\mathbb{R}^{N\times K}\) is a lower triangular matrix, and \(Q_{G}\in\mathbb{R}^{K\times K}\) is the unitary matrix. The classic ICD algorithm is based on the supposition that the Laplacian matrix has a small rank. A new stopping criterion assumes that the cluster assignments tend to converge after selecting each pivot. Therefore, for the cluster assignments \(\mathbf{C^{s}}\) at step \(s\) and \(\mathbf{C^{s-1}}\) at step \(s-1\big{(}\) with \(C^{s}=\big{[}C_{1}^{s},\ldots,C_{N}^{s}\big{]}\big{)}\), the normalized mutual information (NMI) is calculated.