MATH Seminar

Title: Finding a role for structural graph theory in real-world network analysis
Seminar: The SIAM Student Chapter
Speaker: Blair Sullivan of Oak Ridge National Laboratory
Contact: Alexis Aposporidis, aapospo@emory.edu
Date: 2012-10-23 at 4:00PM
Venue: W306
Download Flyer
Abstract: Network science is a rapidly growing interdisciplinary field with methods and applications drawn from across the natural, social, and information sciences. Perhaps surprisingly, very few approaches use techniques from the rich literature of structural graph theory. In this talk, we discuss some first steps towards integrating what have been predominantly theoretical results into tools for scalable network analysis.\\ \\ Tree-like structures arise extensively in network science - for example, hierarchical structures in biology, hyperbolic routing in the internet, and core-periphery behavior in social networks. As such, this talk focuses on ways to use tree decompositions, key combinatorial objects used in graph minor theory, in Tandem with k-cores and Gromov hyperbolicity to provide structural characterization of and improve inference on complex networks. We also discuss new algorithms using tree decompositions to enable scalable solution of certain graph optimization problems in a high performance computing environment.