In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy
will defend his dissertation proposal
Improved Probabilistic Guarantees for Influence Maximization
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.