Leader-Follower Disagreement Minimization in Social Networks

Disagreement optimization is an emerging research issue in social networks. Although leaders are often selected to shape the opinions of followers, little effort has been made to investigate how to optimize the disagreement between them. This paper aims to address this issue by proposing and solving the following subset selection problem called leader-follower disagreement minimization (LFDMP): given a social network with n vertices and m edges, how to select k (k ≪ n) vertices as leaders such that the disagreement between leaders and followers is minimized. We show that the objective function of LFDMP is monotone and supermodular, and the state-of-the-art algorithm called Pareto optimization for subset selection (POSS) can solve this problem with (1-1 / e) approximation in O(k²n⁴) expected time. To address the computational challenge faced by POSS while maintaining its theoretical advantage, we further develop a fast algorithm called Pareto optimization for leader selection (POLS) within its framework. We demonstrate that POLS can solve LFDMP with ε-related approximation in Õ(k²mn) expected time, where ε is an error parameter. Extensive experiments on various real-world social networks illustrate both the effectiveness and efficiency of POLS.