Abstract
Social network often serves as a medium for the diffusion of ideas or innovations. The problem of influence maximization which was posed by Domingos and Richardson is stated as: if we can try to convince a subset of individuals to adopt a new product and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target in order to achieve a maximized influence? In this work, we proposed a potential-based node selection strategy to solve this problem. Our work is based on the observation that local most-influential node-selection adopted in many works, which is very costly, does not always lead to better result. In particular, we investigate on how to set two parameters(θ v and b uv ) appropriately. We conduct thorough experiments to evaluate effectiveness and efficiency of the proposed algorithm. Experimental results demonstrate that our approximation algorithm significantly outperforms local-optimal greedy strategy.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Granovetter, M.: Threshold models of collective behavior. American Journal of Sociology 83(6), 1420–1443 (1978)
Schelling, T.: Micromotives and Macrobehavior. Norton (1978)
Berger, E.: Dynamic Monopolies of Constant Size. Journal of Combinatorial Theory Series B 83, 191–200 (2001)
Morris, S.: Contagion. Review of Economic Studies 67 (2000)
Peleg, D.: Local Majority Voting, Small Coalitions, and Controlling Monopolies in Graphs: A Review. In: 3rd Colloq. On Structural Information and Communication (1996)
Macy, M., Willer, R.: From Factors to Actors: Computational Sociology and Agent-Based Modeling. Ann. Rev. Soc (2002)
Valente, T.: Network Models of the Diffusion of Innovations. Hampton Press (1995)
Peyton Young, H.: The Diffusion of Innovations in Social Networks. Santa Fe Institute Working Paper 02-04-018 (2002)
Watts, D.: A Simple Model of Global Cascades in Random Networks. Proc. Natl. Acad. Sci. 99, 5766–5771 (2002)
Domingos, P., Richardson, M.: Mining the Network Value of Customers. In: ICDM (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(3), 211–223 (2001)
Goldenberg, J., Libai, B., Muller, E.: Using Complex Systems Analysis to Advance Marketing Theory Development. Academy of Marketing Science Review (2001)
Kempe, D., Kleinberg, J., Tardos, E.: Influential nodes in a diffusion model for social networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005, vol. 3580, pp. 1127–1138. Springer, Heidelberg (2005)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence in a social network. In: Proc. 9th Intl. Conf. on KDD, pp. 137–146 (2003)
Sun, S., Ling, L., Zhang, N., Li, G., Chen, R.: Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Research 31(9), 2443–2450 (2003)
Software package Protein Interaction Network PIN
Beebe, N.H.F.: Nelson H.F. Beebe’s Bibliographies Page (2002)
Jones, B.: Computational Geometry Database (February 2002); FTP / HTTP
Estevez, P.A., Vera, P., Saito, K.: Selecting the Most Influential Nodes in Social Networks. In: Proceedings of International Joint Conference on Neural Networks, Orlando, Florida, USA, August 12-17 (2007)
Richardson, M., Domingos, P.: Mining knowledge-sharing sites for Viral Marketing. In: Eighth Intl. Conf. on knowledge Discovery and Data Mining (2002)
Rama Suri, N., Narahari, Y.: Determining the Top-k Nodes in Social Networks using the Shapley Value (Short Paper). In: Padgham, Parkes, Müller, Parsons (eds.) AAMAS 2008, Estoril, Portugal, May 12-16, pp. 1509–1512 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, Y., Feng, X. (2009). A Potential-Based Node Selection Strategy for Influence Maximization in a Social Network. In: Huang, R., Yang, Q., Pei, J., Gama, J., Meng, X., Li, X. (eds) Advanced Data Mining and Applications. ADMA 2009. Lecture Notes in Computer Science(), vol 5678. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03348-3_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-03348-3_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03347-6
Online ISBN: 978-3-642-03348-3
eBook Packages: Computer ScienceComputer Science (R0)