  Previous statistical approaches to hierarchical clustering for social network
analysis all construct an "ultrametric" hierarchy. While the assumption of
ultrametricity has been discussed and studied in the phylogenetics literature,
it has not yet been acknowledged in the social network literature. We show that
"non-ultrametric structure" in the network introduces significant instabilities
in the existing top-down recovery algorithms. To address this issue, we
introduce an instability diagnostic plot and use it to examine a collection of
empirical networks. These networks appear to violate the "ultrametric"
assumption. We propose a deceptively simple and yet general class of
probabilistic models called $\mathbb{T}$-Stochastic Graphs which impose no
topological restrictions on the latent hierarchy. To illustrate this model, we
propose six alternative forms of hierarchical network models and then show that
all six are equivalent to the $\mathbb{T}$-Stochastic Graph model. These
alternative models motivate a novel approach to hierarchical clustering that
combines spectral techniques with the well-known Neighbor-Joining algorithm
from phylogenetic reconstruction. We prove this spectral approach is
statistically consistent.
