Eur. Phys. J. B (2015) 88: 201
https://doi.org/10.1140/epjb/e2015-60263-6

Regular Article

Analysis of information diffusion for threshold models on arbitrary networks

¹ Department of Knowledge Service Engineering, KAIST, Daejeon 34141, Korea
² Department of Electrical and Computer Engineering, Seoul National University, Seoul 08826, Korea
³ SoHoBricks Corp., Irvine, CA 92614, USA

^a e-mail: kjung@snu.ac.kr

Received: 1 April 2015
Received in final form: 23 June 2015
Published online: 10 August 2015

Abstract

Diffusion of information via networks has been extensively studied for decades. We study the general threshold model that embraces most of the existing models for information diffusion. In this paper, we first analyze diffusion processes under the linear threshold model, then generalize it into the general threshold model. We give a closed formula for estimating the final cascade size for those models and prove that the actual final cascade size is concentrated around the estimated value, for any network structure with node degrees ω(log n), where n is the number of nodes. Our analysis analytically explains the tipping point phenomenon that is commonly observed in information diffusion processes. Based on the formula, we devise an efficient algorithm for estimating the cascade size for general threshold models on any network with any given initial adopter set. Our algorithm can be employed as a subroutine for numerous algorithms for diffusion analysis such as influence maximization problem. Through experiments on real-world and synthetic networks, we confirm that the actual cascade size is very close to the value computed by our formula and by our algorithm, even when the degrees of the nodes are not so large.