{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:12:24Z","timestamp":1760173944455,"version":"build-2065373602"},"reference-count":45,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T00:00:00Z","timestamp":1580256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>It is well-documented that social networks play a considerable role in information spreading. The dynamic processes governing the diffusion of information have been studied in many fields, including epidemiology, sociology, economics, and computer science. A widely studied problem in the area of viral marketing is the target set selection: in order to market a new product, hoping it will be adopted by a large fraction of individuals in the network, which set of individuals should we \u201ctarget\u201d (for instance, by offering them free samples of the product)? In this paper, we introduce a diffusion model in which some of the neighbors of a node have a negative influence on that node, namely, they induce the node to reject the feature that is supposed to be spread. We study the target set selection problem within this model, first proving a strong inapproximability result holding also when the diffusion process is required to reach all the nodes in a couple of rounds. Then, we consider a set of restrictions under which the problem is approximable to some extent.<\/jats:p>","DOI":"10.3390\/a13020032","type":"journal-article","created":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T10:51:07Z","timestamp":1580295067000},"page":"32","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Latency-Bounded Target Set Selection in Signed Networks"],"prefix":"10.3390","volume":"13","author":[{"given":"Miriam","family":"Di Ianni","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica, Universit\u00e0 degli Studi di Roma \u201cTor Vergata\u201d, 00133 Roma, RM, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6839-8551","authenticated-orcid":false,"given":"Giovanna","family":"Varricchio","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, 67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,1,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Domingos, P., and Richardson, M. (2001, January 26). Mining the Network Value of Customers. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA.","DOI":"10.1145\/502512.502525"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Richardson, M., and Domingos, P. (2002, January 23). Mining Knowledge-sharing Sites for Viral Marketing. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, AB, Canada.","DOI":"10.1145\/775047.775057"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.disopt.2010.09.007","article-title":"Treewidth governs the complexity of target set selection","volume":"8","author":"Hermelin","year":"2011","journal-title":"Discret. Optim."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Chen, W., Wang, C., and Wang, Y. (2010, January 25). Scalable Influence Maximization for Prevalent Viral Marketing in Large-scale Social Networks. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/1835804.1835934"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1420","DOI":"10.1086\/226707","article-title":"Threshold Models of Collective Behavior","volume":"6","author":"Granovetter","year":"1978","journal-title":"Am. J. Sociol."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., and Tardos, \u00c9. (2003, January 24). Maximizing the Spread of Influence Through a Social Network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/956750.956769"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1127","DOI":"10.1007\/11523468_91","article-title":"Influential Nodes in a Diffusion Model for Social Networks","volume":"Volume 3580","author":"Caires","year":"2005","journal-title":"Automata, Languages and Programming"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"5-es","DOI":"10.1145\/1232722.1232727","article-title":"The Dynamics of Viral Marketing","volume":"1","author":"Leskovec","year":"2007","journal-title":"ACM Trans. Web"},{"key":"ref_9","unstructured":"Contagion, M.S. (2000). The Review of Economic Studies, Oxford University Press."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"4017","DOI":"10.1016\/j.tcs.2010.08.021","article-title":"Combinatorial Model and Bounds for Target Set Selection","volume":"411","author":"Ackerman","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.jda.2014.05.001","article-title":"Parameterized approximability of maximizing the spread of influence in networks","volume":"27","author":"Bazgan","year":"2014","journal-title":"J. Discret. Algorithms"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3693","DOI":"10.1016\/j.tcs.2011.03.029","article-title":"Irreversible conversion of graphs","volume":"412","author":"Centeno","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1400","DOI":"10.1137\/08073617X","article-title":"On the approximability of influence in social networks","volume":"23","author":"Chen","year":"2009","journal-title":"SIAM J. Discret. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1007\/s10878-012-9518-3","article-title":"Some results on the target set selection problem","volume":"25","author":"Chiang","year":"2013","journal-title":"J. Comb. Optim."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/120868864","article-title":"Target Set Selection Problem for Honeycomb Networks","volume":"27","author":"Chiang","year":"2013","journal-title":"SIAM J. Discret. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s00224-013-9499-3","article-title":"Constant Thresholds Can Make Target Set Selection Tractable","volume":"55","author":"Chopin","year":"2014","journal-title":"Theor. Comput. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1016\/j.disc.2011.11.038","article-title":"On dynamic monopolies of graphs with general thresholds","volume":"312","author":"Zaker","year":"2012","journal-title":"Discret. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1016\/j.physa.2005.08.083","article-title":"The power of a good idea: Quantitative modeling of the spread of ideas from epidemiological models","volume":"364","author":"Bettencourt","year":"2006","journal-title":"Phys. Stat. Mech. Appl."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1016\/j.physa.2006.07.017","article-title":"Theory of rumour spreading in complex social networks","volume":"374","author":"Nekovee","year":"2007","journal-title":"Phys. Stat. Mech. Appl."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1023\/A:1011122126881","article-title":"Talk of the network: A complex systems look at the underlying process of word-of-mouth","volume":"12","author":"Goldenberg","year":"2001","journal-title":"Market. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1007\/BFb0057901","article-title":"Irreversible dynamos in tori","volume":"Volume 1470","author":"Pritchard","year":"1998","journal-title":"Euro-Par\u201998 Parallel Processing"},{"key":"ref_22","unstructured":"Luccio, F., Pagli, L., and Sanossian, H. (1999, January 1\u20133). Irreversible dynamos in butterflies. Proceedings of the 6th Colloquium on Structural Information and Communication Complexity, Lacanau-Ocean, France."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/S0166-218X(98)00043-2","article-title":"Size bounds for dynamic monopolies","volume":"86","author":"Peleg","year":"1998","journal-title":"Discret. Appl. Math."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.02.027","article-title":"Latency-Bounded Target Set Selection in Social Networks","volume":"535","author":"Cicalese","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1615","DOI":"10.1016\/j.dam.2008.09.012","article-title":"Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion","volume":"157","author":"Roberts","year":"2009","journal-title":"Discret. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2015.02.015","article-title":"Influence Diffusion in Social Networks under Time Window Constraints","volume":"584","author":"Gargano","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_27","unstructured":"Dreyer, P.A. (2000). Applications and Variations of Domination in Graphs. [Ph.D. Thesis, Rutgers University]."},{"key":"ref_28","unstructured":"Robertson, T.S., and Kassarjian, H. (1991). Memory and decision making. Handbook of Consumer Behavior, Prentice-Hall."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1287\/mksc.1090.0546","article-title":"Limited Memory, Categorization and Competition","volume":"29","author":"Chen","year":"2010","journal-title":"Market. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Chen, W., Collins, A., Cummings, R., Ke, T., Liu, Z., Rincon, D., Sun, X., Wang, Y., Wei, W., and Yuan, Y. (2011, January 28\u201330). Influence maximization in social networks when negative opinions may emerge and propagate. Proceedings of the 2011 SIAM International Conference on Data Mining, Mesa, AZ, USA.","DOI":"10.1137\/1.9781611972818.33"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Nazemian, A., and Taghiyareh, F. (2012, January 6\u20138). Influence maximization in independent cascade model with positive and negative word of mouth. Proceedings of the 6th International Symposium on Telecommunications (IST), Tehran, Iran.","DOI":"10.1109\/ISTEL.2012.6483105"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1080\/12460125.2014.886494","article-title":"Modelling the spread of negative word-of-mouth in online social networks","volume":"23","author":"Stich","year":"2014","journal-title":"J. Decis. Syst."},{"key":"ref_33","unstructured":"Yang, S., Wang, S., and Truong, V.A. (2019). Online Learning and Optimization Under a New Linear-Threshold Model with Negative Influence. arXiv."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Ahmed, S., and Ezeife, C.I. (2013, January 18). Discovering influential nodes from trust network. Proceedings of the 28th Annual ACM Symposium on Applied Computing, New York, NY, USA.","DOI":"10.1145\/2480362.2480389"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Li, Y., Chen, W., Wang, Y., and Zhang, Z.L. (2013, January 4). Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, Rome, Italy.","DOI":"10.1145\/2433396.2433478"},{"key":"ref_36","first-page":"43","article-title":"Networks, Crowds, and Markets: Reasoning about a Highly Connected World","volume":"9","author":"Easley","year":"2012","journal-title":"Significance"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Galhotra, S., Arora, A., and Roy, S. (2016, January 14). Holistic influence maximization: Combining scalability and efficiency with opinion-aware models. Proceedings of the 2016 International Conference on Management of Data, San Francisco, CA, USA.","DOI":"10.1145\/2882903.2882929"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"199","DOI":"10.3233\/IDA-150801","article-title":"Maximizing the spread of positive influence in signed social networks","volume":"20","author":"Zamanifar","year":"2016","journal-title":"Intell. Data Anal."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1037\/1089-2680.5.4.323","article-title":"Bad is stronger than good","volume":"5","author":"Baumeister","year":"2001","journal-title":"Rev. Gen. Psychol."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1080\/14792779108401856","article-title":"Positive-negative asymmetry in evaluations: The distinction between affective and informational negativity effects","volume":"1","author":"Peeters","year":"1990","journal-title":"Eur. Rev. Soc. Psychol."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1207\/S15327957PSPR0504_2","article-title":"Negativity bias, negativity dom- inance, and contagion","volume":"5","author":"Rozin","year":"2001","journal-title":"Personal. Soc. Psychol. Rev."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1037\/0033-2909.110.1.67","article-title":"Asymmetrical effects of positive and negative events: The mobilization-minimization hypothesis","volume":"110","author":"Taylor","year":"1991","journal-title":"Psychol. Bull."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Foerster, K.T. (2013, January 6). Approximating Fault-Tolerant Domination in General Graphs. Proceedings of the Tenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), New Orleans, LA, USA.","DOI":"10.1137\/1.9781611973037.4"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1863","DOI":"10.1137\/S0097539799349948","article-title":"The approximability of constraint satisfaction problems","volume":"30","author":"Khanna","year":"2000","journal-title":"SIAM J. Comput."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set covering problem","volume":"4","year":"1979","journal-title":"Math. Oper. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/32\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:53:00Z","timestamp":1760172780000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,29]]},"references-count":45,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["a13020032"],"URL":"https:\/\/doi.org\/10.3390\/a13020032","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,1,29]]}}}