Structure, phase transitions, and message passing in sparse networks

Most networks and graphs encountered in empirical studies, including technological, social, 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 which works well in the sparse limit and which can also provide new analytic insights. This talk will introduce the message passing method through a 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 properties, 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.