# Evolutionary Features for Dynamic Link Prediction in Social Networks
## 2 Dynamic Similarity Metrics
### Dynamic Features
#### 2.2.1 Temporal Similarity  
In time series clustering, to measure the similarity between temporal sequences with varying speeds, existing distance measures (i.e., Euclidean, Manhattan) produce un-intuitive results and demonstrate incompetency in producing optimal alignment. For example, the Euclidean technique simply measures the distance between a pair of time series by summing the squared distances from each point in one-time series to the corresponding point in the other. If the pair are identical, with one being shifted along the time axis, Euclidean distance may consider totally different time sequences. The dynamic programming-based method of Dynamic Time Warping (DTW) overcomes the aforementioned limitation of traditional distance measures to provide intuitive distance measurements between temporal sequences by ignoring both global and local deviations in the time dimension [45]. It measures the similarity between two time series by shrinking or expanding or simply \"warping\" the time axis of one (or both) sequences to achieve better alignment. This warping technique is an example of dynamic programming that can be used to determine corresponding regions between two time series to measure their similarity. Let \(X^{a}\) and \(Y^{b}\) be the time series of length \(|m|\) and \(|n|\) considering the chosen dynamicity measure, described earlier in Section 2.1 (i.e., structural and neighbourhood dynamicity), for actors \(a\) and \(b\), where \(m,n\leq N\), and \(N\) is the total number of SINs. If \(d(x_{i},y_{j})\) denotes local distance measure (e.g., Euclidean, Minkowski), defined to compare two different points in \(X^{a}\) and \(Y^{b}\), then the goal of the DTW technique is to find an optimal alignment between \(X^{a}\) and \(Y^{b}\) with minimum overall distance. Details of this technique can be found in the study by [PERSON] [46]. The notion of this alignment depends on the definition of an \((m,n)\)-warping path which is a sequence \(p=p_{1},p_{2},p_{3},\ldots,p_{l}\) with \(p_{l}=(m_{l},n_{l})\in[1:m]x[1:n]\) for \(l\in[1:L]\), where \(L\) denotes the length of warping path. The optimal warping path between \(X^{a}\) and \(Y^{b}\) is defined as a warping path \(p^{*}\) with the minimum distance among all possible warping paths. To accomplish that, it may encounter that a single point in one time series may be mapped to multiple points of the other. The optimal warping path is determined by following a dynamic programming method that recursively measures the following function at every step:  
\[\gamma(i,j)=d(x_{i},y_{i})+min[(\gamma(i-1,j-1),\gamma(i-1,j),\gamma(i,j-1))] \tag{4}\]  
Here, \(\gamma(i,j)\) represents the optimal warping path defined between the \(i\)th and \(j\)th component of two time series. In Figure 2, this study presents a comparable representation of calculating similarities between two temporal sequences using traditional distance measures (Figure 2a) (e.g., Euclidean) and the DTW method (Figure 2b). In this figure, the dashed lines represent the distance between corresponding points in both time series. The traditional approach aligns the \(i\)th point in one time series with the corresponding \(j\)th point of the other, whereas DTW provides nonlinear alignment to produce a more intuitive similarity measure and allows similar shapes to match (\(i\to j\), \(j+1\)) even if it requires localized stretching along the time axis. In DTW, the difference between these time series is the warped path distance which is measured by summing the distances between each pair of points connected by the dashed lines in the figure. Considering the temporal similarity measures using the DTW technique, this study first computes the structural and neighbourhood dynamicity of actor pairs at every timestamp of temporal network snapshots. Secondly, using temporal sequences of these dynamicity values, this study applied the DTW technique to measure temporal similarity between them.