Robust Influence Maximization for Hyperparametric Models
This addresses the problem of selecting seed users to maximize influence in social networks under uncertainty in hyperparameters, which is incremental as it builds on existing robust influence maximization research.
The paper tackles robust influence maximization in social networks under a hyperparametric model, where edge probabilities depend on user features and a global hyperparameter, aiming to maximize worst-case influence. The authors prove NP-hardness for proper robust solutions, propose an algorithm using sampling and multiplicative weight updates, and empirically show it outperforms state-of-the-art robust techniques.
In this paper, we study the problem of robust influence maximization in the independent cascade model under a hyperparametric assumption. In social networks users influence and are influenced by individuals with similar characteristics and as such, they are associated with some features. A recent surging research direction in influence maximization focuses on the case where the edge probabilities on the graph are not arbitrary but are generated as a function of the features of the users and a global hyperparameter. We propose a model where the objective is to maximize the worst-case number of influenced users for any possible value of that hyperparameter. We provide theoretical results showing that proper robust solution in our model is NP-hard and an algorithm that achieves improper robust optimization. We make-use of sampling based techniques and of the renowned multiplicative weight updates algorithm. Additionally, we validate our method empirically and prove that it outperforms the state-of-the-art robust influence maximization techniques.