Trees, Dendrograms and Sensitivity

Dendrograms and minimum-weight spanning trees (MWST) are discrete structures which arise inclustering theory, networks, and where strategic choices are made between discrete options. The discrete structureof the solution tree varies discontinuously with respect to changes in the dissimilarity or cost matrix. Tarjan[1982] has obtained bounds on the changes to the elements of the cost matrix, where the structure is not altered.These results are extended to describe the sensitivity of the tree structure with respect to changes in the costmatrix. The sensitivity of the structure to the addition of a node and arcs is solved using potential loops in thetree. This phase of the solution process builds onto the solution to the original MWST. The full sensitivityanalysis of a dendrogram to changes in the attribute matrix is very complex, due partly to the corresponding costmatrix being a function of the full attribute matrix. Statistical methods are used to compare changes in the treestructure with changes in the attribute matrix. Analytical results are obviously difficult to obtain. The Kruskalclustering algorithm is used on the similarity or cost matrix to construct both the MWST and the dendrogram.Thus the sensitivity of the dendrogram to the similarity or cost matrix corresponds to the sensitivity of the MWSTfor this method of clustering.