In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

Nguyen Pham

will defend his dissertation proposal

Improved Probabilistic Guarantees for Influence Maximization

Abstract

The standard Influence maximization problem involves choosing a seed set of a given size, which maximizes the expected influence. However, such solutions might have a significant probability of achieving low influence, which might not be suitable in many applications. In this paper, we consider a different approach: find a seed set which maximizes the influence set size, which can be achieved with a given probability. We show that this objective is not submodular, and design two algorithms for this problem, one of which gives rigorous approximation bounds. We evaluate our algorithms on multiple datasets, and show that they have similar or better performance as the ones optimizing the expected influence, but with additional guarantees on the probability. Keywords: social network influence, influence maximization, multi-criteria approximation, Monte-Carlo sampling.

Date: Thursday, November 29, 2018
Time: 10:00 AM
Place: PGH 218D
Advisors: Dr. Gopal Pandurangan

Faculty, students, and the general public are invited.