## 2 Methodology
### Graph Models
#### 2.1.3 Graph of Snakes  
The graph of snakes is represented as a undirected graph \(G=(\Gamma,\Omega)\). The set of vertices \(\Gamma=\{T_{1},T_{2},\ldots,T_{N}\}\), where \(N=208\) represents the number of network snakes, and the set of edges \(\Omega\) represents the similarity between snakes. Although there is a one-to-one association between links and snakes, the same name \(\Gamma\) is used for both the links and snakes. The value of \(N\) is computed after coarsening the large-scale transportation network of Amsterdam and removing travel time outliers [17]. A snake is formed as a concatenation of a number \(L\) of adjacent links with similar speeds. Each snake is defined in an iterative process starting from an individual link in the graph.  
A snake is defined by \(T_{i}=\{t_{i1},\ldots,t_{il},\ldots,t_{iL}\}\), where \(1\leq\,l\,\leq\,L\), \(L\,\leq\,N\) is the size of the snake, \(t_{i1}=\{id,\
u\}\) is the link composed from an identifier \(id\) and a link speed \(\
u\), and \(t_{ik}\) and \(t_{ik+1}\) are connected links. The connected clusters' dissimilarity is used to evaluate the performance of the clustering algorithm for different values of \(L\)[17].  
For each of the links, we iteratively build a snake, which is a sequence of links, with the objective of having a minimum variance of all the chosen link speeds at each step. One can consider this as a snake that starts from a link and grows by attracting the most similar adjacent link iteratively (Figure 3). Figure 3 shows an example of a snake, initialized  
Figure 2: The two graph models are explained using two different examples. (**a**) The primal graph model, which consists of representing the intersections by nodes and the roads by edges. (**b**) The dual graph model, which consists of considering the roads as the graph nodes and the crossing point between them as edges.  
by a link in red. The green links represent the neighborhood, according to two- and three-dimensional approaches.  
Note that, at each step, the most similar link to the snake is the adjacent link with the closest speed value to the average speed values of the links in the snake. This procedure identifies interesting patterns as the variance grows with the size of the links. This observation is related to the fact that some parts of the graph are more similar than others, and if a large number of dissimilar links are added, high variance is unavoidable.  
Thus, in each step, each snake identifies all the adjacent links and adds the one that has the smallest variance value to the average value of previously added links in that snake. This procedure continues until the snake encompasses all the links in the network. The variance value of the snake at each step \(l\) can be computed by:  
\[\sigma_{l}^{2}=\sigma_{l-1}^{2}+\frac{1}{l}\left[(v_{l}-\overline{v}_{l})(v_{ l}-\overline{v}_{l-1})-\sigma_{l-1}^{2}\right], \tag{1}\]  
where  
\[\overline{v}_{l}=\overline{v}_{l-1}+\frac{1}{l}(v_{l}-\overline{v}_{l-1}), \tag{2}\]  
where \(\overline{v}_{l}\) denotes the mean speed of the snake at each step \(l\), and \(v_{l}\) is the speed of the link added in the \(l\)-th step.  
Clustering the snakes of links requires the construction of a weighted graph that encodes the similarity between data snakes. In the next section, we will explain how to build the snake similarity matrix.