Leader–Follower Disagreement Minimization in Social Networks
研究如何从社交网络中选择k个领导者，使领导者与追随者之间的分歧最小，提出POLS算法，在保证近似比的同时大幅降低计算时间。
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 (kn) 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(k2n4) 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 O(k2mn) expected time, where is an error parameter. Extensive experiments on various real-world social networks illustrate both the effectiveness and efficiency of POLS.