Paper Info
Title
A Nearly-Linear Time Algorithm for Minimizing Risk of Conflict in Social Networks
Abstract
Concomitant with the tremendous prevalence of online social media platforms, the interactions among individuals are unprecedentedly enhanced. People are free to interact with acquaintances, express and exchange their own opinions through commenting, liking, retweeting on online social media, leading to resistance, controversy and other important phenomena over controversial social issues, which have been the subject of many recent works. In this paper, we study the problem of minimizing risk of conflict in social networks by modifying the initial opinions of a small number of nodes. We show that the objective function of the combinatorial optimization problem is monotone and supermodular. We then propose a naive greedy algorithm with a (1-1/e) approximation ratio that solves the problem in cubic time. To overcome the computation challenge for large networks, we further integrate several effective approximation strategies to provide a nearly linear time algorithm with a (1-1/e-ε) approximation ratio for any error parameter ε>0. Extensive experiments on various real-world datasets demonstrate both the efficiency and effectiveness of our algorithms. In particular, the fast one scales to large networks with more than two million nodes, and achieves up to 20x speed-up over the state-of-the-art algorithm.
Year
DOI
Venue
2022
10.1145/3534678.3539469
KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Liwang Zhu100.34
Zhongzhi Zhang28522.02