https://doi.org/10.1140/epjb/e2015-60263-6
Regular Article
Analysis of information diffusion for threshold models on arbitrary networks
1
Department of Knowledge Service Engineering, KAIST,
Daejeon
34141,
Korea
2
Department of Electrical and Computer Engineering, Seoul National
University, Seoul
08826,
Korea
3
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
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.
Key words: Statistical and Nonlinear Physics
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2015