# Similarity-Driven Edge Bundling: Data-Oriented Clutter Reduction in Graphs Layouts
## 4 Results and Evaluation
### Quantitative Analysis
#### 4.1.1 Backbone Evaluation  
To evaluate the quality of trees produces by the _Similarity Tree_ (_STree_) algorithm (see Section 3.1), we compare it with the Neighbour Joining (NJ) [34] and the UPGMA hierarchical clustering [32] since both present the same goal of distance preservation.  
In the first test, we assess the neighborhood preservation of the original space conveyed by the three different techniques. In other words, objects belonging to the same neighborhood should be closely linked in the tree. The neighborhood preservation of a data object \(d_{i}\) is calculated as follows: first we compute the \(k\)-nearest neighbours of \(d_{i}\), resulting on a list \(NN_{i}=\{d_{i_{1}},d_{i_{2}},\ldots,d_{i_{k}}\}\subset D\). Then, for each element \(d_{i_{j}}\in NN_{i}\) we compute how many tree nodes are necessary to traverse from the node representing \(d_{i}\) to the node representing \(d_{i}\) (the length of the path) using the selected technique and call it \(L_{i_{j}}\). The preservation of \(d_{i}\) is the median of \(L_{i_{j}}\), in which lower values indicate higher (local) distance preservation. We are evaluating the design principle \((1)\) (see Section 3.1), that is, well-constructed trees (_backbone_) are the ones that closely link the most similar objects, and consequently, result in a layout where similar objects are positioned close to each other.  
Figure 3a presents boxplots summarizing the neighborhood preservation comparing three techniques considering each dataset. The blue, gray, and orange boxplots represent the results obtained using the NJ, UPGMA, and STree techniques, respectively. These boxplots were obtained by varying the neighborhood size in the range \(k=[5,20]\), and computing \(L_{i_{j}}\) for each data object. On average, the neighborhood preservation attained by the STree is similar or better compared to what is produced by other more computationally expensive techniques (NJ is \(O(n^{3})\), UPGMA is \(O(n^{2})\), and the STree is \(O(n\log n)\)). Also, the deviation from the average is smaller, indicating that the structure produced by the STree is more stable and reliable since the degree of neighborhood preservation is uniformly distributed over the entire tree.  
Another critical aspect of a good _backbone_ is how balanced the tree structure is. Less intermediate vertices (on average) need to be traversed to go from one leaf (data vertex) to any other leaf on balanced trees. Therefore, resulting in visual representations containing less distorted edges since less bending is introduced (see Section 3.2.2). For the radial layout, this results in edges with uniform curvatures, avoiding long distorted edges. There is also a more consistent use of the available visual space, especially for the H-tree layout. The vertices are more uniformly distributed over the visualspace, reducing the visual clutter. Figure 3b presents the result comparing the balance of STree with the other techniques considering each data set. The blue, gray, and orange boxplots represent the NJ, UPGMA, and STree techniques. To compute the balance, for each data vertex (leaf), we calculate its depth from the root and divide by \(\log_{2}n\), where \(n\) accounts for the number of vertices. A tree's balance is then the average of the balance of its data vertices (leaves). The red line represents the results of a perfectly balanced tree (equals one). On average, the STree yields considerably more balanced trees, with results very close to the red line while the other techniques deviate from it.