Opinion Maximization in Social Networks via Leader Selection

We study a leader selection problem for the DeGroot model of opinion dynamics in a social network with n nodes and m edges, in the presence of s0 = O(1) leaders with opinion 0. Concretely, we consider the problem of maximizing the average opinion in equilibrium by selecting k = O(1) leaders with opinion 1 from the remaining n − s0 nodes, which was previously proved to be NP-hard. A deterministic greedy algorithm was also proposed to approximately solve the problem, which has an approximation factor (1 − 1/e) and time complexity O(n3), and thus does not apply to large networks.