Scalable Link Recommendation for Influence Maximization

The rise of link recommendation systems in online social networks has sparked significant research interest in strategically adding links to enhance social influence. This paper delves into the influence maximization with augmentation (IMA) problem that aims to add k edges connecting seed nodes and ordinary nodes to boost the influence propagation of the given seed set. IMA is a monotone submodular maximization problem so that the greedy algorithm provides a (1-1/e-ε)-approximate solution, where ε is an error term caused by the intractable nature of influence spread computation. Previous work often utilizes an unbiased estimator that relies on the chosen edges for influence estimation, resulting in non-submodular estimate with respect to edge selection. To ensure the overall error being bounded by ε, such an estimator requires Θ(ε/k) multiplicative error for each estimation, incurring prohibitive overhead. Meanwhile, some other work approximates IMA via conventional influence maximization (IM) on an augmented graph by adding a new node for every edge candidate, leading to heavy extra sampling due to a significant increase in graph size. To address these challenges, we design a novel unbiased estimator on the original graph that is independent of the chosen edges by leveraging the tractability of one-hop influence computation. We show that the estimate via our estimator is submodular so that it enables the estimate of all k edges in a whole with a bounded estimation error of Θ(ε), saving O(k2) time compared to the chosen-edge-dependent estimator while retaining the same graph size. Moreover, we propose several techniques based on the properties of our estimator to further speed up the greedy selection. Putting it together, we develop a scalable algorithm for the IMA problem, namely ScaLIM. Finally, extensive experiments are conducted to validate the effectiveness and efficiency of our proposed approach, e.g., ScaLIM is faster than baselines by nearly two orders of magnitude.