Efficient Algorithm for Opinion Optimization via Leader Selection in Directed Social Networks

Abstract

We study an opinion optimization problem based on an extended DeGroot model for a social network, where stubborn leaders hold fixed opinions of 0 or 1. Given a set of leaders with opinion 0, our goal is to select a small number of leaders with opinion 1 from the remaining nodes to maximize the average opinion of the network. Previous studies mainly focus on undirected graphs, but real-world social networks are often directed. Therefore, it is essential to address the problem in directed graphs. To solve the problem, we first establish a novel interpretation of equilibrium opinions using random rooted spanning forests. Building on this interpretation, we propose a random spanning forest sampling greedy algorithm that leverages an extension of Wilson’s algorithm and a sample update technique, which is efficient and provides an error guarantee. Our algorithm applies to both undirected and directed graphs. Extensive experiments on real-world networks demonstrate that for undirected graphs our algorithm outperforms the state-of-the-art method—achieving accuracy improvements of up to 42% and speedups of up to 80%. Moreover, for directed graphs our algorithm achieves comparable effectiveness to the deterministic greedy algorithm and is scalable to large directed graphs with millions of nodes, where the deterministic greedy algorithm is not scalable.