Abstract
We study a combinatorial model of the spread of influence in networks that generalizes existing schemata recently proposed in the literature. In our model agents change behaviors/opinions on the basis of information collected from their neighbors in a time interval of bounded size whereas agents are assumed to have unbounded memory in previously studied scenarios. In our mathematical framework, one is given a network G = (V,E), an integer value t(v) for each node v ∈ V, and a time window size λ. The goal is to determine a small set of nodes (target set) that influences the whole graph. The spread of influence proceeds in rounds as follows: initially all nodes in the target set are influenced; subsequently, in each round, any uninfluenced node v becomes influenced if the number of its neighbors that have been influenced in the previous λ rounds is greater than or equal to t(v). We prove that the problem of finding a minimum cardinality target set that influences the whole network G is hard to approximate within a polylogarithmic factor. On the positive side, we design exact polynomial time algorithms for paths, rings, trees, and complete graphs.
This research was supported in part by the Ebco Eppich Endowment Fund at Simon Fraser University and by NSERC of Canada.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-319-03578-9_29
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ackerman, E., Ben-Zwi, O., Wolfovitz, G.: Combinatorial model and bounds for target set selection. Theoretical Computer Science 411, 4017–4022 (2010)
Anderson, R.M., May, R.M.: Infectious Diseases of Humans: Dynamics and Control. Oxford University Press (1991)
Banos, R.A., Borge-Holthoefer, J., Moreno, Y.: The role of hidden influentials in the diffusion of online information cascades. arXiv:1303.4629v1 [physics.soc-ph] (2013)
Barrat, A., Barthelemy, M., Vespignani, A.: Dynamical Processes on Complex Networks. Cambridge University Press (2012)
Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized Approximability of Maximizing the Spread of Influence in Networks. arXiv:1303.6907 [cs.DS]
Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: Treewidth governs the complexity of target set selection. Discrete Optimization 8, 87–96 (2011)
Bettencourt, L.M.A., Cintron-Arias, A., Kaiser, D.I., Castillo-Chavez, C.: The power of a good idea: Quantitative modeling of the spread of ideas from epidemiological models. Physica A 364, 513–536 (2006)
Bikhchandani, S., Hirshleifer, D., Welch, I.: A theory of fads, customs, and cultural change as informational cascades. Journal of Political Economy 100, 992–1026 (1992)
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.-U.: Complex Networks: Structure and Dynamics. Physics Reports 472, 175–308 (2006)
Centeno, C.C., Dourado, M.C., Penso, L.D., Rautenbach, D., Szwarcfiter, J.L.: Irreversible conversion of graphs. Theoretical Computer Science 412, 3693–3700 (2011)
Centola, D.: The spread of behavior in an online social network experiment. Science 329, 1194–1197 (2010)
Centola, D., Macy, M.: Complex contagions and the weakness of long ties. American Journal of Sociology 113, 702–734 (2007)
Chen, N.: On the approximability of influence in social networks. SIAM J. Discrete Math. 23, 1400–1415 (2009)
Chiang, C.Y., Huang, L.H., Huang, W.T., Yeh, H.G.: The Target Set Selection Problem on Cycle Permutation Graphs, Generalized Petersen Graphs and Torus Cordalis. arXiv:1112.1313 (2011)
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)
Chiang, C.-Y., Huang, L.-H., Li, B.-J., Wu, J., Yeh, H.-G.: Some results on the target set selection problem. Journal of Combinatorial Optimization (to appear)
Chiang, C.-Y., Huang, L.-H., Yeh, H.-G.: Target Set Selection Problem for Honeycomb Networks. SIAM J. Discrete Math. 27(1), 310–328 (2013)
Cicalese, F., Cordasco, G., Gargano, L., Milanič, M., Vaccaro, U.: Latency-Bounded Target Set Selection in Social Networks. In: Bonizzoni, P., Brattka, V., Löwe, B. (eds.) CiE 2013. LNCS, vol. 7921, pp. 65–77. Springer, Heidelberg (2013)
Comellas, F., Mitjana, M., Peters, J.G.: Broadcasting in Small-world Communication Networks. In: SIROCCO. Proceedings in Informatics, Carleton Scientific, vol. 13, pp. 73–85 (2002)
Daley, D.J., Kendall, D.G.: Epidemics and rumours. Nature 204, 1118 (1964)
Duenas-Osorio, L., Vemuru, S.M.: Cascading failures in complex infrastructure systems. Structural Safety 31(2), 157–167 (2009)
Domingos, P., Richardson, M.: Mining the network value of customers. In: Proc. of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 57–66 (2001)
Dodds, P.S., Watts, D.J.: A generalized model of social and biological contagion. J. Theoretical Biology 232, 587–604 (2005)
Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press (2010)
Flocchini, P., Královic, R., Ruzicka, P., Roncato, A., Santoro, N.: On time versus size for monotone dynamic monopolies in regular topologies. J. Discrete Algorithms 1, 129–150 (2003)
Karimi, F., Holme, P.: Threshold model of cascades in temporal networks. arXiv:1207.1206v2 [physics.soc-ph] (2012)
Kempe, D., Kleinberg, J.M., Tardos, E.: Maximizing the spread of influence through a social network. In: Proc. of the Ninth ACM SIGKDD International Conference on Knowledge, Discovery and Data Mining, pp. 137–146 (2003)
Kempe, D., Kleinberg, J.M., Tardos, É.: Influential Nodes in a Diffusion Model for Social Networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1127–1138. Springer, Heidelberg (2005)
Kephart, J.O., White, S.R., Chess, D.M.: Computers and epidemiology. IEEE Spectrum 30, 20–26 (1993)
Leskovic, H., Adamic, L.A., Huberman, B.A.: The dynamic of viral marketing. ACM Transactions on the WEB 1 (2007)
Leppaniemi, M., Karjaluoto, H., Lehto, H., Goman, A.: Targeting Young Voters in a Political Campaign: Empirical Insights into an Interactive Digital Marketing Campaign in the 2007 Finnish General Election. Journal of Nonprofit & Public Sector Marketing 22, 14–37 (2010)
Lopez-Pintado, D.: Diffusion in complex social networks. Games and Economic Behavior 62, 573–590 (2008)
Maki, D.P., Thompson, M.: Mathematical Models and Applications, with Emphasis on the Social, Life and Management Sciences. Prentice Hall (1973)
Nekovee, M., Moreno, Y., Bianconi, G., Marsili, M.: Theory of rumour spreading in complex social networks. Physica A: Statistical Mechanics and its Applications 374, 467–470 (2007)
Nichterlein, A., Niedermeier, R., Uhlmann, J., Weller, M.: On Tractable Cases of Target Set Selection. Social Network Analysis and Mining, 1–24 (2012)
Peleg, D.: Local majorities, coalitions and monopolies in graphs: a review. Theoretical Computer Science 282, 231–257 (2002)
Reddy, T.V.T., Rangan, C.P.: Variants of spreading messages. J. Graph Algorithms Appl. 15(5), 683–699 (2011)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer (2004)
Tumulty, K.: Obama’s Viral Marketing Campaign. TIME Magazine (July 5, 2007)
Ugander, J., Backstrom, L., Marlow, C., Kleinberg, J.: Structural Diversity in Social Contagion. Proc. of the Nat’l Academy of Sciences (PNAS) 109, 5962–5966 (2012)
Zaker, M.: On dynamic monopolies of graphs with general thresholds. Discrete Mathematics 312(6), 1136–1143 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gargano, L., Hell, P., Peters, J., Vaccaro, U. (2013). Influence Diffusion in Social Networks under Time Window Constraints. In: Moscibroda, T., Rescigno, A.A. (eds) Structural Information and Communication Complexity. SIROCCO 2013. Lecture Notes in Computer Science, vol 8179. Springer, Cham. https://doi.org/10.1007/978-3-319-03578-9_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-03578-9_12
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03577-2
Online ISBN: 978-3-319-03578-9
eBook Packages: Computer ScienceComputer Science (R0)