×

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

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 behaviours/opinions on the basis of information collected from their neighbours 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 neighbours 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, and trees.

MSC:

91D30 Social networks; opinion dynamics
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ackerman, E.; Ben-Zwi, O.; Wolfovitz, G., Combinatorial model and bounds for target set selection, Theoret. Comput. Sci., 411, 4017-4022 (2010) · Zbl 1235.90168
[2] Alba, J.; Hutchinson, J. W.; Lynch, J., Memory and decision making, (Robertson, T. S.; Kassarjian, H., Handbook of Consumer Behavior (1991))
[3] Anderson, R. M.; May, R. M., Infectious Diseases of Humans: Dynamics and Control (1991), Oxford University Press
[4] Banos, R. A.; Borge-Holthoefer, J.; Moreno, Y., The role of hidden influentials in the diffusion of online information cascades (2013)
[5] Barrat, A.; Barthélemy, M.; Vespignani, A., Dynamical Processes on Complex Networks (2012), Cambridge University Press · Zbl 1253.90001
[6] Bazgan, C.; Chopin, M.; Nichterlein, A.; Sikora, F., Parameterized approximability of maximizing the spread of influence in networks, (Proceedings of Computing and Combinatorics. Proceedings of Computing and Combinatorics, COCOON 2013. Proceedings of Computing and Combinatorics. Proceedings of Computing and Combinatorics, COCOON 2013, Lectures Notes in Computer Science, vol. 7936 (2013)), 543-554 · Zbl 1382.68329
[7] Ben-Zwi, O.; Hermelin, D.; Lokshtanov, D.; Newman, I., Treewidth governs the complexity of target set selection, Discrete Optim., 8, 87-96 (2011) · Zbl 1248.90068
[8] 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, Phys. A, 364, 513-536 (2006)
[9] Bikhchandani, S.; Hirshleifer, D.; Welch, I., A theory of fads, customs, and cultural change as informational cascades, J. Polit. Econ., 100, 992-1026 (1992)
[10] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Complex networks: structure and dynamics, Phys. Rep., 472, 175-308 (2006) · Zbl 1371.82002
[11] Centeno, C. C.; Dourado, M. C.; Penso, L. D.; Rautenbach, D.; Szwarcfiter, J. L., Irreversible conversion of graphs, Theoret. Comput. Sci., 412, 3693-3700 (2011) · Zbl 1220.05109
[12] Centola, D.; Macy, M., Complex contagions and the weakness of long ties, Amer. J. Sociol., 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] Chen, J.; Iver, G.; Pazgal, A., Limited memory, categorization and competition, Mark. Sci., 29, July/August, 650-670 (2010)
[15] Chen, W.; Lakshmanan, L. V.S.; Castillo, C., Information and Influence Propagation in Social Networks (2013), Morgan & Claypool
[16] 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 (2011)
[17] Chopin, M.; Nichterlein, A.; Niedermeier, R.; Weller, M., Constant thresholds can make target set selection tractable, (Proceedings First Mediterranean Conference on Algorithms. Proceedings First Mediterranean Conference on Algorithms, MedAlg 2012. Proceedings First Mediterranean Conference on Algorithms. Proceedings First Mediterranean Conference on Algorithms, MedAlg 2012, LNCS, vol. 7659 (2012)), 120-133 · Zbl 1319.68108
[18] Chiang, C.-Y.; Huang, L.-H.; Li, B.-J.; Wu, J.; Yeh, H.-G., Some results on the target set selection problem, J. Comb. Optim., 25, 4, 702-715 (2013) · Zbl 1273.90224
[19] 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
[20] Cicalese, F.; Cordasco, G.; Gargano, L.; Milanič, M.; Vaccaro, U., Latency-bounded target set selection in social networks, (Bonizzoni, P.; Brattka, V.; Loewe, B., Proc. of Computability in Europe 2013. Proc. of Computability in Europe 2013, CiE 2013. Proc. of Computability in Europe 2013. Proc. of Computability in Europe 2013, CiE 2013, Lectures Notes in Computer Science, vol. 7921 (2013)), 65-77 · Zbl 1390.91262
[21] Comellas, F.; Mitjana, M.; Peters, J. G., Broadcasting in small-world communication networks, (SIROCCO. SIROCCO, Proceedings in Informatics, vol. 13 (2002), Carleton Scientific), 73-85
[22] Coja-Oghlan, A.; Feige, U.; Krivelevich, M.; Reichman, D., Contagious sets in expanders (2013) · Zbl 1375.05061
[23] Daley, D. J.; Kendall, D. G., Epidemics and rumours, Nature, 204, 1118 (1964)
[24] Duenas-Osorio, L.; Vemuru, S. M., Cascading failures in complex infrastructure systems, Struct. Saf., 31, 2, 157-167 (2009)
[25] Domingos, P.; Richardson, M., Mining the network value of customers, (Proc. of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2001)), 57-66
[26] Dodds, P. S.; Watts, D. J., A generalized model of social and biological contagion, J. Theoret. Biol., 232, 587-604 (2005) · Zbl 1442.92162
[27] Easley, D.; Kleinberg, J., Networks, Crowds, and Markets: Reasoning About a Highly Connected World (2010), Cambridge University Press · Zbl 1205.91007
[28] 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
[29] Karimi, F.; Holme, P., Threshold model of cascades in temporal networks (2012)
[30] Kempe, D.; Kleinberg, J. M.; Tardos, E., Maximizing the spread of influence through a social network, (Proc. of the Ninth ACM SIGKDD International Conference on Knowledge, Discovery and Data Mining (2003)), 137-146
[31] Kempe, D.; Kleinberg, J. M.; Tardos, E., Influential nodes in a diffusion model for social networks, (Proc. of the 32nd International Conference on Automata, Languages and Programming. Proc. of the 32nd International Conference on Automata, Languages and Programming, ICALP’05. Proc. of the 32nd International Conference on Automata, Languages and Programming. Proc. of the 32nd International Conference on Automata, Languages and Programming, ICALP’05, LNCS, vol. 3580 (2005)), 1127-1138 · Zbl 1084.91053
[32] Leskovic, H.; Adamic, L. A.; Huberman, B. A., The dynamic of viral marketing, ACM Trans. Web, 1 (2007)
[33] 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, J. Nonprofit Public Sect. Mark., 22, 14-37 (2010)
[34] Maki, D. P.; Thompson, M., Mathematical Models and Applications, with Emphasis on the Social, Life and Management Sciences (1973), Prentice Hall
[35] Nekovee, M.; Moreno, Y.; Bianconi, G.; Marsili, M., Theory of rumour spreading in complex social networks, Phys. A, 374, 467-470 (2007)
[36] Peleg, D., Local majorities, coalitions and monopolies in graphs: a review, Theoret. Comput. Sci., 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] Rival, J.-B.; Walach, J., The use of viral marketing in politics: a case study of the 2007 French presidential election (2009), Jönköping University, Jönköping International Business School, permanent link:
[39] Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency (2004), Springer · Zbl 1072.90030
[40] Tumulty, K., Obama’s viral marketing campaign, TIME Mag. (2007), July 5
[41] Ugander, J.; Backstrom, L.; Marlow, C.; Kleinberg, J., Structural diversity in social contagion, Proc. Nat. Acad. Sci., 109, 5962-5966 (2012)
[42] Zaker, M., On dynamic monopolies of graphs with general thresholds, Discrete Math., 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.