Nonprogressive Diffusion on Social Networks: Approximation and Applications

• 成果类型: Article; Early Access
• 署名作者: Lin, Yunduan; Zhang, Heng; Zhang, Renyu; Shen, Zuo-Jun Max
• 署名单位: Chinese University of Hong Kong; Arizona State University-Tempe; Arizona State University; Arizona State University-Tempe; University of Hong Kong; University of Hong Kong
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2022.03031
• 发表日期: 2025
• 关键词: nonprogressive network diffusion; large-scale network approximation; Network centrality; influence maximization; pricing

摘要

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-tocalculate 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 & iuml;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%.