# Similarity-Driven Edge Bundling: Data-Oriented Clutter Reduction in Graphs Layouts
## 3 Similarity-Driven Edge Bundling (SDEB)
### Backbone Construction
To create such a _backbone_, we adapt the bisecting k-means strategy [35] algorithm to construct a binary tree where the data vertices are iteratively split into clusters and sub-clusters, defining a similarity hierarchy. It starts with one cluster \(C\) containing all data objects, representing the _backbone_ root. Then, \(C\) is split into two new (sub)clusters \(C_{a}\) and \(C_{b}\), so that each contains the most similar data objects between themselves, minimizing  
\[\sum_{d_{i}\in C_{a}}\delta(d_{i},\tilde{C}_{a})+\sum_{d_{j}\in C_{b}}\delta( d_{j},\tilde{C}_{b})\, \tag{1}\]  
where \(\tilde{C}_{a}\) and \(\tilde{C}_{b}\) represents the centroids of \(C_{a}\) and \(C_{b}\), respectively, calculated as  
\[\tilde{C}_{i}=\frac{1}{|C_{i}|}\sum_{d_{j}\in C_{i}}d_{j}\, \tag{2}\]  
where \(|C_{i}|\) represents the number of objects in \(C_{i}\). Once \(C_{a}\) and \(C_{b}\) are computed, they are attached as left and right children of \(C\), and the same process is recursively applied to them. This splitting process continues until singleton clusters, clusters containing only one data object, are created. The _backbone_ tree structure is then extracted from this hierarchy of (sub)clusters considering each non-singleton cluster centroid an intermediate vertex linked to its parent intermediate vertex or (sub)cluster centroid. The singleton clusters centroids are the leaves of this structure and represent the data vertices. The process for the backbone construction is outlined on Algorithm 1. It receives a data set \(D\) and though a recursive linking and splitting process, where more compact clusters are generate after each split, returns a tree \(T\) that obeys the previously mentioned design principles. In this algorithm, the function \(\textsc{Centroid}(C)\) returns the centroid of \(C\) (see Equation (2)), and the function \(\textsc{Pivots}(C)\) first calculates the centroid \(\tilde{C}\) of \(C\) then finds the further data object \(d_{a}\in C\) from \(\tilde{C}\) as the first pivot and the further object from \(d_{a}\) as the second pivot \(d_{b}\). ```
functionSimilarityTree(\(D\)) \(C\leftarrow\{d_{1},\ldots,d_{n}\}\in D\)\(\triangleright\)assign all data objects/vertices to the first cluster \(C\)\(T\).root\(\leftarrow\textsc{Centroid}(C)\)\(\triangleright\) create a tree \(T\) and set its root as the centroid of \(C\) (first intermediate node) \(\textsc{SimilarityTreeRec}(C,T\).root\()\)\(\triangleright\) generate the complete tree return\(T\) endfunctionfunctionSimilarityTreeRec(\(C,v^{\prime}\)) if\(|C|>1\)then\(\triangleright\) If the input cluster \(C\) has more than one data object \(\{C_{a},C_{b}\}\leftarrow\textsc{Split}(C)\)\(\triangleright\) split \(C\) into two clusters \(v^{\prime}.left\leftarrow\textsc{Centroid}(C_{a})\)\(\triangleright\) set the left child of \(v^{\prime}\) as the centroid of \(C_{a}\)\(v^{\prime}.right\leftarrow\textsc{Centroid}(C_{b})\)\(\triangleright\) set the right child of \(v^{\prime}\) as the centroid of \(C_{b}\)\(\textsc{SimilarityTreeRec}(C_{a},v^{\prime}.left)\) \(\textsc{SimilarityTreeRec}(C_{b},v^{\prime}.right)\) endif endfunctionfunctionSplit(\(C\)) \(\{d_{a},d_{b}\}\leftarrow\textsc{Pivots}(C)\)\(\triangleright\) select initial pivots for splitting while\(i<\textsc{Max\_ITERATIONS}\)do\(C_{a}\gets Q\)\(\triangleright\) Initialize the cluster \(C_{b}\leftarrow\emptyset\)\(\triangleright\) Initialize the cluster for all\(d_{i}\in C\)do if\(\delta(d_{i},d_{a})<\delta(d_{i},d_{b})\)then\(C_{a}\gets C_{a}\cup\ d_{i}\)\(\triangleright\) add \(d_{i}\) to cluster \(C_{a}\) else\(C_{b}\gets C_{b}\cup\ d_{i}\)\(\triangleright\) add \(d_{i}\) to cluster \(C_{b}\) endif endfor\(d_{a}\leftarrow\textsc{Centroid}(C_{a})\)\(\triangleright\) update the pivot of \(C_{a}\)\(d_{b}\leftarrow\textsc{Centroid}(C_{b})\)\(\triangleright\) update the pivot of \(C_{b}\)\(i\gets it+1\) endwhile return\(\{C_{a},C_{b}\}\) endfunction
```  
**Algorithm 1** Similarity Tree (STree) algorithm.