nach oben

Knowledge and Information Systems

Erschienen in:

29.03.2020 | Regular Paper

A survey on influence maximization in a social network

verfasst von: Suman Banerjee, Mamata Jenamani, Dilip Kumar Pratihar

Erschienen in: Knowledge and Information Systems | Ausgabe 9/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Given a social network with diffusion probabilities as edge weights and a positive integer k, which k nodes should be chosen for initial injection of information to maximize the influence in the network? This problem is popularly known as the Social Influence Maximization Problem (SIM Problem). This is an active area of research in computational social network analysis domain, since one and half decades or so. Due to its practical importance in various domains, such as viral marketing, target advertisement and personalized recommendation, the problem has been studied in different variants, and different solution methodologies have been proposed over the years. This paper presents a survey on the progress in and around SIM Problem. At last, it discusses current research trends and future research directions as well.

Vorheriger Artikel A survey on context awareness in big data analytics for business applications

Nächster Artikel Bayesian network classifiers using ensembles and smoothing

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ackerman E, Ben-Zwi O, Wolfovitz G (2010) Combinatorial model and bounds for target set selection. Theor Comput Sci 411(44–46):4017–4022MathSciNetMATH

Angell R, Schoenebeck G (2017) Dont be greedy: leveraging community structure to find high quality seed sets for influence maximization. In: International conference on web and internet economics. Springer, pp 16–29

Arora A, Galhotra S, Ranu S (2017) Debunking the myths of influence maximization: an in-depth benchmarking study. In: Proceedings of the 2017 ACM international conference on management of data. ACM, pp 651–666

Bakshy E, Hofman JM, Mason WA, Watts DJ (2011) Everyone’s an influencer: quantifying influence on twitter. In: Proceedings of the fourth ACM international conference on Web search and data mining. ACM, pp 65–74

Balogh J, Bollobás B, Morris R (2010) Bootstrap percolation in high dimensions. Comb Probab Comput 19(5–6):643–692MathSciNetMATH

Banerjee P, Chen W, Lakshmanan LV (2019) Maximizing welfare in social networks under a utility driven influence diffusion model. In: Proceedings of the 2019 international conference on management of data. ACM, pp 1078–1095

Banerjee S, Mathew R (2018) An inapproximability result for the target set selection problem on bipartite graphs. arXiv preprint arXiv:1812.01482

Bazgan C, Chopin M, Nichterlein A, Sikora F (2014) Parameterized approximability of maximizing the spread of influence in networks. J Discrete Algorithms 27:54–65MathSciNetMATH

Borgs C, Brautbar M, Chayes J, Lucier B (2014) Maximizing social influence in nearly optimal time. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 946–957

10.

Bozorgi A, Haghighi H, Zahedi MS, Rezvani M (2016) Incim: A community-based algorithm for influence maximization problem under the linear threshold model. Inf Process Manag 52(6):1188–1199

11.

Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw ISDN Syst 30(1–7):107–117

12.

Bucur D, Iacca G (2016) Influence maximization in social networks with genetic algorithms. In: European conference on the applications of evolutionary computation. Springer, pp 379–392

13.

Campbell WM, Dagli CK, Weinstein CJ (2013) Social network analysis with content and graphs. Linc Lab J 20(1):61–81

14.

Centola D (2010) The spread of behavior in an online social network experiment. Science 329(5996):1194–1197

15.

Chakraborty T, Dalmia A, Mukherjee A, Ganguly N (2017) Metrics for community analysis: a survey. ACM Comput Surv (CSUR) 50(4):54

16.

Charikar M, Naamad Y, Wirth A (2016) On approximating target set selection. In: LIPIcs-Leibniz international proceedings in informatics, vol 60. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

17.

Chen N (2009) On the approximability of influence in social networks. SIAM J Discrete Math 23(3):1400–1415MathSciNetMATH

18.

Chen S, Fan J, Li G, Feng J, Kl Tan, Tang J (2015) Online topic-aware influence maximization. Proc VLDB Endow 8(6):666–677

19.

Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 199–208

20.

Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1029–1038

21.

Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model. In: 2010 IEEE 10th international conference on data mining (ICDM). IEEE, pp 88–97

22.

Chen W, Collins A, Cummings R, Ke T, Liu Z, Rincon D, Sun X, Wang Y, Wei W, Yuan Y (2011) Influence maximization in social networks when negative opinions may emerge and propagate. In: Proceedings of the 2011 SIAM international conference on data mining. SIAM, pp 379–390

23.

Chen Y, Chang S, Chou C, Peng W, Lee S (2012) Exploring community structures for influence maximization in social networks. In: Proceedings of the 6th SNA-KDD workshop on social network mining and analysis held in conjunction with KDD12 (SNA-KDD12), pp 1–6

24.

Chen YC, Zhu WY, Peng WC, Lee WC, Lee SY (2014) Cim: community-based influence maximization in social networks. ACM Trans Intell Syst Technol (TIST) 5(2):25

25.

Cheng S, Shen H, Huang J, Zhang G, Cheng X (2013) Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In: Proceedings of the 22nd ACM international conference on information & knowledge management. ACM, pp 509–518

26.

Chopin M, Nichterlein A, Niedermeier R, Weller M (2012) Constant thresholds can make target set selection tractable. Springer, Berlin, pp 120–133MATH

27.

Chopin M, Nichterlein A, Niedermeier R, Weller M (2014) Constant thresholds can make target set selection tractable. Theory Comput Syst 55(1):61–83MathSciNetMATH

28.

Cicalese F, Cordasco G, Gargano L, Milanič M, Vaccaro U (2014) Latency-bounded target set selection in social networks. Theor Comput Sci 535:1–15MathSciNetMATH

29.

Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111

30.

Cohen E, Delling D, Pajor T, Werneck RF (2014) Sketch-based influence maximization and computation: scaling up with guarantees. In: Proceedings of the 23rd ACM international conference on conference on information and knowledge management. ACM, pp 629–638

31.

Cordasco G, Gargano L, Mecchia M, Rescigno AA, Vaccaro U (2015a) A fast and effective heuristic for discovering small target sets in social networks. In: Combinatorial optimization and applications. Springer, pp 193–208

32.

Cordasco G, Gargano L, Rescigno AA (2015b) Influence propagation over large scale social networks. In: Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015. ACM, pp 1531–1538

33.

Cordasco G, Gargano L, Rescigno AA (2016) Active spreading in networks. In: ICTCS, pp 149–162

34.

Cowan R, Jonard N (2004) Network structure and the diffusion of knowledge. J Econ Dyn Control 28(8):1557–1575MathSciNetMATH

35.

Dhamal S, Prabuchandran K, Narahari Y (2016) Information diffusion in social networks in two phases. IEEE Trans Netw Sci Eng 3(4):197–210MathSciNet

36.

Diestel R (2005) Graph theory. 2005. Grad Texts in Math 101

37.

Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 57–66

38.

Downey RG, Fellows MR (2012) Parameterized complexity. Springer, BerlinMATH

39.

Downey RG, Fellows MR (2013) Fundamentals of parameterized complexity, vol 4. Springer, BerlinMATH

40.

Downey RG, Fellows MR, Regan KW (1998) Parameterized circuit complexity and the W hierarchy. Theor Comput Sci 191(1–2):97–115MathSciNetMATH

41.

Dreyer PA, Roberts FS (2009) Irreversible k-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl Math 157(7):1615–1627MathSciNetMATH

42.

Epasto A, Mahmoody A, Upfal E (2017) Real-time targeted-influence queries over large graphs. In: Proceedings of the 2017 IEEE/ACM international conference on advances in social networks analysis and mining 2017. ACM, pp 224–231

43.

Feige U, Goemans M (1995) Approximating the value of two power proof systems, with applications to max 2sat and max dicut

44.

Fortunato S (2010) Community detection in graphs. Phys Rep 486(3):75–174MathSciNet

45.

Freeman LC (1978) Centrality in social networks conceptual clarification. Soc Netw 1(3):215–239

46.

Galhotra S, Arora A, Virinchi S, Roy S (2015) Asim: a scalable algorithm for influence maximization under the independent cascade model. In: Proceedings of the 24th international conference on world wide web. ACM, pp 35–36

47.

Galhotra S, Arora A, Roy S (2016) Holistic influence maximization: combining scalability and efficiency with opinion-aware models. In: Proceedings of the 2016 international conference on management of data. ACM, pp 743–758

48.

Garey MR, Johnson DS (2002) Computers and intractability, vol 29. W. H. Freeman, New York

49.

Gionis A, Terzi E, Tsaparas P (2013) Opinion maximization in social networks. In: Proceedings of the 2013 SIAM international conference on data mining. SIAM, pp 387–395

50.

Goel S, Watts DJ, Goldstein DG (2012) The structure of online diffusion networks. In: Proceedings of the 13th ACM conference on electronic commerce. ACM, pp 623–638

51.

Gong M, Yan J, Shen B, Ma L, Cai Q (2016) Influence maximization in social networks based on discrete particle swarm optimization. Inf Sci 367:600–614

52.

Goyal A, Bonchi F, Lakshmanan LV (2010) Learning influence probabilities in social networks. In: Proceedings of the third ACM international conference on Web search and data mining. ACM, pp 241–250

53.

Goyal A, Bonchi F, Lakshmanan LV (2011a) A data-based approach to social influence maximization. Proc. VLDB Endow. 5(1):73–84

54.

Goyal A, Lu W, Lakshmanan LV (2011b) Celf++: optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference companion on world wide web. ACM, pp 47–48

55.

Goyal A, Lu W, Lakshmanan LV (2011c) Simpath: an efficient algorithm for influence maximization under the linear threshold model. In: 2011 IEEE 11th international conference on data mining (ICDM). IEEE, pp 211–220

56.

Gruhl D, Guha R, Liben-Nowell D, Tomkins A (2004) Information diffusion through blogspace. In: Proceedings of the 13th international conference on world wide web. ACM, pp 491–501

57.

Han K, Huang K, Xiao X, Tang J, Sun A, Tang X (2018) Efficient algorithms for adaptive influence maximization. In: Proceedings of the VLDB endowment, vol 11, no 9

58.

Harant J, Pruchnewski A, Voigt M (1999) On dominating sets and independent sets of graphs. Comb Probab Comput 8(6):547–553MathSciNetMATH

59.

Heidari N (2016) Modeling information diffusion in social networks. arXiv preprint arXiv:1603.02178

60.

Ienco D, Bonchi F, Castillo C (2010) The meme ranking problem: maximizing microblogging virality. In: 2010 IEEE international conference on data mining workshops (ICDMW). IEEE, pp 328–335

61.

Jiang Q, Song G, Cong G, Wang Y, Si W, Xie K (2011) Simulated annealing based influence maximization in social networks. In: AAAI, vol 11, pp 127–132

62.

Jung K, Heo W, Chen W (2012) Irie: scalable and robust influence maximization in social networks. In: 2012 IEEE 12th international conference on data mining (ICDM). IEEE, pp 918–923

63.

Kang C, Kraus S, Molinaro C, Spezzano F, Subrahmanian V (2016) Diffusion centrality: a paradigm to maximize spread in social networks. Artif Intell 239:70–96MathSciNetMATH

64.

Karp RM (1972) Reducibility among combinatorial problems. In: Complexity of computer computations. Springer, pp 85–103

65.

Kasprzak R (2012) Diffusion in networks. J Telecommun Inf Technol 99–106

66.

Ke X, Khan A, Cong G (2018) Finding seeds and relevant tags jointly: for targeted influence maximization in social networks. In: Proceedings of the 2018 international conference on management of data. ACM, pp 1097–1111

67.

Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 137–146

68.

Kempe D, Kleinberg JM, Tardos É (2005) Influential nodes in a diffusion model for social networks. In: ICALP, vol 5. Springer, pp 1127–1138

69.

Kempe D, Kleinberg JM, Tardos É (2015) Maximizing the spread of influence through a social network. Theory Comput 11(4):105–147MathSciNetMATH

70.

Khuller S, Moss A, Naor JS (1999) The budgeted maximum coverage problem. Inf Process Lett 70(1):39–45MathSciNetMATH

71.

Kim J, Kim SK, Yu H (2013) Scalable and parallelizable processing of influence maximization for large-scale social networks? In: 2013 IEEE 29th international conference on data engineering (ICDE). IEEE, pp 266–277

72.

Kimura M, Saito K (2006) Tractable models for information diffusion in social networks. In: Knowledge discovery in databases: PKDD 2006, pp 259–271

73.

Kimura M, Saito K, Nakano R, Motoda H (2009) Finding influential nodes in a social network from information diffusion data. In: Social computing and behavioral modeling, pp 1–8

74.

Klasing R, Laforest C (2004) Hardness results and approximation algorithms of k-tuple domination in graphs. Inf Process Lett 89(2):75–83MathSciNetMATH

75.

Kortsarz G (2001) On the hardness of approximating spanners. Algorithmica 30(3):432–450MathSciNetMATH

76.

Landherr A, Friedl B, Heidemann J (2010) A critical review of centrality measures in social networks. Bus Inf Syst Eng 2(6):371–385

77.

Lee JR, Chung CW (2015) A query approach for influence maximization on specific users in social networks. IEEE Trans Knowl Data Eng 27(2):340–353MathSciNet

78.

Leskovec J, Kleinberg J, Faloutsos C (2005) Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. ACM, pp 177–187

79.

Leskovec J, Adamic LA, Huberman BA (2007a) The dynamics of viral marketing. ACM Trans Web (TWEB) 1(1):5

80.

Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007b) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 420–429

81.

Li X, Cheng X, Su S, Sun C (2018a) Community-based seeds selection algorithm for location aware influence maximization. Neurocomputing 275:1601–1613

82.

Li Y, Chen W, Wang Y, Zhang ZL (2013) Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. In: Proceedings of the sixth ACM international conference on web search and data mining. ACM, pp 657–666

83.

Li Y, Zhang D, Tan KL (2015) Real-time targeted influence maximization for online advertisements. Proc VLDB Endow 8(10):1070–1081

84.

Li Y, Fan J, Wang Y, Tan KL (2018b) Influence maximization on social graphs: a survey. IEEE Trans Knowl Data Eng 30:1852–1872

85.

Liu B (2011) Social network analysis. In: Web data mining. Springer, Berlin, pp 269–309

86.

Liu SJ, Chen CY, Tsai CW (2017) An effective simulated annealing for influence maximization problem of online social networks. Proc Comput Sci 113:478–483

87.

Ma H, Yang H, Lyu MR, King I (2008) Mining social networks using heat diffusion processes for marketing candidates selection. In: Proceedings of the 17th ACM conference on information and knowledge management. ACM, pp 233–242

88.

Maehara T, Suzuki H, Ishihata M (2017) Exact computation of influence spread by binary decision diagrams. In: Proceedings of the 26th international conference on world wide web, international world wide web conferences steering committee, pp 947–956

89.

Narayanam R, Narahari Y (2011) A shapley value-based approach to discover influential nodes in social networks. IEEE Trans Autom Sci Eng 8(1):130–147

90.

Nekovee M, Moreno Y, Bianconi G, Marsili M (2007) Theory of rumour spreading in complex social networks. Phys A 374(1):457–470

91.

Nguyen H, Zheng R (2012) On budgeted influence maximization in social networks. arXiv preprint arXiv:1204.4491

92.

Nguyen H, Zheng R (2013) On budgeted influence maximization in social networks. IEEE J Sel Areas Commun 31(6):1084–1094

93.

Nguyen HT, Dinh TN, Thai MT (2016a) Cost-aware targeted viral marketing in billion-scale networks. In: IEEE INFOCOM 2016-the 35th annual IEEE international conference on computer communications. IEEE, pp 1–9

94.

Nguyen HT, Thai MT, Dinh TN (2016b) Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks. In: Proceedings of the 2016 international conference on management of data. ACM, pp 695–710

95.

Nguyen HT, Ghosh P, Mayo ML, Dinh TN (2017) Social influence spectrum at scale: near-optimal solutions for multiple budgets at once. ACM Trans Inf Syst (TOIS) 36(2):14

96.

Nguyen HT, Thai MT, Dinh TN (2017) A billion-scale approximation algorithm for maximizing benefit in viral marketing. IEEE/ACM Trans Netw 25:2419–2429

97.

Nichterlein A, Niedermeier R, Uhlmann J, Weller M (2010) On tractable cases of target set selection. In: Algorithms and computation, pp 378–389

98.

Nichterlein A, Niedermeier R, Uhlmann J, Weller M (2013) On tractable cases of target set selection. Soc Netw Anal Min 3(2):233–256MATH

99.

Peleg D (2002) Local majorities, coalitions and monopolies in graphs: a review. Theor Comput Sci 282(2):231–257MathSciNetMATH

100.

Peng S, Zhou Y, Cao L, Yu S, Niu J, Jia W (2018) Influence analysis in social networks: a survey. J Netw Comput Appl 106:17–32

101.

Raghavan S, Zhang R (2015) Weighted target set selection on social networks. Technical report, Working paper, University of Maryland

102.

Rahimkhani K, Aleahmad A, Rahgozar M, Moeini A (2015) A fast algorithm for finding most influential people based on the linear threshold model. Expert Syst Appl 42(3):1353–1361

103.

Raman V, Saurabh S, Srihari S (2008) Parameterized algorithms for generalized domination. Lect Notes Comput Sci 5165:116–126MathSciNetMATH

104.

Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 61–70

105.

Saito K, Nakano R, Kimura M (2008) Prediction of information diffusion probabilities for independent cascade model. In: Knowledge-based intelligent information and engineering systems. Springer, pp 67–75

106.

Saito K, Kimura M, Ohara K, Motoda H (2010) Selecting information diffusion models over social networks for behavioral analysis. In: Machine learning and knowledge discovery in databases, pp 180–195

107.

Saito K, Ohara K, Yamagishi Y, Kimura M, Motoda H (2011) Learning diffusion probability based on node attributes in social networks. In: International symposium on methodologies for intelligent systems. Springer, pp 153–162

108.

Salathé M, Kazandjieva M, Lee JW, Levis P, Feldman MW, Jones JH (2010) A high-resolution human contact network for infectious disease transmission. Proc Nat Acad Sci 107(51):22020–22025

109.

Sankar CP, Asharaf S, Kumar KS (2016) Learning from bees: an approach for influence maximization on viral campaigns. PLoS ONE 11(12):e0168125

110.

Shakarian P, Bhatnagar A, Aleali A, Shaabani E, Guo R (2015) The independent cascade and linear threshold models. In: Diffusion in social networks. Springer, pp 35–48

111.

Shang J, Zhou S, Li X, Liu L, Wu H (2017) Cofim: a community-based framework for influence maximization on large-scale networks. Knowl Based Syst 117:88–100

112.

Song X, Tseng BL, Lin CY, Sun MT (2006) Personalized recommendation driven by information flow. In: Proceedings of the 29th annual international ACM SIGIR conference on research and development in information retrieval. ACM, pp 509–516

113.

Sun J, Tang J (2011) A survey of models and algorithms for social influence analysis. In: Social network data analytics. Springer, Berlin, pp 177–214

114.

Sun L, Huang W, Yu PS, Chen W (2018) Multi-round influence maximization. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. ACM, pp 2249–2258

115.

Tabak BM, Takami M, Rocha JM, Cajueiro DO, Souza SR (2014) Directed clustering coefficient as a measure of systemic risk in complex banking networks. Phys A 394:211–216

116.

Tang J, Tang X, Yuan J (2017) Influence maximization meets efficiency and effectiveness: a hop-based approach. In: Proceedings of the 2017 IEEE/ACM international conference on advances in social networks analysis and mining 2017. ACM, pp 64–71

117.

Tang J, Tang X, Yuan J (2018) An efficient and effective hop-based approach for influence maximization in social networks. Soc Netw Anal Min 8(1):10

118.

Tang Y, Xiao X, Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD international conference on management of data. ACM, pp 75–86

119.

Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data. ACM, pp 1539–1554

120.

Tong G, Wu W, Tang S, Du DZ (2017) Adaptive influence maximization in dynamic social networks. IEEE/ACM Trans Netw (TON) 25(1):112–125

121.

Tovey CA (1984) A simplified np-complete satisfiability problem. Discrete Appl Math 8(1):85–89MathSciNetMATH

122.

Tsai CW, Yang YC, Chiang MC (2015) A genetic newgreedy algorithm for influence maximization in social network. In: 2015 IEEE international conference on systems, man, and cybernetics (SMC). IEEE, pp 2549–2554

123.

Valente TW (1995) Network models of the diffusion of innovations

124.

Valente TW (1996) Social network thresholds in the diffusion of innovations. Soc Netw 18(1):69–89

125.

Varshney D, Kumar S, Gupta V (2017) Predicting information diffusion probabilities in social networks: a Bayesian networks based approach. Knowl Based Syst 133:66–76

126.

Wang C, Chen W, Wang Y (2012) Scalable influence maximization for independent cascade model in large-scale social networks. Data Min Knowl Disc 25(3):545MathSciNetMATH

127.

Wang F, Jiang W, Li X, Wang G (2017a) Maximizing positive influence spread in online social networks via fluid dynamics. Future Gener Comput Syst 86:1491–1502

128.

Wang Q, Gong M, Song C, Wang S (2017b) Discrete particle swarm optimization based influence maximization in complex networks. In: 2017 IEEE congress on evolutionary computation (CEC). IEEE, pp 488–494

129.

Wang T, Chen Y, Zhang Z, Xu T, Jin L, Hui P, Deng B, Li X (2011) Understanding graph sampling algorithms for social network analysis. In: 2011 31st international conference on distributed computing systems workshops (ICDCSW). IEEE, pp 123–128

130.

Wang Y, Cong G, Song G, Xie K (2010) Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1039–1048

131.

Weng J, Lim EP, Jiang J, He Q (2010) Twitterrank: finding topic-sensitive influential twitterers. In: Proceedings of the third ACM international conference on Web search and data mining. ACM, pp 261–270

132.

Wilder B, Immorlica N, Rice E, Tambe M (2017) Influence maximization with an unknown network by exploiting community structure. In: SocInf@ IJCAI, pp 2–7

133.

Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, CambridgeMATH

134.

Wilson C, Boe B, Sala A, Puttaswamy KP, Zhao BY (2009) User interactions in social networks and their implications. In: Proceedings of the 4th ACM European conference on computer systems. ACM, pp 205–218

135.

Wu H, Yue K, Fu X, Wang Y, Liu W (2016) Parallel seed selection for influence maximization based on k-shell decomposition. In: International conference on collaborative computing: networking, applications and worksharing. Springer, pp 27–36

136.

Wu HH, Küçükyavuz S (2017) A two-stage stochastic programming approach for influence maximization in social networks. Comput Optim Appl 69:1–33MathSciNet

137.

Xie J, Szymanski BK, Liu X (2011) Slpa: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: 2011 IEEE 11th international conference on data mining workshops (ICDMW). IEEE, pp 344–349

138.

Xu B, Liu L (2010) Information diffusion through online social networks. In: 2010 IEEE international conference on emergency management and management sciences (ICEMMS). IEEE, pp 53–56

139.

Yang J, Leskovec J (2010) Modeling information diffusion in implicit networks. In: 2010 IEEE 10th international conference on data mining (ICDM). IEEE, pp 599–608

140.

Yang XS (2010) Nature-inspired metaheuristic algorithms. Luniver Press, Oxford

141.

Yang XS, Chien SF, Ting TO (2014) Computational intelligence and metaheuristic algorithms with applications. Sci World J 2014:425853

142.

Yi H, Duan Q, Liao TW (2013) Three improved hybrid metaheuristic algorithms for engineering design optimization. Appl Soft Comput 13(5):2433–2444

143.

Zhang H, Dinh TN, Thai MT (2013) Maximizing the spread of positive influence in online social networks. In: 2013 IEEE 33rd international conference on distributed computing systems (ICDCS). IEEE, pp 317–326

144.

Zhang H, Mishra S, Thai MT, Wu J, Wang Y (2014) Recent advances in information diffusion and influence maximization in complex social networks. Oppor Mobile Soc Netw 37(1.1):37

145.

Zhang K, Du H, Feldman MW (2017) Maximizing influence in a social network: improved results using a genetic algorithm. Phys A 478:20–30MATH

146.

Zhu T, Wang B, Wu B, Zhu C (2014) Maximizing the spread of influence ranking in social networks. Inf Sci 278:535–544MathSciNet

147.

Zhu Y, Wu W, Bi Y, Wu L, Jiang Y, Xu W (2015) Better approximation algorithms for influence maximization in online social networks. J Comb Optim 30(1):97–108MathSciNetMATH

148.

Zhuang H, Sun Y, Tang J, Zhang J, Sun X (2013) Influence maximization in dynamic social networks. In: 2013 IEEE 13th international conference on data mining (ICDM). IEEE, pp 1313–1318

149.

Zong Z, Li B, Hu C (2014) dirier: distributed influence maximization in social network. In: 2014 20th IEEE international conference on parallel and distributed systems (ICPADS). IEEE, pp 119–125

150.

Zou CC, Towsley D, Gong W (2007) Modeling and simulation study of the propagation and defense of internet e-mail worms. IEEE Trans Dependable Secure Comput 4(2):105–118

Titel: A survey on influence maximization in a social network
verfasst von: Suman Banerjee
Mamata Jenamani
Dilip Kumar Pratihar
Publikationsdatum: 29.03.2020
Verlag: Springer London
Erschienen in: Knowledge and Information Systems / Ausgabe 9/2020
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI: https://doi.org/10.1007/s10115-020-01461-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 9/2020

TAILOR: time-aware facility location recommendation based on massive trajectories

EAFIM: efficient apriori-based frequent itemset mining algorithm on Spark for big transactional data

Tell me something my friends do not know: diversity maximization in social networks

Rule extraction from neural network trained using deep belief network and back propagation

Decision model change patterns for dynamic system evolution

Bayesian network classifiers using ensembles and smoothing

Premium Partner