Structure, phase transitions, and message passing in sparse networks

Most networks and graphs encountered in empirical studies, including the Internet and the World Wide Web, social networks, and biological and ecological networks, are very sparse. Standard spectral and linear algebra methods perform poorly when applied to such networks. Message passing methods, such as belief propagation, offer an alternative that can deliver better performance as well as new analytic insights. This talk will introduce the message passing method through a progressive series of examples and illustrate how the method can be used for a wide range of calculations of network structure and function. Among other things, the talk will touch upon the calculation of percolation thresholds, graph spectra, and community structure, the deep connections between message-passing fixed points and structural phase transitions in networks, and a new solution to the long-standing problem of message passing on networks with a high density of short loops.