Structure, phase transitions, and belief propagation in sparse networks

Most networks and graphs encountered in empirical studies, including internet and web graphs, social networks, and biological and ecological networks, are very sparse.  Standard spectral and linear algebra methods can fail badly when applied to such networks and a fundamentally different approach is needed.  Message passing methods, such as belief propagation, offer a promising solution for these problems.  In this talk I will introduce some simple models of sparse networks and illustrate how message passing can form the basis for a wide range of calculations of their structure.  I will also show how message passing can be applied to real-world data to calculate fundamental properties such as percolation thresholds, graph spectra, and community structure, and how the fixed-point structure of the message passing equations has a deep connection with structural phase transitions in networks.