Myhill Lecture Series 2018 by Dr. Mark Newman, *Anatol Rapoport Distinguished University Professor of Physics*, Department of Physics and Center for the Study of Complex Systems, University of Michigan.

**About the speaker:** Professor Newman's research is on statistical physics and the theory of complex systems, with a primary focus on networked systems, including social, biological, and computer networks, which are studied using a combination of empirical methods, analysis, and computer simulation. Among other topics, he and his collaborators have worked on mathematical models of network structure, computer algorithms for analyzing network data, and applications of network theory to a wide variety of specific problems, including the spread of disease through human populations and the spread of computer viruses among computers, the patterns of collaboration of scientists and business-people, citation networks of scientific articles and law cases, network navigation algorithms and the design of distributed databases, and the robustness of networks to the failure of their nodes.

Professor Newman also has a research interest in cartography and was, along with collaborators, one of the developers of a new type of map projection or "cartogram" that can be used to represent geographic data by varying the sizes of states, countries, or regions.

Professor Newman is the author of several books, including a recent textbook on network theory and a popular book of cartography.

Abstract: There are networks in every part of our lives: the Internet, the power grid, the road network, networks of friendship or acquaintance, ecological networks, biochemical networks, and many others. As large-scale data on these networks have become available in the last few years, a new science of networks has grown up combining empirical observations with the mathematics of graph theory to shed light on systems ranging from bacteria to the whole of human society. This first lecture will give an introduction to this fascinating branch of science, and discuss some of its central questions and the techniques we use to answer them.

Abstract: A fundamental class of tools in the study of networks are network models such as the classic random graph of Erdos and Renyi as well as more modern models, including configuration models and preferential attachment models. This lecture will introduce the mathematics behind these models and demonstrate how they are applied to help us understand such things as degree distributions, assortativity, and community structure, as well as processes taking place on networks such as the spread of disease.

Abstract: Most graphs encountered in the empirical study of networks, including Internet and Web graphs, social networks, and biological and ecological networks, are very sparse. Standard spectral and linear algebra methods fail badly when applied to such graphs and a fundamentally different approach is needed. Message passing methods, such as belief propagation, offer a promising solution. In this lecture I will illustrate how message passing can be used to calculate the structural and dynamic properties of a range of common network models. 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 to structural phase transitions in networks.