  Recent work has established that large informatics graphs such as social and
information networks have non-trivial tree-like structure when viewed at
moderate size scales. Here, we present results from the first detailed
empirical evaluation of the use of tree decomposition (TD) heuristics for
structure identification and extraction in social graphs. Although TDs have
historically been used in structural graph theory and scientific computing, we
show that---even with existing TD heuristics developed for those very different
areas---TD methods can identify interesting structure in a wide range of
realistic informatics graphs. Our main contributions are the following: we show
that TD methods can identify structures that correlate strongly with the
core-periphery structure of realistic networks, even when using simple greedy
heuristics; we show that the peripheral bags of these TDs correlate well with
low-conductance communities (when they exist) found using local spectral
computations; and we show that several types of large-scale "ground-truth"
communities, defined by demographic metadata on the nodes of the network, are
well-localized in the large-scale and/or peripheral structures of the TDs. Our
other main contributions are the following: we provide detailed empirical
results for TD heuristics on toy and synthetic networks to establish a baseline
to understand better the behavior of the heuristics on more complex real-world
networks; and we prove a theorem providing formal justification for the
intuition that the only two impediments to low-distortion hyperbolic embedding
are high tree-width and long geodesic cycles. Our results suggest future
directions for improved TD heuristics that are more appropriate for realistic
social graphs.
