Paper Info
Title
Maximizing Influence of Leaders in Social Networks
Abstract
ABSTRACTThe operation of adding edges has been frequently used to the study of opinion dynamics in social networks for various purposes. In this paper, we consider the edge addition problem for the DeGroot model of opinion dynamics in a social network with n nodes and m edges, in the presence of a small number s << n of competing leaders with binary opposing opinions 0 or 1. Concretely, we pose and investigate the problem of maximizing the equilibrium overall opinion by creating k new edges in a candidate edge set, where each edge is incident to a 1-valued leader and a follower node. We show that the objective function is monotone and submodular. We then propose a simple greedy algorithm with an approximation factor (1 - 1 over e) that approximately solves the problem in O(n3) time. Moreover, we provide a fast algorithm with a (1 - 1 over e -∈) approximation ratio and Õ(mke∈-2) time complexity for any ∈ > 0, where Õ (⋅) notation suppresses the poly (log n) factors. Extensive experiments demonstrate that our second approximate algorithm is efficient and effective, which scales to large networks with more than a million nodes.
Year
DOI
Venue
2021
10.1145/3447548.3467229
Knowledge Discovery and Data Mining
Keywords
DocType
Citations 
Opinion dynamics, social network, multi-agent system, graph algorithm, influence maximization, discrete optimization, Laplacian solver
Conference
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Xiaotian Zhou100.34
Zhongzhi Zhang28522.02