Tree decompositions and social graphs

DOI10.1080/15427951.2016.1182952zbMATH Open1461.68139arXiv1411.1546OpenAlexW2963079722WikidataQ57434415 ScholiaQ57434415MaRDI QIDQ5856440FDOQ5856440

Authors: Aaron Adcock, Michael W. Mahoney, Blair D. Sullivan 

Publication date: 26 March 2021

Published in: Internet Mathematics (Search for Journal in Brave)

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. 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.

Full work available at URL: https://arxiv.org/abs/1411.1546

Recommendations

• Treewidth computations. I: Upper bounds
• Finding good tree decompositions by local search
• \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Algorithm 837
• The University of Florida sparse matrix collection
• Title not available (Why is that?)
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• An open graph visualization system and its applications to software engineering
• The analysis of a nested dissection algorithm
• Nested Dissection of a Regular Finite Element Mesh
• Probabilistic graphical models.
• An Approximate Minimum Degree Ordering Algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• Collective dynamics of `small-world' networks
• Title not available (Why is that?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Call routing and the ratcatcher
• Geodetic topological cycles in locally finite graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complex graphs and networks
• A sufficiently fast algorithm for finding close to optimal clique trees
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Title not available (Why is that?)
• Approximation algorithms for treewidth
• Learning Markov networks: Maximum bounded tree-width graphs
• Polynomial bounds for the grid-minor theorem
• Hyperbolicity and chordality of a graph
• On the hyperbolicity of chordal graphs
• Minimal triangulations of graphs: a survey
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• The Pathwidth and Treewidth of Cographs
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Metric embedding, hyperbolic space, and social networks
• Treewidth computations. I: Upper bounds
• Treewidth: Characterizations, Applications, and Computations
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Title not available (Why is that?)
• A note on treewidth in random graphs
• Scaled Gromov hyperbolic graphs
• Monadic second-order evaluations on tree-decomposable graphs
• The elimination form of the inverse and its application to linear programming
• Treewidth: computational experiments
• On the Complexity of Computing Treelength
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Title not available (Why is that?)
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Maximum cardinality search for computing minimal triangulations of graphs
• On tree width, bramble size, and expansion
• SOFSEM 2005: Theory and Practice of Computer Science
• On treewidth approximations.
• Tree-Like Structures in Graphs: A Metric Point of View
• Tree-decompositions with bags of small diameter
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Linear-time computation of optimal subgraphs of decomposable graphs
• Scaled Gromov four-point condition for network graph curvature computation
• Title not available (Why is that?)
• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• Core-periphery structure in networks
• Fast algorithms for determining (generalized) core groups in social networks
• Title not available (Why is that?)
• The minimum degree heuristic and the minimal triangulation process.
• On compact and efficient routing in certain graph classes
• Connected tree-width
• Solving partial constraint satisfaction problems with tree decomposition
• \(k\)-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases
• Characterization of Graphs Using Degree Cores
• The peculiar phase structure of random graph bisection

Cited In (14)

• From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
• The hyperbolicity constant of infinite circulant graphs
• On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• An Experimental Study of the Treewidth of Real-World Graph Data
• Helly-gap of a graph and vertex eccentricities
• Local 2-separators
• To approximate treewidth, use treelength!
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• On the herdability of linear time-invariant systems with special topological structures
• Graph decompositions for demographic loop analysis
• Vertex-Pursuit in Hierarchical Social Networks

Uses Software

• AMD
• Pajek
• SparseMatrix
• ComputeTW
• INDDGO
• GitHub

This page was built for publication: Tree decompositions and social graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5856440)