article

Efficient discovery of influential nodes for SIS models in social networks

Authors:

Masahiro Kimura,

Hiroshi MotodaAuthors Info & Claims

Knowledge and Information Systems, Volume 30, Issue 3

Pages 613 - 635

Published: 01 March 2012 Publication History

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.

References

[1]

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

[2]

Agarwal N, Liu H (2008) Blogosphere: research issues, tools, and applications. SIGKDD Explor 10(1): 18---31

Digital Library

[3]

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

[4]

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

[5]

Domingos P (2005) Mining social networks for viral marketing. IEEE Intell Syst 20(1): 80---82

Digital Library

[6]

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

Digital Library

[7]

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

[8]

Grassberger P (1983) On the critical behavior of the general epidemic process and dynamical percolation. Math Biosci 63(2): 157---172

[9]

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

[10]

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

[11]

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

Digital Library

[12]

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

[13]

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

Digital Library

[14]

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

Digital Library

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Muhlestein D, Lim S (2009) Online learning with social computing based interest sharing. Knowl Inf Syst (published online: Nov 2009)

[20]

Newman MEJ (2001) The structure of scientific collaboration networks. Proc Natl Acad Sci USA 98(2): 404---409

[21]

Newman MEJ (2002) Spread of epidemic disease on networks. Phys Rev E 66: 016128

[22]

Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2): 167---256

Digital Library

[23]

Newman MEJ, Park J (2003) Why social networks are different from other types of networks. Phys Rev E 68: 036122

[24]

Peng W, Li T (2010) Temporal relation co-clustering on directional social network and author-topic evolution. Knowl Inf Syst (published online: March 2010)

[25]

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

Digital Library

[26]

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

[27]

Wasserman S, Faust K (1994) Social network analysis. Cambridge University Press, Cambridge

[28]

Watts DJ (2002) A simple model of global cascade on random networks. Proc Natl Acad Sci USA 99(9): 5766---5771

[29]

Watts DJ, Dodds PS (2007) Influence, networks, and public opinion formation. J Consum Res 34(4): 441---458

[30]

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)

[31]

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

[32]

Zhuge H, Zhang J (2010) Topological centrality and its applications. J Am Soc Inf Sci Technol 61(9): 1824---1841

Digital Library

Cited By

Al-Garadi MVarathan KRavana SAhmed EMujtaba GKhan MKhan S(2018)Analysis of Online Social Network Connections for Identification of Influential UsersACM Computing Surveys10.1145/315589751:1(1-37)Online publication date: 31-Jan-2018
https://dl.acm.org/doi/10.1145/3155897
Jin DMa XZhang YAbbas HYu H(2018)Information Diffusion Model Based on Social Big DataMobile Networks and Applications10.1007/s11036-018-1004-423:4(717-722)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s11036-018-1004-4
Manaskasemsak BPhuangpanya RRungsawang ABen-Othman JGang FLiu JArai M(2017)Topic-constrained influence maximization in social networksProceedings of the 3rd International Conference on Communication and Information Processing10.1145/3162957.3162997(405-410)Online publication date: 24-Nov-2017
https://dl.acm.org/doi/10.1145/3162957.3162997
Show More Cited By

Recommendations

Selecting Influential Nodes in Social Networks Using Neighborhood Coreness
Abstract
With the proliferation of social networks, the study of the spread of influence has grabbed the attention of researchers from various disciplines. Finding a subset of nodes in a social network that maximizes the spread of influence in the network ...
What is Twitter, a social network or a news media?
WWW '10: Proceedings of the 19th international conference on World wide web

Twitter, a microblogging service less than three years old, commands more than 41 million users as of July 2009 and is growing fast. Twitter users tweet about any topic within the 140-character limit and follow others to receive their tweets. The goal ...
Discovering Influential Nodes for SIS Models in Social Networks
DS '09: Proceedings of the 12th International Conference on Discovery Science

We address the problem of efficiently discovering the influential nodes in a social network under the <em>susceptible/infected/susceptible (SIS) model</em> , a diffusion model where nodes are allowed to be activated multiple times. The computational ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Knowledge and Information Systems

Knowledge and Information Systems Volume 30, Issue 3

March 2012

240 pages

ISSN:0219-1377

Issue’s Table of Contents

Copyright © Copyright © 2012 Springer-Verlag London Limited.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 March 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Al-Garadi MVarathan KRavana SAhmed EMujtaba GKhan MKhan S(2018)Analysis of Online Social Network Connections for Identification of Influential UsersACM Computing Surveys10.1145/315589751:1(1-37)Online publication date: 31-Jan-2018
https://dl.acm.org/doi/10.1145/3155897
Jin DMa XZhang YAbbas HYu H(2018)Information Diffusion Model Based on Social Big DataMobile Networks and Applications10.1007/s11036-018-1004-423:4(717-722)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s11036-018-1004-4
Manaskasemsak BPhuangpanya RRungsawang ABen-Othman JGang FLiu JArai M(2017)Topic-constrained influence maximization in social networksProceedings of the 3rd International Conference on Communication and Information Processing10.1145/3162957.3162997(405-410)Online publication date: 24-Nov-2017
https://dl.acm.org/doi/10.1145/3162957.3162997
Sagharichian MNaderi H(2017)Intelligent and independent processes for overcoming big graphsThe Journal of Supercomputing10.1007/s11227-016-1834-473:4(1438-1466)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s11227-016-1834-4
Marra GUrsino DRicca FTerracina G(2016)Information diffusion in a multi-social-network scenarioKnowledge and Information Systems10.1007/s10115-015-0890-z48:3(619-648)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10115-015-0890-z
Huang LWang WChen XChen J(2016)A Heuristic Method of Identifying Key MicrobloggersProceedings of the 14th International Conference on Inclusive Smart Cities and Digital Health - Volume 967710.1007/978-3-319-39601-9_37(417-426)Online publication date: 25-May-2016
https://dl.acm.org/doi/10.1007/978-3-319-39601-9_37
Zhou CZhang PZang WGuo LChung CBroder AShim KSuel T(2014)Maximizing the long-term integral influence in social networks under the voter modelProceedings of the 23rd International Conference on World Wide Web10.1145/2567948.2577376(423-424)Online publication date: 7-Apr-2014
https://dl.acm.org/doi/10.1145/2567948.2577376
Chen YZhu WPeng WLee WLee S(2014)CIMACM Transactions on Intelligent Systems and Technology10.1145/25325495:2(1-31)Online publication date: 30-Apr-2014
https://dl.acm.org/doi/10.1145/2532549
Peng SWu MWang GYu S(2014)Containing smartphone worm propagation with an influence maximization algorithmComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.09.00474:PB(103-113)Online publication date: 9-Dec-2014
https://dl.acm.org/doi/10.1016/j.comnet.2014.09.004
Hernández CNavarro G(2014)Compressed representations for web and social graphsKnowledge and Information Systems10.1007/s10115-013-0648-440:2(279-313)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/s10115-013-0648-4
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents