Preliminary Exam – Marco Minutoli

About the event

Student:  Marco Minutoli

Committee Chair:  Dr. Ananth Kalyanaraman

Title: Parallel Influence Maximization Algorithms and their Applications

Abstract:  This thesis proposal aims at bridging the gap between the theoretical work on approximation algorithms and efficient parallel algorithms for the Influence Maximization Problem to enable advancements in the achievable quality of results and scale. Building on these advancements, we aim at exploring innovative applications of the problem in other areas of science with particular focus on applications in the field of computational epidemiology.

Building on the current state-of-the-art approximation algorithms for influence maximization, we have proposed Ripples: a framework of parallel and scalable algorithms for Influence Maximization. Ripples incorporates a custom dispatching engine that allows to distribute the computation among the processing elements of a heterogeneous system and, therefore, leverage GPU acceleration. The framework has provided up to a 760x improvement over the current state-of-the-art. Building on Ripples, we will draw the connection between the research in Influence Maximization algorithms and the research designing intervention strategies in the framework of networked epidemiology by proposing PREEMPT. PREEMPT is a scalable epidemic intervention strategy that targets the most influential node in a contact network by leveraging the submodular optimization framework that is able to scale on multi-GPU systems.  PREEMPT improves over the current state-of-the-art methods based on mathematical programming in terms of scalability, time to solution, and effectiveness in the intervention. We conclude by suggesting future research directions aiming at improving the performance of the methods, reducing the system requirements, and advising fairness in epidemic control.