Walk-Based Measures of Centrality, Communicability, and Robustness in Networks

Network science is a rapidly growing interdisciplinary area at the intersection of mathematics, physics, computer science, and a multitude of disciplines ranging from the life sciences to the social sciences and even the humanities.  Network analysis methods are now widely used in proteomics, the study of social networks (both human and animal), finance, ecology, bibliometric studies, archeology, the evolution of cities, and a host of other fields.  

After giving a brief overview of network science, I will discuss some basic mathematical and computational problems arising in network analysis, with a focus on the fundamental notions of centrality, communicability, and robustness.  Quantitative, walk-based measures of these notions will be introduced and motivated.  I will then show how these measures can be efficiently computed, even for large networks, using state-of-the-art numerical linear algebra techniques.  Heuristics for edge manipulation aimed at obtaining robust networks will also be discussed.  I will conclude with some open challenges in computational network analysis.  Most of the talk is intended to be accessible to a broad audience.