Tree decompositions and social graphs
Preprint
Abstract
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. Among other things, 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 detailed empirical results for different TD heuristics on toy and synthetic networks help to establish a baseline to understand better the behavior of the heuristics on more complex real-world networks; and our results here suggest future directions for the development of improved TD heuristics that are more appropriate for improved structure identification in realistic networks.Keywords
All Related Versions
This publication has 47 references indexed in Scilit:
- Scaled Gromov hyperbolic graphsJournal of Graph Theory, 2007
- Maximum Cardinality Search for Computing Minimal Triangulations of GraphsAlgorithmica, 2004
- Solving partial constraint satisfaction problems with tree decompositionNetworks, 2002
- On the Hyperbolicity of Chordal GraphsAnnals of Combinatorics, 2001
- Efficient Parallel Algorithms for Graphs of Bounded Tree-WidthJournal of Algorithms, 1996
- Call routing and the ratcatcherCombinatorica, 1994
- Approximating treewidth, pathwidth, and minimum elimination tree heightLecture Notes in Computer Science, 1992
- Linear time algorithms for NP-hard problems restricted to partial k-treesDiscrete Applied Mathematics, 1989
- The analysis of a nested dissection algorithmNumerische Mathematik, 1986
- The intersection graphs of subtrees in trees are exactly the chordal graphsJournal of Combinatorial Theory, Series B, 1974