×

Influence diffusion in social networks under time window constraints. (English) Zbl 1408.91176

Moscibroda, Thomas (ed.) et al., Structural information and communication complexity. 20th international colloquium, SIROCCO 2013, Ischia, Italy, July 1–3, 2013. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 8179, 141-152 (2013).
Summary: 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 \in V\), and a time window size \(\lambda \). 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 \(\lambda \) 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.
For the entire collection see [Zbl 1277.68017].

MSC:

91D30 Social networks; opinion dynamics
91-04 Software, source code, etc. for problems pertaining to game theory, economics, and finance
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ackerman, E., Ben-Zwi, O., Wolfovitz, G.: Combinatorial model and bounds for target set selection. Theoretical Computer Science 411, 4017–4022 (2010) · Zbl 1235.90168
[2] Anderson, R.M., May, R.M.: Infectious Diseases of Humans: Dynamics and Control. Oxford University Press (1991)
[3] 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)
[4] Barrat, A., Barthelemy, M., Vespignani, A.: Dynamical Processes on Complex Networks. Cambridge University Press (2012) · Zbl 1253.90001
[5] Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized Approximability of Maximizing the Spread of Influence in Networks. arXiv:1303.6907 [cs.DS] · Zbl 1361.68105
[6] Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: Treewidth governs the complexity of target set selection. Discrete Optimization 8, 87–96 (2011) · Zbl 1248.90068
[7] 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)
[8] 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)
[9] Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.-U.: Complex Networks: Structure and Dynamics. Physics Reports 472, 175–308 (2006) · Zbl 1371.82002
[10] 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) · Zbl 1220.05109
[11] Centola, D.: The spread of behavior in an online social network experiment. Science 329, 1194–1197 (2010)
[12] Centola, D., Macy, M.: Complex contagions and the weakness of long ties. American Journal of Sociology 113, 702–734 (2007)
[13] Chen, N.: On the approximability of influence in social networks. SIAM J. Discrete Math. 23, 1400–1415 (2009) · Zbl 1203.68314
[14] 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)
[15] 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) · Zbl 1319.68108
[16] 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) · Zbl 1273.90224
[17] 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) · Zbl 1272.68063
[18] 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) · Zbl 1390.91262
[19] 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)
[20] Daley, D.J., Kendall, D.G.: Epidemics and rumours. Nature 204, 1118 (1964)
[21] Duenas-Osorio, L., Vemuru, S.M.: Cascading failures in complex infrastructure systems. Structural Safety 31(2), 157–167 (2009)
[22] 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)
[23] Dodds, P.S., Watts, D.J.: A generalized model of social and biological contagion. J. Theoretical Biology 232, 587–604 (2005)
[24] Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press (2010) · Zbl 1205.91007
[25] 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) · Zbl 1074.68045
[26] Karimi, F., Holme, P.: Threshold model of cascades in temporal networks. arXiv:1207.1206v2 [physics.soc-ph] (2012)
[27] 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) · Zbl 1337.91069
[28] 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) · Zbl 1084.91053
[29] Kephart, J.O., White, S.R., Chess, D.M.: Computers and epidemiology. IEEE Spectrum 30, 20–26 (1993)
[30] Leskovic, H., Adamic, L.A., Huberman, B.A.: The dynamic of viral marketing. ACM Transactions on the WEB 1 (2007) · Zbl 05463436
[31] 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)
[32] Lopez-Pintado, D.: Diffusion in complex social networks. Games and Economic Behavior 62, 573–590 (2008) · Zbl 1137.91606
[33] Maki, D.P., Thompson, M.: Mathematical Models and Applications, with Emphasis on the Social, Life and Management Sciences. Prentice Hall (1973)
[34] 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)
[35] Nichterlein, A., Niedermeier, R., Uhlmann, J., Weller, M.: On Tractable Cases of Target Set Selection. Social Network Analysis and Mining, 1–24 (2012)
[36] Peleg, D.: Local majorities, coalitions and monopolies in graphs: a review. Theoretical Computer Science 282, 231–257 (2002) · Zbl 0997.68088
[37] Reddy, T.V.T., Rangan, C.P.: Variants of spreading messages. J. Graph Algorithms Appl. 15(5), 683–699 (2011) · Zbl 1276.05119
[38] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer (2004) · Zbl 1072.90030
[39] Tumulty, K.: Obama’s Viral Marketing Campaign. TIME Magazine (July 5, 2007)
[40] 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)
[41] Zaker, M.: On dynamic monopolies of graphs with general thresholds. Discrete Mathematics 312(6), 1136–1143 (2012) · Zbl 1238.05262
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.