Analysis of Tipping Points for Threshold Models on Arbitrary Networks

Abstract

Diffusion of new ideas, technologies or epidemics via various social networks has been extensively studied for decades. In particular, Kempe, Kleinberg, and Tardos proposed the \emph{general threshold model}, a generalization of many diffusion models on networks which is based on utility maximization of individuals in game theoretic consideration. Despite its importance, the analysis under the threshold model, however, has concentrated on special cases such as the submodular influence, homogeneous thresholds, and locally tree-like networks. In this paper, we consider the general threshold model~ with arbitrary threshold distributions on arbitrary networks. We prove that only if (essentially) all nodes have degrees ω(log n), the final cascade size is highly concentrated around its mean with high probability for a large class of general threshold models including the linear threshold model, the independent cascade model, and the Katz-Shapiro pricing model. We also prove that in those cases, the expectation of the cascade size is asymptotically invariant of the network structures and provide a formula to compute the average cascade size, if initial adopters are chosen uniformly at random. Hence, even if network structures are not known, we can still estimate the final cascade size. We also extend our results to arbitrary general threshold models and provide upper and lower bounds for the cascade size. We then provide an efficient algorithm that estimates the average cascade size for the general threshold model. Our algorithm also computes the probability of being influenced for each individual. Our results allow us to predict when a phase transition for a large spreading happens. Since our algorithm estimates the final cascade size efficiently, it can be also used as a subroutine in many algorithms for the influence maximization problem. Through extensive experiments on several real-world and synthetic networks, we confirm that the cascade size is actually concen...