Nonprogressive Diffusion on Social Networks: Approximation and Applications



    Department of Systems Engineering and Engineering Management

                       The Chinese University of Hong Kong


Date: Wednesday, January 17, 2:00 pm – 3:00 pm

Venue: ERB 513, The Chinese University of Hong Kong

Title: Nonprogressive Diffusion on Social Networks: Approximation and Applications

Speaker: Yunduan Lin, UC Berkeley



Nonprogressive diffusion describes the spread of behavior on a social network, where agents are allowed to reverse their decisions as time evolves. It has a wide variety of applications in service adoption, opinion formation, epidemiology, etc. To offer an efficient framework for evaluating and optimizing nonprogressive diffusion, we introduce a comprehensive model and a Fixed-Point Approximation (FPA) scheme. This approximation scheme admits both a theoretical guarantee and computational efficiency. We establish that the approximation error is inherently related to the network structure, and derive order-optimal bounds for the error using two novel metrics of network characteristics. We show that the FPA scheme is most powerful for dense and large networks that are generally prohibitive to analyze by simulation. Taking the widely studied influence maximization and pricing problems on a social network as examples, we further illustrate the broad applications of our FPA scheme. Finally, we conduct comprehensive numerical studies with synthetic and real-world networks. In real networks, the FPA scheme shows 70-230 times more speed up in computation time than simulation while achieving a mean absolute percentage error of less than 3.48%. Moreover, our proposed two network metrics are reliable indicators of the FPA scheme's performance.


Yunduan Lin is a fifth-year Ph.D. candidate from the Systems Engineering program in the Department of Civil and Environmental Engineering, UC Berkeley, advised by Zuo-Jun Max Shen. Her research focuses on navigating the operations of complex societal systems by leveraging the vast wealth of data and information available. Her recent work addresses real-world challenges on social networks, online marketplaces and healthcare systems. She is the winner of INFORMS Social Media Analytics Best Student Paper Award, first-place prize of the POMS-HK Best Student Paper Award and a finalist of the INFORMS Data Mining and Decision Analytics Workshop Best Paper award in theoretical track.

Everyone is welcome to attend the talk!

SEEM-5202 Website:


Wednesday, January 17, 2024 - 14:00