Opinion Maximization in Social Networks: An Inverse Optimization Perspective

摘要

Given a social network 𝒢 with n nodes and m edges, the opinion maximization (OM) problem aims at identifying k (k ≪ n) opinion leaders to maximize their opinion propagation in 𝒢. Despite its significance and prevalence, existing OM methods often struggle to strike a satisfactory balance between theoretical performance and practical efficiency. This paper provides an inverse optimization perspective for OM by reformulating it as an opinion minimization (OMin) problem, whose objective function holds succinct expression and desired properties. Then, we introduce a bounded estimation scheme (BES) that can estimate the objective function of OMin with bounded error in Õ(kn+m) expected time, thereby making the optimization for OMin more efficient. To further enhance the optimization efficiency, a decomposition-based decremental estimation algorithm (DDEA) with a near (1-1/e) approximation ratio in Õ(kmn) expected time is specifically designed for OMin. Extensive experiments on real-world social networks of varying scales demonstrate the effectiveness of BES and the superiority of DDEA.