Xiaojing Ye - US grants

Have you ever been wondering how fast news spreads or a topic becomes trendy in online social networks? It is actually very challenging to answer such questions quantitatively and accurately. The difficulty, in mathematical language, is that the process takes place in extremely large heterogeneous networks, and the spreads exhibit pervasive randomness. For example, a Twitter user may retweet a post at literally any time, or just ignore it. Therefore, understanding and predicting the spread of trendy topics are among the most emerging problems in social networking. The study also has applications in smartphone/computer malware outbreak and epidemiology of infectious disease since the spreads share similar mathematical underpinning. Therefore, we use a general notion of information propagation on networks to describe the dynamic nature of those problems. The 'information' being propagated on networks can be a trendy topic, a new computer malware, or an infectious disease; the nodes can be users of social networking sites, computers on the internet, or human hosts; and links in the networks can be the followee and follower relationships, the network connections of computers, or the proximity or physical contact between people. In this project, we aim at developing new theory and efficient computational methods for several important problems about information propagation in networks. We advocate a new approach to model the propagation as continuous-time discrete-space stochastic processes, and propose to address these problems by novel theory and algorithms rooted in modern optimal transport theory and Fokker-Plank equations on graphs. In particular, we focus on three closely related problems which are fundamental in information propagation: influence prediction, propagation optimization, and propagation control. We will develop efficient numerical methods based on the novel approach to tackle these problems, and expect the results can greatly advance our ability to understand and control information propagation.

The focus of this project is on theoretical analysis and computations of information propagation on large-scale heterogeneous networks. The research has extensive applications in the real-world including social networking, cyber security and epidemics of infectious diseases. We concentrate on the investigation of three key problems on prediction and decision-making related to information propagation on networks. 1) Influence prediction: for a given source set of active nodes in the network, predict the influence, i.e. expected number of activated nodes (nodes which receive the information) in the future. 2) Optimal source distribution: select an optimal source set of nodes to achieve maximal influence. 3) Network control: change and manipulate resource distribution and network topology dynamically to achieve the desirable outcomes for information propagation on networks. These problems are difficult to solve due to many factors, such as large scale and heterogeneous structure of networks, uncertainties in propagation, incomplete knowledge of propagation dynamics, and noise in datasets. To overcome these difficulties, we take a novel and effective approach which is different from any existing method. In particular, we establish systems of differential equations, based on recently developed Fokker-Planck equations on graphs, to describe and compute the time evolution of the probability density functions for the activation states of the network and estimate the influence. We design graph-based stochastic optimization methods, which are closely related to the recent advancements on optimal transport theory, to effectively find optimal source distribution and propagation control strategy. The proposed methods are efficient, accurate, and can tackle those problems on large-scale real-world networks.

This EArly-concept Grant for Exploratory Research (EAGER) project addresses modeling and inference problems in order to improve understanding of interactions and interdependencies within interdependent critical infrastructures (ICIs). The key application areas are financial services, healthcare systems, communication technologies. This work will result in novel machine learning methodologies to generate data on infrastructure interdependencies. Findings will be widely disseminated in scholarly fora, with accompanying efforts in graduate-level training. Data and computer software produced in this project will be made publicly available via online data repositories.

This project includes the development of new generative models and algorithms to simulate and synthesize extensive interdependent CI data for comprehensive study. This research focuses on modeling and simulation of interdependent critical infrastructure (ICI) data by leveraging point process models and mean field games (MFG) theory. In particular, multivariate Hawkes processes are used to model interactions and interdependencies of behaviors in a variety of domains. Additionally, an MFG framework is employed to capture the implicit optimization strategies that individuals perform, along with the cost functions that drive those strategies. This work addresses both mechanistic and human aspects of the ICIs, captured in point process models and their evolution. This work advances the theory and computational methods for generative methods and algorithms for quantitative understanding and rigorous analysis of ICIs.

The goal of this project is to tackle major computational challenges faced by scientists and engineers in their quest to improve the accuracy and efficiency of numerical algorithms for solving large-scale inverse problems. This is a scenario where direct measurements of the unknown quantities are not feasible, and one needs to identify "cause from effect" by using (generally nonlinear) mathematical and statistical models. The resulting problems are notoriously ill-posed (or unstable), in a sense that even small measurement errors in the input data may give rise to a substantial noise propagation in the recovered solution, to the extent that this solution gets entirely destroyed. For this reason, special techniques called "regularization" must be combined with high-speed optimization procedures, so that reliable information on the unknown effect could be obtained from the available data. The key areas of application include imaging and sensing technology, machine learning, gravitational sounding, ocean acoustics, and data sciences.

This project aims at the development of iteratively regularized Broyden-type numerical algorithms for solving nonlinear ill-posed inverse problems in either finite or infinite dimensional spaces. A family of new regularization methods will be designed to solve large-scale unstable least squares problems, where the Jacobian of a discretized nonlinear operator is difficult or even impossible to compute. To overcome this obstacle, PIs consider a family of Gauss-Newton and Levenberg-Marquardt algorithms with the Frechet derivative operator recalculated recursively by using Broyden-type single rank updates. To balance accuracy and stability, the pseudo-inverse for the derivative-free Jacobian is regularized in a problem-specific manner at every step of the iteration process. A variety of filters will be investigated, yielding greater flexibility in the use of qualitative and quantitative a priori information available for each particular applied problem. The proposed iteratively regularized methods will be studied in both deterministic and stochastic settings. For stochastic processes, the minimization functionals are evaluated subject to stochastic errors due to inexact computations to lower per-iteration cost, and/or unavoidable environmental noise and fluctuations. In the framework of the proposed research, PIs will conduct comprehensive convergence analysis of the new algorithms, including convergence rates and optimal policies for the selection of regularization parameters and step sizes. In addition to the theoretical investigation, a significant component of this project is to evaluate the proposed algorithms using extensive numerical experiments on real-world nonlinear inverse problems.

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.

We live in a world full of networks: contact and social networks connect us to our family, friends and colleagues; computer networks such as Internet allow us to access huge amount of data and information remotely; traffic and logistical networks deliver people, water/food, and all kinds of goods faster than ever before. While we enjoy the conveniences brought by these networks, we must also be aware of the threats and harms if they get jeopardized by, for example, infectious virus, cyber-attacks, etc. The goal of this project is to develop computational algorithms for automated early threat detection based on novel and rigorous mathematical modeling and data analysis concepts. In particular, the activities generated by human and other sources on these networks are modeled as the so-called interactive stochastic point processes. These dynamics are studied and inferred in a mathematical framework of jump stochastic differential equations, which is further extended to integrate mean-field approximation and deep learning techniques that fully leverage the existing big data for fast and accurate threat detection. This project will exploit three closely related computational problems in-depth: influence prediction, optimal sensor allocation, and source identification, all of which are fundamental in threat detection applications on large, heterogeneous, real-world networks.

This project will exploit two novel approaches to influence prediction based on a jump stochastic differential equation (JSDE) formulation and an integration of mean field approximation and deep learning techniques. The JSDE formulation yields a concise and exact mathematical formulation of the temporal point process that takes into account the known network structure and mechanism of epidemic spread; and the deep neural mean field approach deduced from JSDE formulation maps the classical difference method in numerical analysis into a structured multi-layer residual network, where the unknown bias of mean field approximation can be effectively learned from observed cascade data for rapid influence prediction. These prediction algorithms will be used in the optimal sensor allocation and epidemic source identification problems for threat detection and mitigation. The results produced in this project are expected to make significant contributions to our understanding of interdependent activities on large-scale heterogeneous networks and the development of new, efficient algorithms for threat detection. The outcomes of the project include novel computational techniques, rigorous mathematical theory and analysis, and efficient numerical algorithms for threat detection applications.

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.