Abstract
We address a problem of predicting diffusion probabilities in complex networks. As one approach to this problem, we focus on the independent cascade (IC) model, and define the likelihood for information diffusion episodes, where an episode means a sequence of newly active nodes. Then, we present a method for predicting diffusion probabilities by using the EM algorithm. Our experiments using a real network data set show the proposed method works well.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adar, E., Adamic, L.: Tracking information epidemics in blogspace. In: Proc. of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2005), pp. 207–214 (2005)
Albert, R., Jeong, H., Barabási, A.L.: Error and attack tolerance of complex networks. Nature 406, 378–382 (2000)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)
Balthrop, J., Forrest, S., Newman, M.E.J., Williampson, M.W.: Technological networks and the spread of computer viruses. Science 304, 527–529 (2004)
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.: Graph structure in the Web. In: Proc. of the 9th International World Wide Web Conference (WWW 2000), pp. 309–320 (2000)
Callaway, D.S., Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Network robustness and fragility: Percolation on random graphs. Physical Review Letters 85, 5468–5471 (2000)
Domingos, P., Richardson, M.: Mining the network value of customers. In: Proc. of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2001), pp. 57–66 (2001)
Goldenberg, J., Libai, B., Muller, E.: Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters 12, 211–223 (2001)
Gruhl, D., Guha, R., Liben-Nowell, D., Tomkins, A.: Information diffusion through blogspace. In: Proc. of the 13th International World Wide Web Conference (WWW 2004), pp. 107–117 (2004)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proc. of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2003), pp. 137–146 (2003)
Kimura, M., Saito, K., Nakano, R.: Extracting influential nodes for information diffusion on a social network. In: Proc. of the 22nd AAAI Conference on Artificial Intelligence (AAAI-2007), pp. 1371–1376 (2007)
Leskovec, J., Adamic, L., Huberman, B.A.: The dynamics of viral marketing. In: Proc. of the 7th ACM Conference on Electronic Commerce (EC-2006), pp. 228–237 (2006)
McCallum, A., Corrada-Emmanuel, A., Wang, X.: Topic and role discovery in social networks. In: Proc. of the 19th International Joint Conference on Artificial Intelligence (IJCAI-2005), pp. 786–791 (2005)
Newman, M.E.J., Forrest, S., Balthrop, J.: Email networks and the spread of computer viruses. Physical Review E 66, 035101 (2002)
Newman, M.E.J.: The structure and function of complex networks. SIAM Review 45, 167–256 (2003)
Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005)
Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: Proc. of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2002), pp. 61–70 (2002)
Strogatz, S.H.: Exploring complex networks. Nature 410, 268–276 (2001)
Song, X., Chi, Y., Hino, K., Tseng, B.L.: Information flow modeling based on diffusion rate for prediction and ranking. In: Proc. of the 16th International World Wide Web Conference (WWW-2007), pp. 191–200 (2007)
Watts, D.J.: A simple model of global cascades on random networks. In: Proc. of the National Academy of Sciences of the United States of America, vol. 99, pp. 5766–5771 (2002)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Saito, K., Nakano, R., Kimura, M. (2008). Prediction of Information Diffusion Probabilities for Independent Cascade Model. In: Lovrek, I., Howlett, R.J., Jain, L.C. (eds) Knowledge-Based Intelligent Information and Engineering Systems. KES 2008. Lecture Notes in Computer Science(), vol 5179. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85567-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-85567-5_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85566-8
Online ISBN: 978-3-540-85567-5
eBook Packages: Computer ScienceComputer Science (R0)