{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:22:58Z","timestamp":1761805378847,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,10,26]],"date-time":"2017-10-26T00:00:00Z","timestamp":1508976000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s00453-017-0390-5","type":"journal-article","created":{"date-parts":[[2017,10,26]],"date-time":"2017-10-26T15:41:54Z","timestamp":1509032514000},"page":"1804-1833","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Discovering Small Target Sets in Social Networks: A Fast and Effective Algorithm"],"prefix":"10.1007","volume":"80","author":[{"given":"Gennaro","family":"Cordasco","sequence":"first","affiliation":[]},{"given":"Luisa","family":"Gargano","sequence":"additional","affiliation":[]},{"given":"Marco","family":"Mecchia","sequence":"additional","affiliation":[]},{"given":"Adele A.","family":"Rescigno","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4085-7300","authenticated-orcid":false,"given":"Ugo","family":"Vaccaro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,10,26]]},"reference":[{"issue":"44\u201346","key":"390_CR1","doi-asserted-by":"crossref","first-page":"4017","DOI":"10.1016\/j.tcs.2010.08.021","volume":"411","author":"E Ackerman","year":"2010","unstructured":"Ackerman, E., Ben-Zwi, O., Wolfovitz, G.: Combinatorial model and bounds for target set selection. Theor. Comput. Sci. 411(44\u201346), 4017\u20134022 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"390_CR2","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.jda.2014.05.001","volume":"27","author":"C Bazgan","year":"2014","unstructured":"Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized approximability of maximizing the spread of influence in networks. J. Discrete Algorithms 27, 54\u201365 (2014)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"390_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.disopt.2010.09.007","volume":"8","author":"O Ben-Zwi","year":"2011","unstructured":"Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: Treewidth governs the complexity of target set selection. Discrete Optim. 8(1), 87\u201396 (2011)","journal-title":"Discrete Optim."},{"key":"390_CR4","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1038\/nature11421","volume":"489","author":"RM Bond","year":"2012","unstructured":"Bond, R.M., Fariss, C.J., Jones, J.J., Kramer, A.D.I., Marlow, C., Settle, J.E., Fowler, J.H.: A 61-million-person experiment in social influence and political mobilization. Nature 489, 295\u2013298 (2012)","journal-title":"Nature"},{"issue":"29","key":"390_CR5","doi-asserted-by":"crossref","first-page":"3693","DOI":"10.1016\/j.tcs.2011.03.029","volume":"412","author":"CC Centeno","year":"2011","unstructured":"Centeno, C.C., Dourado, M.C., Penso, L.D., Rautenbach, D., Szwarcfiter, J.L.: Irreversible conversion of graphs. Theor. Comput. Sci. 412(29), 3693\u20133700 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"390_CR6","doi-asserted-by":"crossref","first-page":"1400","DOI":"10.1137\/08073617X","volume":"23","author":"N Chen","year":"2009","unstructured":"Chen, N.: On the approximability of influence in social networks. SIAM J. Discrete Math. 23(3), 1400\u20131415 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"390_CR7","doi-asserted-by":"crossref","unstructured":"Chen, W., Lakshmanan, L.V., Castillo, C.: Information and Influence Propagation in Social Networks. Morgan & Claypool, San Rafael (2013)","DOI":"10.2200\/S00527ED1V01Y201308DTM037"},{"issue":"4","key":"390_CR8","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1007\/s10878-012-9518-3","volume":"25","author":"C-Y Chiang","year":"2013","unstructured":"Chiang, C.-Y., Huang, L.-H., Li, B.-J., Jiaojiao, W., Yeh, H.-G.: Some results on the target set selection problem. J. Comb. Optim. 25(4), 702\u2013715 (2013)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"390_CR9","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/120868864","volume":"27","author":"C-Y Chiang","year":"2013","unstructured":"Chiang, C.-Y., Huang, L.-H., Yeh, H.-G.: Target set selection problem for honeycomb networks. SIAM J. Discrete Math. 27(1), 310\u2013328 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"390_CR10","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s00224-013-9499-3","volume":"55","author":"M Chopin","year":"2014","unstructured":"Chopin, M., Nichterlein, A., Niedermeier, R., Weller, M.: Constant thresholds can make target set selection tractable. Theory Comput. Syst. 55(1), 61\u201383 (2014)","journal-title":"Theory Comput. Syst."},{"key":"390_CR11","unstructured":"Christakis, N.A., Fowler, J.H.: Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives\u2014How Your Friends\u2019 Friends\u2019 Friends Affect Everything You Feel, Think, and Do. Back Bay Books (reprint edition) (2011)"},{"key":"390_CR12","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.tcs.2015.02.032","volume":"586","author":"F Cicalese","year":"2015","unstructured":"Cicalese, F., Cordasco, G., Gargano, L., Milani\u010d, M., Peters, J., Vaccaro, U.: Spread of influence in weighted networks under time and budget constraints. Theor. Comput. Sci. 586, 40\u201358 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"390_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.02.027","volume":"535","author":"F Cicalese","year":"2014","unstructured":"Cicalese, F., Cordasco, G., Gargano, L., Milani\u010d, M., Vaccaro, U.: Latency-bounded target set selection in social networks. Theor. Comput. Sci. 535, 1\u201315 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"390_CR14","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Feige, U., Krivelevich, M., Reichman, D.: Contagious sets in expanders. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1953\u20131987 (2015)","DOI":"10.1137\/1.9781611973730.131"},{"key":"390_CR15","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Mecchia, M., Rescigno, A.A., Vaccaro, U.: A fast and effective heuristic for discovering small target sets in social networks. In: Proceedings of International Conference on Combinatorial Optimization and Applications, COCOA 2015, vol. 9486, pp. 193\u2013208 (2015)","DOI":"10.1007\/978-3-319-26626-8_15"},{"key":"390_CR16","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Optimizing spread of influence in social networks via partial incentives. In: Structural Information and Communication Complexity: 22nd International Colloquium, SIROCCO 2015, pp. 119\u2013134 (2015)","DOI":"10.1007\/978-3-319-25258-2_9"},{"key":"390_CR17","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Brief announcement: active information spread in networks. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC, vol. 16, pp. 435\u2013437 (2016)","DOI":"10.1145\/2933057.2933069"},{"key":"390_CR18","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Evangelism in social networks. In: Proceedings of Combinatorial Algorithms\u201427th International Workshop, IWOCA 2016, pp. 96\u2013108 (2016)","DOI":"10.1007\/978-3-319-44543-4_8"},{"issue":"94","key":"390_CR19","first-page":"2016","volume":"6","author":"G Cordasco","year":"2016","unstructured":"Cordasco, G., Gargano, L., Rescigno, A.A.: On finding small sets that influence large networks. Soc. Netw. Anal. Min. SNAM 6(94), 2016 (2016)","journal-title":"Soc. Netw. Anal. Min. SNAM"},{"issue":"6","key":"390_CR20","doi-asserted-by":"crossref","first-page":"2001","DOI":"10.1109\/TNET.2013.2290714","volume":"22","author":"TN Dinh","year":"2014","unstructured":"Dinh, T.N., Zhang, H., Nguyen, D.T., Thai, M.T.: Cost-effective viral marketing for time-critical campaigns in large-scale social networks. IEEE\/ACM Trans. Netw. 22(6), 2001\u20132011 (2014)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"390_CR21","doi-asserted-by":"crossref","unstructured":"Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD\u201901, pp. 57\u201366 (2001)","DOI":"10.1145\/502512.502525"},{"key":"390_CR22","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511761942","volume-title":"Networks, Crowds, and Markets: Reasoning About a Highly Connected World","author":"D Easley","year":"2010","unstructured":"Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York (2010)"},{"issue":"1","key":"390_CR23","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/s13278-014-0214-4","volume":"4","author":"L Fan","year":"2014","unstructured":"Fan, L., Weili, W., Zhai, X., Xing, K., Lee, W., Ding-Zhu, D.: Maximizing rumor containment in social networks with constrained time. Soc. Netw. Anal. Min. 4(1), 214 (2014)","journal-title":"Soc. Netw. Anal. Min."},{"issue":"C","key":"390_CR24","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2015.02.015","volume":"584","author":"L Gargano","year":"2015","unstructured":"Gargano, L., Hell, P., Peters, J.G., Vaccaro, U.: Influence diffusion in social networks under time window constraints. Theor. Comput. Sci. 584(C), 53\u201366 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"390_CR25","doi-asserted-by":"crossref","first-page":"1420","DOI":"10.1086\/226707","volume":"83","author":"M Granovetter","year":"1978","unstructured":"Granovetter, M.: Threshold models of collective behavior. Am. J. Sociol. 83(6), 1420\u20131443 (1978)","journal-title":"Am. J. Sociol."},{"key":"390_CR26","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201903, pp. 137\u2013146, New York, NY, USA (2003)","DOI":"10.1145\/956750.956769"},{"key":"390_CR27","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Influential nodes in a diffusion model for social networks. In: Proceedings of the 32nd International Conference on Automata, Languages and Programming, ICALP\u201905, pp. 1127\u20131138, Berlin, Heidelberg (2005)","DOI":"10.1007\/11523468_91"},{"key":"390_CR28","volume-title":"An Army of Eyeballs: The Rise of the Advertisee","author":"D Lately","year":"2014","unstructured":"Lately, D.: An Army of Eyeballs: The Rise of the Advertisee. The Baffler, Chicago (2014)"},{"issue":"1","key":"390_CR29","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1080\/10495140903190374","volume":"22","author":"M Leppaniemi","year":"2010","unstructured":"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. Market. 22(1), 14\u201337 (2010)","journal-title":"J. Nonprofit Public Sect. Market."},{"key":"390_CR30","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection (2015). http:\/\/snap.stanford.edu\/data"},{"issue":"1","key":"390_CR31","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1232722.1232727","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec, J., Adamic, L.A., Huberman, B.A.: The dynamics of viral marketing. ACM Trans. Web 1(1), 5 (2007)","journal-title":"ACM Trans. Web"},{"key":"390_CR32","volume-title":"Encyclopedia of Algorithms","author":"Z Lu","year":"2014","unstructured":"Lu, Z., Wu, W.: Influence maximization. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms. Springer, Berlin (2014)"},{"issue":"23","key":"390_CR33","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","volume":"103","author":"EJ Mark","year":"2006","unstructured":"Mark, E.J.: Newman modularity and community structure in networks. Proc. Natl. Acad. Sci. USA (PNAS) 103(23), 8577\u20138582 (2006)","journal-title":"Proc. Natl. Acad. Sci. USA (PNAS)"},{"issue":"2","key":"390_CR34","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s13278-012-0067-7","volume":"3","author":"A Nichterlein","year":"2013","unstructured":"Nichterlein, A., Niedermeier, R., Uhlmann, J., Weller, M.: On tractable cases of target set selection. Soc. Netw. Anal. Min. 3(2), 233\u2013256 (2013)","journal-title":"Soc. Netw. Anal. Min."},{"issue":"5","key":"390_CR35","doi-asserted-by":"crossref","first-page":"683","DOI":"10.7155\/jgaa.00244","volume":"15","author":"TT Reddy","year":"2011","unstructured":"Reddy, T.T., Pandu Rangan, C.: Variants of spreading messages. J. Gr. Algorithms Appl. 15(5), 683\u2013699 (2011)","journal-title":"J. Gr. Algorithms Appl."},{"issue":"4","key":"390_CR36","doi-asserted-by":"crossref","first-page":"1225","DOI":"10.1007\/s13278-013-0135-7","volume":"3","author":"P Shakarian","year":"2013","unstructured":"Shakarian, P., Eyre, S., Paulo, D.: A scalable heuristic for viral marketing under the tipping model. Soc. Netw. Anal. Min. 3(4), 1225\u20131248 (2013)","journal-title":"Soc. Netw. Anal. Min."},{"volume-title":"Dynamics of Information Systems: Mathematical Foundations","year":"2012","key":"390_CR37","unstructured":"Sorokin, A., Murphey, R., Thai, M.T., Pardalos, P. (eds.): Dynamics of Information Systems: Mathematical Foundations. Springer, Berlin (2012)"},{"key":"390_CR38","volume-title":"Obama\u2019s Viral Marketing Campaign","author":"K Tumulty","year":"2007","unstructured":"Tumulty, K.: Obama\u2019s Viral Marketing Campaign. TIME Magazine, New York (2007)"},{"key":"390_CR39","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511815478","volume-title":"Social Network Analysis: Methods and Applications","author":"S Wasserman","year":"1994","unstructured":"Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge (1994)"},{"key":"390_CR40","unstructured":"Zafarani, R., Liu, H.: Social computing data repository at ASU (2009). http:\/\/socialcomputing.asu.edu"},{"issue":"6","key":"390_CR41","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1016\/j.disc.2011.11.038","volume":"312","author":"M Zaker","year":"2012","unstructured":"Zaker, M.: On dynamic monopolies of graphs with general thresholds. Discrete Math. 312(6), 1136\u20131143 (2012)","journal-title":"Discrete Math."},{"key":"390_CR42","volume-title":"Opportunistic Mobile Social Networks","author":"H Zhang","year":"2014","unstructured":"Zhang, H., Mishra, S., Thai, M.T.: Recent advances in information diffusion and influence maximization in complex social networks. In: Wu, J., Wang, Y. (eds.) Opportunistic Mobile Social Networks. CRC Press, Boca Raton (2014)"},{"issue":"1","key":"390_CR43","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10878-013-9635-7","volume":"30","author":"Y Zhu","year":"2015","unstructured":"Zhu, Y., Weili, W., Bi, Y., Lidong, W., Jiang, Y., Wen, X.: Better approximation algorithms for influence maximization in online social networks. J. Comb. Optim. 30(1), 97\u2013108 (2015)","journal-title":"J. Comb. Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0390-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0390-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0390-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T02:22:05Z","timestamp":1570242125000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0390-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,26]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["390"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0390-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,10,26]]}}}