Marco Minutoli – Dissertation Defense

About the event

Student: Marco Minutoli

Advisor: Dr. Ananth Kalyanaraman

Degree:  Computer Science Ph.D.

Dissertation Title: Parallel Influence Maximization Algorithms and Their Applications

Abstract:

Influence Maximization is the problem of identifying a small set of influencers from a social network that, when initially activated, will result in the maximum number of activations over the network. The problem is driven by the hypothesis that a small cohort of actors is sufficient to exert a large degree of influence on the network. Consequently, the problem has been of interest for many application domains including marketing, social media analysis, and epidemiology.

 Efficient and scalable algorithms for Influence Maximization need to address the challenges emerging from its combinatorial nature and its embedded stochasticity. Achieving scale of computation while preserving high quality approximations has been an important challenge for real world applications with the current methods. Surprisingly, parallel computing approaches have been left largely unexplored.

Efficient parallel algorithms for Influence Maximization need to address new challenges. The unique characteristics of its highly dynamic workload and the data volume required for good quality approximations set Influence Maximization apart from the classical parallel graph analytics methods. The approaches and implementation presented in this dissertation constitute a systematic effort to address all the key parallelization challenges of Influence Maximization methods.

 This dissertation presents the design, development, and application of scalable Influence Maximization algorithms. We introduce the first parallel and scalable algorithm for distributed memory systems. Our method enables to compute high quality approximate solutions on million scale networks. We propose the first parallel and scalable algorithms targeting multi-GPU systems and the upcoming generation of exascale machines. We formulate the problem of controlling an epidemic through vaccination as the maximization of the individuals saved from the disease and we show the submodularity of the objective function. This result enables us to apply the techniques developed for Influence Maximization to the epidemic control problem. The approach shows comparable performance with the current state-of-the-art methods and greatly improves scalability by enabling the analysis of million scale networks.

 We believe the methods presented in this dissertation can guide future development in graph analytics for the upcoming exascale system and the post-exascale era. We expect that future modeling efforts will further expand the application of Influence Maximization methods and will enable new scientific discoveries.