Abstract: Although large social and information networks are often thought of as having hierarchical or tree-like structure, this assumption is rarely tested. We have performed a detailed empirical analysis of the tree-like properties of realistic informatics graphs using two very different notions of tree-likeness: Gromov's δ-hyperbolicity, which is a notion from geometric group theory that measures how tree-like a graph is in terms of its metric structure; and tree decompositions, tools from structural graph theory which measure how tree-like a graph is in terms of its cut structure. Although realistic informatics graphs often do not have meaningful tree-like structure when viewed with respect to the simplest and most popular metrics, e.g., the value of δ or the treewidth, we conclude that many such graphs do have meaningful tree-like structure when viewed with respect to more refined metrics, e.g., a size-resolved notion of δ or a closer analysis of the tree decompositions. We also show that, although these two rigorous notions of tree-likeness capture very different tree- like structures in the worst-case, for realistic informatics graphs they empirically identify surprisingly similar structure. We interpret this tree-like structure in terms of the recently-characterized "nested core-periphery" property of large informatics graphs; and we show that the fast and scalable k-core heuristic can be used to identify this tree-like structure.

Abstract: I will introduce some fundamental concepts of lattice theory (unimodular lattices, lattice gluing) and explain why we expect them to naturally appear on a homological algebra level. We will discuss the example of the cut and flow lattices of a graph, and a categorical realisation which serves as an example for lifting lattice theoretic concepts as mentioned above. We end with a number of open questions and directions. Joint work with Anthony Licata.