Stability of Influence Maximization

摘要

In the well-studied Influence Maximization problem, the goal is to identify a set of k nodes in a social network whose joint influence on the network is maximized. A large body of recent work has justified research on Influence Maximization models and algorithms with their potential to create societal or economic value. However, in order to live up to this potential, the algorithms must be robust to large amounts of noise, for they require quantitative estimates of the influence which individuals exert on each other; ground truth for such quantities is inaccessible, and even decent estimates are very difficult to obtain. We begin to address this concern formally. First, we exhibit simple inputs on which even very small estimation errors may mislead every algorithm into highly suboptimal solutions, motivating a need for algorithms that can determine whether a given instance is vulnerable to noise. Analyzing the susceptibility of specific instances to estimation errors leads to a clean algorithmic question which we term the Influence Difference Maximization problem, and for which we present an approximation algorithm based on maximizing a non-monotone submodular function. Using the proposed techniques, we investigate the susceptibility of synthetic and real-world social network data sets. Roughly, when perturbations are on the order of 10% of the observed parameter values, the objective function is fairly stable, while relative perturbations above 20% may lead to significant instability. Our results thus suggest caution in the use of algorithmic Influence Maximization results.