Graphs and networks are a popular way to model interactions in a wide range of applications, including data drawn from natural, social, and information sciences, and thus offer promising opportunities for interdisciplinary research. However, one significant challenge in analyzing large complex networks has been understanding the 'intermediate-scale' structure, i.e., those properties not captured by metrics which are very local (e.g., clustering coefficient) or very global (e.g., degree distribution). It is often this structure which governs the dynamic evolution of the network and the behavior of diffusion-like processes on it. Although there is a large body of empirical evidence suggesting that complex networks have 'tree-like' properties at intermediate to large size-scales (e.g., hierarchical structures in biology, hyperbolic routing in the Internet, and core-periphery behavior in social networks), it remains a challenge to quantify and take algorithmic advantage of this structure in many data analysis applications.

In this talk, we describe recent empirical and theoretical results aimed at integrating techniques from structural graph theory (tree decompositions and minors), metric embedding theory (Gromov hyperbolicity), and scalable heuristics (core-periphery heuristics and k-core decompositions) into scalable and robust tools for extracting meaningful tree-like structure from large informatics networks. We present computational results showing the successes and failings of existing measures of tree-likeness on real world data, and discuss recent progress integrating structural information into downstream frameworks for local inference. Finally, as time permits, we will discuss new algorithms using tree decompositions to enable scalable solution of certain graph optimization problems in a high performance computing environment, and several open research problems.

Blair D. Sullivan is a Research Staff Member in the Complex Systems Group at Oak Ridge National Laboratory. Her current research interests include network modeling and analysis, applied structural graph theory, and scalable graph algorithms. She has also worked in parallel computing, extremal (di) graph theory, quantum computing, and combinatorics. Before joining ORNL, Blair was a visiting researcher at the Renyi Institute in Budapest, Hungary. She received her Ph.D. in Mathematics at Princeton University as a Department of Homeland Security Graduate Fellow, and bachelor's degrees in Applied Mathematics and Computer Science at Georgia Tech. Blair has been the Principal Investigator on grants from the DOE's Office of Advanced Scientific Computing Research, ORNL's LDRD program, and the DARPA GRAPHS program. She serves on the Graph500 Steering Committee, is leading a research cluster during the ICERM Semester Program on Network Science and Graph Algorithms, and is on the organizing committee for the SIAM Workshop on Combinatorial Scientific Computing (CSC14).