Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Knowledge and Information Systems
Erschienen in: Knowledge and Information Systems 5/2021

19.03.2021 | Regular Paper

Learning diffusion model-free and efficient influence function for influence maximization from information cascades

verfasst von: Qi Cao, Huawei Shen, Jinhua Gao, Xueqi Cheng

Erschienen in: Knowledge and Information Systems | Ausgabe 5/2021

Einloggen

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

search-config
loading …

Abstract

When considering the problem of influence maximization from information cascades, one essential component is influence estimation. Traditional approaches for influence estimation generally follow a two-stage framework, i.e., learn a hypothetical diffusion model from information cascades and then calculate the influence spread according to the learned diffusion model via Monte Carlo simulation or heuristic approximation. The effectiveness of these approaches heavily relies on the correctness of the diffusion model, suffering from the problem of model misspecification. Meanwhile, these approaches are inefficient when influence estimation is conducted via lots of Monte Carlo simulations. In this paper, without assuming a diffusion model a priori, we directly learn a monotone and submodular influence function from information cascades. Once the influence function is obtained, greedy algorithm is applied to efficiently solve influence maximization. Experimental results on both synthetic and real-world datasets show the effectiveness and efficiency of the learned influence function for both influence estimation and influence maximization tasks.
Vorheriger Artikel Kernel-based regression via a novel robust loss function and iteratively reweighted least squares
Nächster Artikel Expert-driven trace clustering with instance-level constraints

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
Literatur
1.
Aslay C, Lakshmanan LV, Lu W, Xiao X (2018) Influence maximization in online social networks. In: Proceedings of the 11th ACM International Conference on Web Search and Data Mining. ACM, pp 775–776
2.
Balkanski E, Immorlica N, Singer Y (2017) The importance of communities for learning to influence. In: Proceedings of the 31th International Conference on Neural Information Processing Systems. Curran Associates Inc, pp 5862–5871
3.
Balkanski E, Rubinstein A, Singer Y (2017) The limitations of optimization from samples. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ACM, pp 1016–1027
4.
Barbieri N, Bonchi F, Manco G (2013) Topic-aware social influence propagation models. Knowl Inf Syst 37:555–584CrossRef
5.
Bi B, Tian Y, Sismanis Y, Balmin A, Cho J (2014) Scalable topic-specific influence analysis on microblogs. In: Proceedings of the 7th ACM International Conference on Web Search and Data Mining. ACM, pp 513–522
6.
Borgs C, Brautbar M, Chayes J, Lucier B (2014) Maximizing social influence in nearly optimal time. In: Proceedings of the 25th annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, pp 946–957
7.
Bourigault S, Lamprier S, Gallinari P (2016) Representation learning for information diffusion through social networks: an embedded cascade model. In: Proceedings of the 9th ACM international conference on web search and data mining. ACM, pp 573–582
8.
Cao Q, Shen H, Cen K, Ouyang W, Cheng X (2017) Deephawkes: Bridging the gap between prediction and understanding of information cascades. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. ACM, pp 1149–1158
9.
Chen W, Wang C, Wang Y (2010a) 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
10.
Chen W, Yuan Y, Zhang L (2010b) Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In Proceedings of the 2010 IEEE International Conference on Data Mining. ACM, pp 88–97
11.
Chen W, Lu W, Zhang N (2012) Time-critical influence maximization in social networks with time-delayed diffusion process. In: Proceedings of the 26th AAAI conference on artificial intelligence. AAAI Press, pp 592–598
12.
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 and knowledge management. ACM, pp 509–518
13.
Cheng S, Shen H, Huang J, Chen W, Cheng X (2014) IMRank: Influence maximization via finding self-consistent ranking. In: Proceedings of the 37th International ACM sigir conference on research and development in information retrieval. ACM, pp 475–484
14.
Du N, Liang Y, Balcan M, Song L (2014) Influence function learning in information diffusion networks. In: Proceedings of the 31st International conference on machine learning. PMLR, pp 2016–2024
15.
Feng S, Cong G, Khan A, Li X, Liu Y, Chee YM (2018) Inf2vec: latent representation model for social influence embedding. In: Proceedings of the 34th international conference on data engineering. IEEE, pp 941–952
16.
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
17.
Goldenberg J, Libai B, Muller E (2001) Talk of the network: a complex systems look at the underlying process of word-of-mouth. Mark Lett 12(3):211–223CrossRef
18.
Gomez-Rodriguez M, Balduzzi D, Schlkopf B (2011) Uncovering the temporal dynamics of diffusion networks. In: Proceedings of the 28th international conference on international conference on machine learning. Omnipress, pp 561–568
19.
Goyal A, Bonchi F, Lakshmanan LV (2010) Learning influence probabilities in social networks. In: Proceedings of the 3rd ACM international conference on web search and data mining. ACM, pp 241–250
20.
Goyal A, Bonchi F, Lakshmanan LV (2011a) A data-based approach to social influence maximization. Proc VLDB Endow 5(1):73–84CrossRef
21.
Goyal A, Lu W, Lakshmanan LV (2011b) SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. In: Proceedings of the 2011 IEEE 11th international conference on data mining. IEEE, pp 211–220
22.
Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420–1443CrossRef
23.
He X, Xu K, Kempe D, Liu Y (2016) Learning influence functions from incomplete observations. In: Proceedings of the 30th international conference on neural information processing systems. Curran Associates Inc, pp 2073–2081
24.
Huang J, Cheng XQ, Shen HW, Zhou T, Jin X (2012) Exploring social influence via posterior effect of word-of-mouth recommendations. In: Proceedings of the 5th ACM international conference on web search and data mining. ACM, pp 573–582
25.
Hung HJ, Shuai HH, Yang DN, Huang LH, Lee WC, Pei J, Chen MS (2016) When social influence meets item inference. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 915–924
26.
Kempe D, Kleinberg J, Tardos (2003) Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 137-146
27.
28.
Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) 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
29.
Leskovec J, Chakrabarti D, Kleinberg J, Faloutsos C, Ghahramani Z (2010) Kronecker graphs: an approach to modeling networks. J Mach Learn Res 11(2):985–1042MathSciNetMATH
30.
Li G, Chen S, Feng J, Tan KL, Li WS (2014) Efficient location-aware influence maximization. In: Proceedings of the 2014 ACM SIGMOD international conference on management of data. ACM, pp 87–98
31.
Li Y, Fan J, Wang Y, Tan KL (2018) Influence maximization on social graphs: a survey. IEEE Trans Knowl Data Eng 30(10):1852–1872CrossRef
32.
Lin T, Li J, Chen W (2015) Stochastic online greedy learning with semi-bandit feedbacks. In: Proceedings of the 28th International Conference on Neural Information Processing Systems. pp 352–360, MIT Press, Cambridge.
33.
Liu B, Cong G, Zeng Y, Xu D, Chee YM (2013) Influence spreading path and its application to the time constrained social influence maximization problem and beyond. IEEE Trans Knowl Data Eng 26(8):1904–1917CrossRef
34.
Manaskasemsak B, Phuangpanya R, Rungsawang A (2017) Topic-constrained influence maximization in social networks. In: Proceedings of the 3rd international conference on communication and information processing. ACM, pp 405–410
35.
Mathioudakis M, Bonchi F, Castillo C, Gionis A, Ukkonen A (2011) Sparsification of influence networks. In: Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 529–537
36.
Narasimhan H, Parkes DC, Singer Y (2015) Learnability of influence in networks. In: Proceedings of the 29th international conference on neural information processing systems. pp 3186-3194. MIT Press, Cambridege
37.
Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functionsI. Math Program 14(1):265–294CrossRef
38.
Netrapalli P, Sanghavi S (2012) Learning the graph of epidemic cascades. In: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on measurement and modeling of computer systems. ACM, pp 211-222
39.
Nguyen HT, Thai MT, Dinh TN (2016) 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
40.
Ohsaka N, Akiba T, Yoshida Y, Kawarabayashi KI (2014). Fast and accurate influence maximization on large networks with pruned Monte-Carlo simulations. In: Proceedings of the 28th AAAI conference on artificial intelligence. pp 138–144. AAAI Press
41.
Saito K, Nakano R, Kimura M (2008) Prediction of Information Diffusion Probabilities for Independent Cascade Model. In: Proceedings of the 12th international conference on Knowledge-Based Intelligent Information and Engineering Systems. pp 67–75. Springer, Berlin
42.
Samadi M, Nagi R, Semenov A, Nikolaev A (2018) Seed activation scheduling for influence maximization in social networks. Omega 77:96–114CrossRef
43.
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
44.
Vaswani S, Kveton B, Wen Z, Ghavamzadeh M, Lakshmanan LV, Schmidt M (2017) Model-independent online learning for influence maximization. In: Proceedings of the 34th international conference on machine learning. PMLR, pp 3530–3539
45.
Wang Y, Shen H, Liu S, Cheng X (2015) Learning user-specific latent influence and susceptibility from information cascades. In: Proceedings of the 29th AAAI conference on artificial intelligence. pp 477–483, AAAI Press
46.
Wang X, Zhang Y, Zhang W, Lin X (2017) Bring order into the samples: a novel scalable method for influence maximization. IEEE Trans Knowl Data Eng 29(2):243–256CrossRef
47.
Wang X, Zhang Y, Zhang W, Lin X (2017) Efficient distance-aware influence maximization in geo-social networks. IEEE Trans Knowl Data Eng 29(3):599–612CrossRef
48.
Wen Z, Kveton B, Valko M, Vaswani S (2017) Online influence maximization under independent cascade model with semi-bandit feedback. In: Proceedings of the 31st international conference on neural information processing systems. pp 3026–3036. Curran Associates Inc
49.
Wilder B, Immorlica N, Rice E, Tambe M (2018) Maximizing influence in an unknown social network. In: Proceedings of the 32nd AAAI conference on artificial intelligence. pp 4743–4750. AAAI Press
50.
Yu H, Kim SK, Kim J (2013) Scalable and parallelizable processing of influence maximization for large-scale social networks?. In: Proceedings of the 2013 IEEE international conference on data engineering. IEEE, pp 266-277
51.
Zhang C, Shou L, Chen K, Chen G, Bei Y (2012) Evaluating geo-social influence in location-based social networks. In: Proceedings of the 21st ACM international conference on information and knowledge management. ACM, pp 1442-1451
Metadaten
Titel
Learning diffusion model-free and efficient influence function for influence maximization from information cascades
verfasst von
Qi Cao
Huawei Shen
Jinhua Gao
Xueqi Cheng
Publikationsdatum
19.03.2021
Verlag
Springer London
Erschienen in
Knowledge and Information Systems / Ausgabe 5/2021
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI
https://doi.org/10.1007/s10115-021-01556-6

Weitere Artikel der Ausgabe 5/2021

Knowledge and Information Systems 5/2021 Zur Ausgabe

Regular Paper

Cost-sensitive selection of variables by ensemble of model sequences

Regular Paper

PPNW: personalized pairwise novelty loss weighting for novel recommendation

Regular Paper

Mining discriminative itemsets in data streams using the tilted-time window model

Regular Paper

Unifying community detection and network embedding in attributed networks

Regular Paper

Kernel-based regression via a novel robust loss function and iteratively reweighted least squares

Regular Paper

A scalable framework for large time series prediction