Nonprogressive Diffusion on Social Networks : Approximation and Applications

Nonprogressive diffusion describes the dissemination of behavior on a social network, where the agents are allowed to reverse their decisions as time evolves. It has a wide variety of applications in service adoption, opinion formation, epidemiology, etc. Building upon the rich studies in network diffusion analysis and operations research, we propose a general model to characterize nonprogressive diffusion and develop a fixed-point approximation (FPA) scheme to characterize the limiting adoption on a social network. This approximation scheme admits both a theoretical guarantee and computational efficiency. We show that the maximal deviation of the FPA scheme diminishes as the network size and density increase at a rate of $\mathcal{O}(1/\sqrt{N_{\min}})$, where $N_{\min}$ is the minimum indegree of the agents on a social network. Thus, the FPA scheme is most powerful for dense and large networks that are generally prohibitive 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. The FPA scheme shows 1,000 times speed up in computation time than simulation. It achieves small approximation error, and outperforms conventional algorithms even when the social network is small and/or sparse