Graph Limits and Measurable Graphs

Northeastern University, Boston MA

Investigators

Abstract

Understanding the structure and properties of large real-life networks has become one of the most important scientific challenges of our time. Large networks are ubiquitous in both the natural and social sciences and we have access to more-and-more data about them. However, most existing methods for analyzing this data are too slow for even moderately large networks. Hence the need to devise, new, robust tools for network analysis. One way of building new tools is to advance our understanding of the underlying structure of large networks. This approach has led to tremendous success in the case of networks with relatively many connections (so called dense networks). However, most real-word networks do not fall into this category (they are so-called sparse), and our understanding of their structural properties remain rather limited. The goal of this project is to advance the understanding of large sparse networks through the study of similarities between networks, and via the use of continuous models - so called graph limits - to approximate large networks. This approach has proved extremely successful in the case of dense networks. Progress in the sparse case has been slow mainly because the "right" notion of similarity seems elusive, and a host of different concepts have emerged over time whose relationship to each other remains unclear. The project will focus on the graph limits, networks defined on probability measure spaces, so-called graphings. It will investigate classical graph theoretic notions on such objects. The few known results indicate that graphings frequently exhibit surprising differences compared to classical graphs. Yet, one can often find natural assumptions under which classical results extend to the measurable context without any change. The central motivating question of the project is the approximability of graphings by finite graphs. To this end, various combinatorial and algebraic properties of graphings will be explored in detail to allow comparison to finite graphs. The combinatorial aspects include understanding how standard theorems in graph theory about the existence of matchings, vertex- and edge-colorings generalize to graphings. Algebraic aspects include the study of spectral properties of graphings. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.