Recommending Links to Maximize the Influence in Social Networks

Federico Corò, Gianlorenzo D'Angelo, Yllka Velaj

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:

  1. 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.
  2. 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).

Comparison of the Greedy algorithm against baselines in terms of active nodes reached as the budget B increases.

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%.

Detailed performance metrics across various datasets for ICM and LTM models.

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

Abstract

Social link recommendation systems, like "People-you-may-know" on Facebook, "Who-to-follow" on Twitter, and "Suggested-Accounts" on Instagram assist the users of a social network in establishing new connections with other users. While these systems are becoming more and more important in the growth of social media, they tend to increase the popularity of users that are already popular. Indeed, since link recommenders aim at predicting users' behavior, they accelerate the creation of links that are likely to be created in the future, and, as a consequence, they reinforce social biases by suggesting few (popular) users, while giving few chances to the majority of users to build new connections and increase their popularity.In this paper we measure the popularity of a user by means of its social influence, which is its capability to influence other users' opinions, and we propose a link recommendation algorithm that evaluates the links to suggest according to their increment in social influence instead of their likelihood of being created. In detail, we give a constant factor approximation algorithm for the problem of maximizing the social influence of a given set of target users by suggesting a fixed number of new connections. We experimentally show that, with few new links and small computational time, our algorithm is able to increase by far the social influence of the target users. We compare our algorithm with several baselines and show that it is the most effective one in terms of increased influence.
BibTeX
@inproceedings{coro2019recommending,
  author = {Federico Corò and Gianlorenzo D'Angelo and Yllka Velaj},
  title = {{Recommending Links to Maximize the Influence in Social Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/304},
}
Figure