NeurIPS paper cuts opinion dynamics computation from linear to sublinear time

A new NeurIPS 2025 paper tackles the computational bottleneck of the Friedkin-Johnsen (FJ) model, a widely used framework for simulating how opinions evolve in social networks. The authors—Haoxin Sun, Yubo Sun, Xiaotian Zhou, and Zhongzhi Zhang—introduce a clever technique called partial rooted forests that reduces the time complexity of computing opinion-based quantities from linear to sublinear. This means that instead of scaling proportionally with network size, the algorithm can handle millions of nodes in a fraction of the previous time, making it practical for real-world social platforms.

The paper addresses two key optimization problems: minimizing a single opinion (e.g., pushing a target belief) and simultaneously reducing polarization and disagreement across the network. For both, the team designed fast algorithms based on partial rooted forest sampling. Their experiments on real-world networks (e.g., citation graphs, social media structures) show that their methods outperform existing state-of-the-art approaches in both accuracy and speed. The work is especially relevant for researchers studying influence campaigns, echo chambers, and policy interventions on online platforms, offering a scalable toolkit for computational social science.