nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Time-Bounded Influence Diffusion with Incentives

verfasst von : Gennaro Cordasco, Luisa Gargano, Joseph G. Peters, Adele A. Rescigno, Ugo Vaccaro

Erschienen in: Structural Information and Communication Complexity

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A widely studied model of influence diffusion in social networks represents the network as a graph \(G=(V,E)\) with an influence threshold t(v) for each node. Initially the members of an initial set \(S\subseteq V\) are influenced. During each subsequent round, the set of influenced nodes is augmented by including every node v that has at least t(v) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total of the incentives required to ensure that the process completes within a given number of rounds. The problem is hard to approximate in general networks. We present polynomial-time algorithms for paths, trees, and complete networks.

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 "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

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

Vorheriges Kapitel Communication Complexity in Vertex Partition Whiteboard Model

Nächstes Kapitel Balanced Allocations and Global Clock in Population Protocols: An Accurate Analysis

We will omit the subscript G whenever the graph G is clear from the context.

Notice that this does not exclude the case that v becomes an influenced node at some round \(\ell ' < \ell \).

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

Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: Treewidth governs the complexity of target set selection. Discret. Optim. 8, 87–96 (2011)MathSciNetCrossRef

Chopin, M., Nichterlein, A., Niedermeier, R., Weller, M.: Constant thresholds can make target set selection tractable. In: Even, G., Rawitz, D. (eds.) MedAlg 2012. LNCS, vol. 7659, pp. 120–133. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34862-4_9CrossRef

Coja-Oghlan, A., Feige, U., Krivelevich, M., Reichman, D.: Contagious sets in expanders. In: Proceedings of SODA 2015, pp. 1953–1987 (2015)

Chen, W., Lakshmanan, L.V.S., Castillo, C.: Information and Influence Propagation in Social Networks. Morgan & Claypool, San Rafael (2013)

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

Chiang, C.-Y., Huang, L.-H., Li, B.-J., Wu, J., Yeh, H.-G.: Some results on the target set selection problem. Journal of Comb. Opt. 25(4), 702–715 (2013)MathSciNetCrossRef

Cicalese, F., Cordasco, G., Gargano, L., Milanič, M., Peters, J., Vaccaro, U.: Spread of influence in weighted networks under time and budget constraints. Theor. Comput. Sci. 586, 40–58 (2015)MathSciNetCrossRef

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

10.

Cordasco, G., Gargano, L., Rescigno, A.A.: On finding small sets that influence large networks. Soc. Netw. Anal. Min. 6(94) (2016)

11.

Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Optimizing spread of influence in social networks via partial incentives. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 119–134. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25258-2_9CrossRef

12.

Demaine, E.D., et al.: How to influence people with partial incentives. In: Proceedings of WWW 2014, pp. 937–948 (2014)

13.

Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 57–66 (2001)

14.

Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, Cambridge (2010)CrossRef

15.

Gargano, L., Hell, P., Peters, J.G., Vaccaro, U.: Influence diffusion in social networks under time window constraints. Theor. Comput. Sci. 584, 53–66 (2015)MathSciNetCrossRef

16.

Granovetter, M.: Thresholds models of collective behaviors. Am. J. Sociol. 83(6), 1420–1443 (1978)CrossRef

17.

Kempe, D., Kleinberg, J.M., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003)

18.

Lafond, M., Narayanan, L., Wu, K.: Whom to befriend to influence people. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 340–357. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48314-6_22CrossRef

19.

Narayanan, L., Wu, K.: How to choose friends strategically. In: Das, S., Tixeuil, S. (eds.) SIROCCO 2017. LNCS, vol. 10641, pp. 283–302. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72050-0_17CrossRef

20.

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

21.

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

22.

Reddy, T.V.T., Rangan, C.P.: Variants of spreading messages. J. Graph Algorithms Appl. 15(5), 683–699 (2011)MathSciNetCrossRef

23.

Liu, X., Yang, Z., Wang, W.: Exact solutions for latency-bounded target set selection problem on some special families of graphs. Discret. Appl. Math. 203(C), 111–116 (2016)MathSciNetCrossRef

Titel: Time-Bounded Influence Diffusion with Incentives
verfasst von: Gennaro Cordasco
Luisa Gargano
Joseph G. Peters
Adele A. Rescigno
Ugo Vaccaro
Verlag: Springer International Publishing
Buch: Structural Information and Communication Complexity
Print ISBN: 978-3-030-01324-0

Electronic ISBN: 978-3-030-01325-7

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-01325-7_25

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 "Technik"

Springer Professional "Wirtschaft"

Premium Partner