CAREER: Network Centrality and Its Applications in Detection, Dynamics, and Load Balancing

点击翻译按钮获取中文摘要

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). This project aims to develop a mathematical understanding of networks that evolve over time and the processes that take place on them. The key idea is to identify network attributes that carry a footprint of a network's past and to exploit them in reconstructing the early stages of a network from its current configuration. This can be used to detect, for example, the origin of a rumor spread, popular individuals and their influence in a social network, or a source of a disease outbreak. The results are expected to have significant applications in national security and public health. Another key research direction is to develop a systematic understanding of how local interactions in a large network influence its global geometry. This knowledge can be used to increase the overall efficiency of a network of servers through cooperative local interactions, with potential applications in improving routing schemes for airport security, supermarket distribution systems, and distribution of vaccines and other medicines. The project aims to develop a robust toolbox across many disciplines in science and engineering. The project involves significant educational activities and integration of research and education. The activities aim to prepare a diverse STEM workforce through long-term research and career mentoring for undergraduate and graduate students. Course material and review papers emerging from this research will be freely available online to students and researchers. Centrality driven networks connect the fields of dynamic random networks and reinforced processes. The first part of the project investigates centrality driven networks, in which incoming vertices attach to one or more existing vertices with probability proportional to their centrality scores. Centrality measures like PageRank, which interpolate the global and local network geometries, will be used to study network archaeology questions. Novel dynamic networks driven by PageRank and opinion dynamics will also be analyzed. The second part of the project explores centrality-driven routing policies for networks where each vertex has a server with a unit service rate. Jobs arriving at a subset of vertices designated arrival nodes myopically explore the network in search of less busy servers to minimize their waiting time. Optimal placement of the arrival nodes will be analyzed using a new notion of load centrality. Diffusion limits and load balancing based on Dirichlet energy functionals will be used to study systems in heavy traffic. The techniques used in the research will rely on a delicate interplay between discrete time and continuous time dynamics to move beyond model specific computations. As a byproduct, the project aims to provide new characterizations of branching process limits and rates of convergence.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.