From Local Network Structure to Global Graph Spectrum

ABSTRACT: Using methods from algebraic graph theory and convex optimization we study the relationship between local structural features of a network and global spectral properties. In particular, we derive expressions for the so-called spectral moments of a graph in terms of local structural measurements, such as subgraph densities. Furthermore, we propose a series of semidefinite programs to compute bounds on the spectral radius, and other spectral properties, from a truncated sequence of spectral moments. Using our tools, we illustrate how important spectral properties of real-world networks are strongly constrained by local structural features.

BIO: Victor M. Preciado received his Ph.D. degree in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology in 2008. He is currently the Raj and Neera Singh Assistant Professor of Electrical and Systems Engineering at the University of Pennsylvania. He is a member of the Networked & Social Systems Engineering (NETS) program, the Warren Center for Network & Data Sciences, and the Applied Math and Computational Science (AMCS) program. He is a recipient of the 2017 National Science Foundation Faculty Early Career Development (CAREER) Award. His main research interests lie at the intersection of Big Data and Network Science; in particular, in using innovative mathematical and computational approaches to capture the essence of complex, high-dimensional dynamical systems. Relevant applications of this line of research can be found in the context of socio-technical networks, brain dynamical networks, healthcare operations, biological systems, and critical technological infrastructure.