期刊
IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS
卷 8, 期 3, 页码 1116-1127出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TCNS.2021.3058620
关键词
Approximation algorithm; balance of opinions; French-DeGroot model; optimization; social network
资金
- NSF [CNS-1553340, CNS-1816307]
This study focuses on the French-DeGroot opinion dynamics in a social network with two polarizing parties, investigating the selection of leaders to shift average opinion. Analysis shows the NP-hardness of selecting leaders to change average opinion and proposes a greedy algorithm for approximating the optimal solution. Experimental results demonstrate the effectiveness of the algorithm in both random and real-world networks.
We study the French-DeGroot opinion dynamics in a social network with two polarizing parties. We consider a network in which the leaders of one party are given, and we pose the problem of selecting the leader set of the opposing party so as to shift the average opinion to a desired value. When each party has only one leader, we express the average opinion in terms of the transition matrix and the stationary distribution of random walks in the network. The analysis shows the balance of influence between the two leader nodes. We show that the problem of selecting at most k absolute leaders to shift the average opinion is NP-hard. Then, we reduce the problem to a problem of submodular maximization with a submodular knapsack constraint and an additional cardinality constraint, and propose a greedy algorithm with upper bound search to approximate the optimum solution. We also conduct experiments in random networks and real-world networks to show the effectiveness of the algorithm.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据