Abstract
We address the problem of discovering the influential nodes in a social network under the susceptible/infected/susceptible model that allows multiple activation of the same node, by defining two influence maximization problems: final-time and integral-time. We solve this problem by constructing a layered graph from the original network with each layer added on top as the time proceeds and applying the bond percolation with two effective control strategies: pruning and burnout. We experimentally demonstrate that the proposed method gives much better solutions than the conventional methods that are based solely on the notion of centrality using two real-world networks. The pruning is most effective when searching for a single influential node, but burnout is more powerful in searching for multiple nodes which together are influential. We further show that the computational complexity is much smaller than the naive probabilistic simulation both by theory and experiment. The influential nodes discovered are substantially different from those identified by the centrality measures. We further note that the solutions of the two optimization problems are also substantially different, indicating the importance of distinguishing these two problem characteristics and using the right objective function that best suits the task in hand.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adar E, Adamic LA (2005) Tracking information epidemics in blogspace. In: Skowron A, Agrawal R, Luck M, Yamaguchi T, Morizet-Mahoudeaux P, Liu J, Zhong N (eds) Proceedings of 2005 IEEE/WIC/ACM international conference on web intelligence, Compiegne, Sept 2005, pp 207–214
Agarwal N, Liu H (2008) Blogosphere: research issues, tools, and applications. SIGKDD Explor 10(1): 18–31
Backstrom L, Dwork C, Kleinberg J (2007) Wherefore art thou r3579 × ?: anonymized social networks, hidden patterns, and structural steganography. In: Williamson CL, Zurko ME, Patel-Schneider PF, Shenoy PJ (eds). Proceedings of the 16th international conference on world wide web, Banff, May 2007, pp 181–190
Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Elder IV JF, Fogelman-Soulié F, Flach PA, Zaki MJ (eds) Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, Paris, June 2009, pp 199–208
Domingos P (2005) Mining social networks for viral marketing. IEEE Intell Syst 20(1): 80–82
Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the 7th ACM SIGKDD international conference on knowledge discovery and data mining, San Francisco, Aug 2001, pp 57–66
Goldenberg J, Libai B, Muller E (2001) Talk of the network: a complex systems look at the underlying process of word-o-mouth. Market Lett 12(3): 211–223
Grassberger P (1983) On the critical behavior of the general epidemic process and dynamical percolation. Math Biosci 63(2): 157–172
Gruhl D, Guha R, Liben-Nowell D, Tomkins A (2004) Information diffusion through blogspace. In: Feldman SI, Uretsky M, Najork M, Wills CE (eds) Proceedings of the 13th international conference on world wide web, New York, May 2004, pp 107–117
Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Getoor L, Senator TE, Domingos P, Faloutsos C (eds) Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining, Washington Aug 2003, pp 137–146
Kimura M, Saito K, Motoda H (2009) Blocking links to minimize contamination spread in a social network. ACM Trans Knowl Discov Data 3(2): 9:1–9:23
Kimura M, Saito K, Motoda H (2009b) Efficient estimation of influence functions for SIS model on social networks. In: Boutilier C (ed) Proceedings of the 21st international joint conference on artificial intelligence, Pasadena, July 2009, pp 2046–2051
Kimura M, Saito K, Nakano R (2007) Extracting influential nodes for information diffusion on a social network. In: Proceedings of the 22nd AAAI conference on artificial intelligence, Vancouver, July 2007, pp 1371–1376
Kimura M, Saito K, Nakano R, Motoda H (2010) Extracting influential nodes on a social network for information. Data Min Knowl Discov 20(1): 70–97
Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007a) Cost-effective outbreak detection in networks. In: Berkhin P, Caruana R, Wu X (eds) Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining, San Jose, Aug 2007, pp 420–429
Leskovec J, McGlohon M, Faloutsos C, Glance N, Hurst M (2007b) Patterns of cascading behavior in large blog graphs. In: Proceedings of the 7th SIAM international conference on data mining, Minneapolis, Apr 2007, pp 551–556
McCallum A, Corrada-Emmanuel A, Wang X (2005) Topic and role discovery in social networks. In: Kaelbling LP, Saffiotti A (eds) Proceedings of the 19th international joint conference on artificial intelligence, Edinburgh, July–Aug 2005, pp 786–791
Mislove A, Marcon M, Gummadi KP, Druschel P, Bhattacharjee B (2007) Measurement and analysis of online social networks. In: Dovrolis C, Roughan M (eds) Proceedings of the 7th ACM SIGCOMM conference on internet measurement, San Diego, Oct 2007, pp 29–42
Muhlestein D, Lim S (2009) Online learning with social computing based interest sharing. Knowl Inf Syst (published online: Nov 2009)
Newman MEJ (2001) The structure of scientific collaboration networks. Proc Natl Acad Sci USA 98(2): 404–409
Newman MEJ (2002) Spread of epidemic disease on networks. Phys Rev E 66: 016128
Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2): 167–256
Newman MEJ, Park J (2003) Why social networks are different from other types of networks. Phys Rev E 68: 036122
Peng W, Li T (2010) Temporal relation co-clustering on directional social network and author-topic evolution. Knowl Inf Syst (published online: March 2010)
Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of the 8th ACM SIGKDD international conference on knowledge discovery and data mining, Edmonton, July 2002, pp 61–70
Saito K, Kimura M, Motoda H (2009) Discovering influential nodes for SIS models in social networks. In: Gama J, Costa VS, Jorge AM, Brazdil P (eds). Proceedings of the 12th international conference of discovery science, Porto, Oct 2009. Lecture Notes in Computer Science, vol 5808. Springer, pp 302–316
Wasserman S, Faust K (1994) Social network analysis. Cambridge University Press, Cambridge
Watts DJ (2002) A simple model of global cascade on random networks. Proc Natl Acad Sci USA 99(9): 5766–5771
Watts DJ, Dodds PS (2007) Influence, networks, and public opinion formation. J Consum Res 34(4): 441–458
Zhou B, Pei J (2010) The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks. Knowl Inf Syst (published online: June 2010)
Zhou D, Ji X, Zha H, Giles CL (2006) Topic evolution and social interactions: how authors effect research. In: Yu PS, Tsotras VJ, Fox EA, Liu B (eds) Proceedings of the 2006 ACM CIKM international conference on information and knowledge management, Arlington, Nov 2006, pp 248–257
Zhuge H, Zhang J (2010) Topological centrality and its applications. J Am Soc Inf Sci Technol 61(9): 1824–1841
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Saito, K., Kimura, M., Ohara, K. et al. Efficient discovery of influential nodes for SIS models in social networks. Knowl Inf Syst 30, 613–635 (2012). https://doi.org/10.1007/s10115-011-0396-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10115-011-0396-2