Fast Computation and Optimization for Opinion-Based Quantities of Friedkin-Johnsen Model

Haoxin Sun (Fudan University) · Yubo Sun (Fudan University) · Xiaotian Zhou (Fudan University) · Zhongzhi Zhang (Fudan University, Tsinghua University)

accuracy and efficiencydisagreement minimization problemefficient algorithmsfast computationfriedkin–johnsen modellarge-scale networksopinion minimization problemopinion-based quantitiesoptimization problemspartial rooted forest samplingpartial rooted forestspolarization minimization problemreal-world networks state-of-the-art methodssublinear algorithmstime complexity

In this paper, we address the problem of fast computation and optimization of opinion-based quantities in the Friedkin–Johnsen (FJ) model. We first introduce the concept of partial rooted forests and present an efficient algorithm for computing these quantities using this method. Furthermore, we study two optimization problems in the FJ model: the Opinion Minimization Problem and the Polarization and Disagreement Minimization Problem. For both problems, we propose fast algorithms based on partial rooted forest sampling. Our methods reduce the time complexity from linear to sublinear. Extensive experiments on real-world networks demonstrate that our algorithms are both accurate and efficient, outperforming state-of-the-art methods and scaling effectively to large-scale networks.