Top

Published in:

2018 | OriginalPaper | Chapter

Time-Bounded Influence Diffusion with Incentives

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

Published in: Structural Information and Communication Complexity

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Communication Complexity in Vertex Partition Whiteboard Model

next chapter 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

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

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

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

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner