Many systems of scientific and technological importance can be represented as networks: the Internet, the power grid, airline and road networks, biological networks, and social networks, to name just a few. The last fifteen years have seen a wave of advances in mathematical and computational techniques for understanding these systems and analyzing the massive troves of network data that are becoming available. The work to be undertaken under this funding will do two things: (1) develop fundamental new mathematics to enhance our understanding of the structure and function of networks of all types, and (2) employ that mathematical foundation in the creation of new measures, metrics, and computer algorithms for practical application to real-world network problems. The work will draw on mathematical methods from two areas in which the PI has worked extensively: Statistics (Bayesian inference) and spectral theory. Using these tools the PI and his students and collaborators will develop techniques to tackle a range of network problems, including: the detection of communities of interacting nodes or individuals within larger networks; the identification of the most influential or core nodes with a network; the understanding and prediction of spreading processes on networks, including the spread of diseases over human contact networks; fast and scalable computer algorithms for the analysis of network data on the largest scales; and specific applications to a range of technological, social, and information networks.
This grant will fund a three-year research effort to develop fundamental mathematical tools for understanding large, real-world networks such as the Internet, the World Wide Web, biological networks, epidemiological contact networks, social networks, and others. The proposed work focuses on large-scale network properties, rather than local properties, and will employ techniques mainly from two fields, spectral methods and statistical inference. Recent work by the PI's group and others has produced significant advances, including a number of results revealing deep and previously unsuspected connections between spectral and inference methods. These advances have opened up substantial avenues for new research whose exploration is the primary goal of the proposed work. Specific projects to be undertaken include the development of random matrix and free probability methods for computing spectra of complex networks within several widely used structural models; development of new inference algorithms for features such as core/periphery structure and centrality, particularly based on belief propagation methods; connections between inference and spectral methods, particularly via the Hashimoto operator which appears in the theory of graph zeta functions; spectral localization and the development of improved spectral centrality measures; applications to network processes such as percolation and disease transmission, which can be treated using belief propagation and hence connected to spectral properties of graphs; applications to spectral algorithms for multiway community detection and other large-scale structure detection problems; connections between spectral and inference methods derived from relaxations of the likelihood function; and model selection methods for network inference.
