Nonprogressive Diffusion on Social Networks: Approximation and Applications

Nonprogressive diffusion models the spread of behavior on social networks, where agents are allowed to reverse their decisions as time evolves. To provide an efficient framework for evaluating and optimizing nonprogressive diffusion, we introduce a comprehensive model along with a fixed-point approximation (FPA) scheme, which admits both theoretical guarantee and computational efficiency. We show that the approximation error depends on the network structure and derive order-optimal bounds for this error based on a newly proposed network measure. Additionally, we propose two easy-to-calculate network metrics (one at the node level and the other at the network level) that serve as reliable indicators of FPA performance. Our results indicate that the FPA scheme is particularly accurate for dense and large networks, which are typically challenging to analyze via simulation. To showcase the broad applicability of our approach, we apply the FPA scheme to well-known problems, like influence maximization and optimal pricing on social networks. Finally, we conduct extensive numerical experiments on both synthetic and real-world networks. On real-world networks, the FPA scheme achieves computational speedups of 70–230 times compared with naïve agent-based simulation and 23–30 times compared with a more advanced simulation method while maintaining a mean absolute percentage error of less than 3.48%.

This paper was accepted by Jeannette Song, operations management.

Funding: R. Zhang is grateful for financial support from the National Natural Science Foundation of China [Grant 72422004] and the Hong Kong Research Grants Council General Research Fund [Grants 14502722, 14504123, and 14503224].

Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2022.03031.