  Link recommendation systems in online social networks (OSNs), such as
Facebook's ``People You May Know'', Twitter's ``Who to Follow'', and
Instagram's ``Suggested Accounts'', facilitate the formation of new connections
among users. This paper addresses the challenge of link recommendation for the
purpose of social influence maximization. In particular, given a graph $G$ and
the seed set $S$, our objective is to select $k$ edges that connect seed nodes
and ordinary nodes to optimize the influence dissemination of the seed set.
This problem, referred to as influence maximization with augmentation (IMA),
has been proven to be NP-hard.
  In this paper, we propose an algorithm, namely \textsf{AIS}, consisting of an
efficient estimator for augmented influence estimation and an accelerated
sampling approach. \textsf{AIS} provides a
$(1-1/\mathrm{e}-\varepsilon)$-approximate solution with a high probability of
$1-\delta$, and runs in $O(k^2 (m+n) \log (n / \delta) / \varepsilon^2 + k
\left|E_{\mathcal{C}}\right|)$ time assuming that the influence of any
singleton node is smaller than that of the seed set. To the best of our
knowledge, this is the first algorithm that can be implemented on large graphs
containing millions of nodes while preserving strong theoretical guarantees. We
conduct extensive experiments to demonstrate the effectiveness and efficiency
of our proposed algorithm.
