CRII: Interpretable Influence Propagating and Blocking on Graphs

Mississippi State University, Mississippi State MS

Investigators

Abstract

As networks including virtual (e.g., social networks) and physically grounded (e.g., transportation networks) increase in complexity, the need to understanding the spread of network influence is crucial. Influence in networks has been the subject of increasing attention among researchers due to its far-reaching social and commercial implications. For instance, the objective of information propagation or viral marketing is to identify the most prominent trend setters capable of influencing vast numbers of others, while the primary objective of epidemiology is to ascertain who is most likely to spread a disease, which aids in the development of vaccine and quarantine regulations. This project will develop novel tools to analyze how the spreading network's structure and initial state maximize the influence flow, and then investigate policy options for controlling the flows. The primary innovation of this project will be its ability to learn the complex relationship between flows and the geometric structure of graphs and extract understandable rules for decision-makers. The main challenge is the huge number of combinations of variables combined across structures and attributes to alter influence flows. This project advocates a unique paradigm for learning interpretable representations of influence flow over graphs, with a particular emphasis on disentangling the combinatorial limitations imposed by both the graph's geometric structure and seed selection. This research aims at developing a new framework that boosts accuracy and interpretability while decoupling the influence process. The difficulty of developing interpretable models is compounded by the specific characteristics of influence modeling, which include complex tangled topological links, insufficient data, and confluence effects. The investigator will use context-aware constraints and complementing observations to narrow the search and determine the effect source. The investigator will perform an in-depth assessment of effective and efficient control policies to improve influence propagation or blocking. This project will address the following three fundamental research issues: learning expository topological dependence of influence; Learning the influence cascade and the sources; and learning to control the influence flows. The proposed model will determine the optimal seeds that minimize future influence based on the currently influenced region, which requires modeling the interaction of numerous graph-dependent elements. According to thermodynamics' second law, the flow rate is determined by the energy levels within the system, which motivates us to examine graph entropy notions further to provide a more robust assessment of them. The investigator will employ global sensitivity analysis and perturbation matrix theory to choose the smallest yet most critical and robust set. 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.