Introduction
Traditional link recommendation systems, such as Facebook's "People You May Know," primarily focus on predicting connections that are likely to form based on existing network structures like mutual friends or profile similarities. While these systems drive network growth, they often exacerbate the "rich-get-richer" phenomenon, reinforcing existing social biases and amplifying the reach of already popular users. This paper introduces a paradigm shift by addressing the Influence Maximization with Augmentation (IMA) problem. Instead of predicting likely links, the authors propose recommending links specifically designed to maximize the social influence—or information spread—of a target group of users.
Theoretical Framework and Submodularity
The researchers evaluate link recommendation under two foundational diffusion models: the Independent Cascade Model (ICM) and the Linear Threshold Model (LTM). A significant theoretical contribution of this work is the proof that the influence function under the LTM model is both monotone and submodular with respect to edge addition.
Submodularity is a critical property in optimization; it implies that while adding more links increases total influence, the marginal gain from each additional link decreases. This mathematical characteristic allows for the application of a greedy algorithm that is guaranteed to achieve an approximation factor of $(1 - 1/e)$, or approximately 63% of the optimal solution. Proving this for edge addition is notably more complex than for standard node selection, providing a rigorous foundation for the proposed recommendation heuristics.
Algorithmic Approach
To implement this theory at scale, the authors developed two primary algorithms:
- GREEDY1: An optimized version of the standard greedy approach that incorporates heuristics such as pruning low-probability edges and reducing the "live-edge" graph size to enhance computational speed.
- GREEDY2: A more advanced version that reduces the IMA problem to a "Limited Seed Selection" (LSS) problem. This reduction significantly accelerates the search for the most impactful edges to add to the network.
Both algorithms utilize "lazy evaluations" to skip redundant calculations by exploiting the submodularity property, ensuring they can handle large-scale real-world social networks.
Key Results
The proposed algorithms were tested across 13 diverse real-world networks, ranging from small academic citation graphs to massive social platforms like Twitter (nearly 500,000 nodes). The results demonstrate that the greedy approach consistently and significantly outperforms traditional baselines, such as recommending links to high-degree nodes (TopK) or nodes with high existing connection probability (Prob).
The quantitative impact of strategic link recommendation is profound. As shown in the experimental data, adding a small number of targeted edges can lead to an exponential increase in reach. For instance, on the Twitter dataset under the ICM model, the algorithm achieved a relative influence increment ($I\%$) of 7,136%. Even on smaller networks like Wiki-Vote, the boost exceeded 3,200%.
Beyond effectiveness, the GREEDY2 algorithm proved to be highly efficient. Despite the complexity of the Twitter graph, the algorithm identified the optimal links in just 10.23 seconds. This efficiency makes the approach viable for real-time recommendation systems in large-scale environments.
Conclusion and Future Directions
This research demonstrates that structural influence is a distinct and powerful metric for link recommendation, offering a way to bypass traditional popularity biases. By focusing on utility rather than just likelihood, recommenders can help "niche" users or specific content creators gain significant visibility with minimal network changes.
Future work may explore more complex scenarios where both the seed set of users and the recommended links are selected simultaneously. Additionally, integrating user acceptance models—ensuring recommended links feel "natural" to the user—and explicitly incorporating fairness constraints will be essential for deploying these algorithms in live social ecosystems.
Summary updated