## 2 Methodology
### Similarity  
There are many proposed methods in the literature to construct a similarity matrix for a graph, such as the inner product of feature vectors, the Gaussian similarity and the cosine similarity [25]. In our study, the goal is to define a similarity between each pair of links in the network that takes into account both homogeneity and spatial connectivity. Using this similarity measure, a fully connected graph is built in which one edge exists between every two nodes, meaning that every two snakes in the network are similar. The sequence of the links in a snake not only represents the links with the close speed values but also has some information about the spatial connectivity of the links. As the size of the snake grows, this measure of similarity gives less forget weight on the links that are collected. After some iterations, the snake does not have any good options to add and starts adding links with variant speeds leading to a higher variance. To further investigate, we plot the variance of the first and the second snake of the network of links (Figure 4). Based on these properties of the snake, we propose to put more weights on the links that are spatially closer to each other, and their corresponding snakes will converge to the same point [17]. Figure 3: Example of a snake initialized by a link in red. The green links represent the neighborhood, according to a 2D approach (**a**) and a 3D approach (**b**) [24]. In this case, we obtain a sparse similarity matrix. The snake similarity is defined as follows:  
\[ \begin{cases}w_{ij}=\frac{1}{\sum_{l=1}^{L}l\phi}\sum_{l=1}^{L}\phi^{l}card(T_{i} [l]\cap T_{j}[l]),\hskip 28.452756 pti,j=1,\ldots,N.\\ w_{ii}=0.\end{cases}  \tag{3}\]  
Note that:  
\[\sum_{l=1}^{L}l\phi^{l}=\frac{\phi(L\phi^{(L+1)}-(L+1)\phi^{L}+1)}{(1-\phi)^{2 }}\approx\frac{\phi}{(1-\phi)^{2}}, \tag{4}\]  
where \(T_{i}[l]\) and \(T_{j}[l]\) are \(l\)-size snakes corresponding to starting links \(i\) and \(j\), and \(card(T_{i}[l]\cap T_{j}[l])\) is the number of common link identifiers between the two snakes of size \(l\). The weight coefficient \(\phi\) is assigned by the user with \(0<\phi\leq 1\). The snake similarity matrix algorithm for the transportation network is given by Algorithm 1. ```
0:set \(\Gamma=\{l_{1},\ldots,l_{N}\}\) with \(N\) links (The same set \(\Gamma\) is used for both the links and the snakes). 1:while Link \(l_{i}\) is in the set of links do
2: Add the link \(l_{i}\) to the snake \(T_{i}\)
3:while length\((T_{i})<\) L do
4: find the adjacent link \(A\) of the snake \(T_{i}\), which has the closest variance to the average value of previously added links in that snake using Equation (1). 5: Add this link \(A\) to the snake \(T_{i}\). 6:endwhile
7:endwhile
8:while Snake \(T_{i}\) is in \(\Gamma\)do
9:while Snake \(T_{j}\) is in \(\Gamma\)do
10: Compute the similarity matrix \(w_{ij}\) based on Equation (3). 11:endwhile
12:endwhile
```  
**Algorithm 1** Snake Similarity Matrix Algorithm for the Transportation Network  
In order to prove the correctness of the algorithm, we consider a graph of links with a certain number of homogeneous regions with different levels of congestion in the graph. The links of one region have the same density or speed value. Each snake adds the adjacent link with the closest speed value to the average speed values of the links in the snake. Figure 4: Variance of two snakes of the graph of links. Snakes start from different links in each of these regions. They first integrate all the links in that region and then start adding from other regions with different levels of congestion. We can conclude, that after reaching this state, all the snakes within one component will show the same behavior. Moreover, they have many common links during their evolution before reaching the whole component. We use these features to define a similarity matrix constituted by the number of common link identifiers between the pairs of snakes.