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.
Similar content being viewed by others
References
J.A. Dodson., E. Muller, Management Science 24, 1568 (1976)
J. Coleman, E.M. Katz, H. Menzel, Sociometry 20, 253 (1957)
D.H.S. Bikhchandani, I. Welch, J. Polit. Econ. 100, 992 (1992)
T.W. Valente, Network Models of the Diffusion of Innovations (Hampton Press, 1995)
F. Chierichetti, S. Lattanzi, A. Panconesi, in Proceedings of SODA, 2010, pp. 1657–1663
M. Granovetter, Am. J. Sociol. 83, 1420 (1978)
R. Cohen, K. Erez, D. ben Avraham, S. Havlin, Phys. Rev. Lett. 85, 4626 (2000)
R. Pastor-Satorras, A. Vespignani, Phys. Rev. Lett. 86, 3200 (2000)
D.J. Watts, Proc. Natl. Acad. Sci. USA 99, 5766 (2002)
D.E. Whitney, Phys. Rev. E 82, 066110 (2010)
E. Valdano, L. Ferreri, C. Poletto, V. Colizza, Phys. Rev. X 5, 021005 (2015)
D. Kempe, J. Kleinberg, E. Tardos, in Proceedings of KDD, 2003, pp. 137–146
M.E.J. Newman, Phys. Rev. E 66, 016128 (2002)
T.C. Schelling, J. Conflict Resolut. 17, 381 (1973)
P. Domingos, M. Richardson, Mining Knowledge-Sharing Sites for Viral Marketing, in Proceedings of KDD, 2002, pp. 61–70
L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, E. Tardos, in Proceedings of FOCS, 2011, pp. 393–402
D.M. Romero, Btranscript. Meeder, J. Kleinberg, in Proceedings of WWW, 2011, pp. 695–704
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance, in Proceedings of KDD, 2007, pp. 420–429
W. Chen, C. Wang, Y. Wang, in Proceedings of KDD, 2010, pp. 1029–1038
A. Goyal, W. Lu, L.V.S. Lakshmanan, in Proceedings of WWW, 2011, pp. 47–48
W. Chen, Y. Yuan, L. Zhang, in Proceedings of ICDM, 2010, pp. 88–97
A. Goyal, W. Lu, L.V.S. Lakshmanan, in Proceedings of ICDM, 2011, pp. 211–220
P. Holme, B.J. Kim, C.N. Yoon, S.K. Han, Phys. Rev. E 65, 056109 (2002)
P. Gai, S. Kapadia, Proc. R. Soc. A 466, 2401 (2010)
S.V. Buldyrev, R. Parshani, G. Paul, H.E. Stanley, S. Havlin, Nature 464, 1025 (2010)
D.S. Callaway, M.E.J. Newman, S.H. Strogatz, D.J. Watts, Phys. Rev. Lett. 85, 5468 (2000)
A. Ganesh, L. Massoulie, D. Towsley, in Proceedings of INFOCOM, 2005, pp. 1455–1466
G. Ergun, Physica A 308, 483 (2002)
S. Wasserman, K. Faust, Social Network Analysis (Cambridge University Press, 1994)
M. Szell, R. Lambiotte, S. Thurner, Proc. Natl. Acad. Sci. USA 107, 13636 (2010)
M. Richardson, R. Agrawal, P. Domingos, in Proceedings of ISWC, 2003, pp. 351–368
L.A. Adamic, N. Glance, in Proceedings of LinkKDD, 2005, pp. 36–43
K.T.D. Eames, M.J. Keeling, Proc. Natl. Acad. Sci. USA 99, 13330 (2002)
H. Zhou, R. Lipowsky, Proc. Natl. Acad. Sci. USA 102, 10052 (2005)
J.P. Gleeson, Phys. Rev. Lett. 107, 068701 (2011)
J.P. Gleeson, Phys. Rev. X 3, 021004 (2013)
S. Lim, K. Jung, J.C.S. Lui, ACM SIGMETRICS Perform. Eval. Rev. 41, 31 (2013)
Y. Lin, J.C.S. Lui, K. Jung, S. Lim, J. Complex Networks 2, 431 (2014)
M.L. Katz, C. Shapiro, Am. Econ. Rev. 75, 424 (1985)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lim, S., Jung, I., Lee, S. et al. Analysis of information diffusion for threshold models on arbitrary networks. Eur. Phys. J. B 88, 201 (2015). https://doi.org/10.1140/epjb/e2015-60263-6
Received:
Revised:
Published:
DOI: https://doi.org/10.1140/epjb/e2015-60263-6