{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T02:49:48Z","timestamp":1777690188938,"version":"3.51.4"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,2]],"date-time":"2019-04-02T00:00:00Z","timestamp":1554163200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1452915,1535912"],"award-info":[{"award-number":["1452915,1535912"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds, formally referred to as the\n            <jats:italic>influence maximization problem<\/jats:italic>\n            . It admits a (1\u22121\/e)-factor approximation algorithm if the influence function is\n            <jats:italic>submodular<\/jats:italic>\n            . Otherwise, in the worst case, the problem is NP-hard to approximate to within a factor of\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>1\u2212\u03b5<\/jats:sup>\n            . This article studies whether this worst-case hardness result can be circumvented by making assumptions about either the underlying network topology or the cascade model. All our assumptions are motivated by many real-life social network cascades.\n          <\/jats:p>\n          <jats:p>\n            First, we present strong inapproximability results for a very restricted class of networks called the\n            <jats:italic>(stochastic) hierarchical blockmodel<\/jats:italic>\n            , a special case of the well-studied\n            <jats:italic>(stochastic) blockmodel<\/jats:italic>\n            in which relationships between blocks admit a tree structure. We also provide a dynamic-programming-based polynomial time algorithm, which optimally computes a directed variant of the influence maximization problem on hierarchical blockmodel networks. Our algorithm indicates that the inapproximability result is due to the bidirectionality of influence between agent-blocks.\n          <\/jats:p>\n          <jats:p>\n            Second, we present strong inapproximability results for a class of influence functions that are \u201calmost\u201d submodular, called\n            <jats:italic>2-quasi-submodular<\/jats:italic>\n            . Our inapproximability results hold even for any 2-quasi-submodular\n            <jats:italic>f<\/jats:italic>\n            fixed in advance. This result also indicates that the \u201cthreshold\u201d between submodularity and nonsubmodularity is sharp, regarding the approximability of influence maximization.\n          <\/jats:p>","DOI":"10.1145\/3313904","type":"journal-article","created":{"date-parts":[[2019,4,4]],"date-time":"2019-04-04T18:38:37Z","timestamp":1554403117000},"page":"1-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization"],"prefix":"10.1145","volume":"11","author":[{"given":"Grant","family":"Schoenebeck","sequence":"first","affiliation":[{"name":"The University of Michigan, Ann Arbor, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Biaoshuai","family":"Tao","sequence":"additional","affiliation":[{"name":"The University of Michigan, Ann Arbor, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the WINE. Springer, 16--29","author":"Angell Rico","year":"2017"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/2234208"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Abhijit Banerjee Arun G Chandrasekhar Esther Duflo and Matthew O Jackson. 2013. The diffusion of microfinance. Science 341 6144 (2013).  Abhijit Banerjee Arun G Chandrasekhar Esther Duflo and Matthew O Jackson. 2013. The diffusion of microfinance. Science 341 6144 (2013).","DOI":"10.1126\/science.1236498"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.15.5.215"},{"key":"e_1_2_1_6_1","volume-title":"In Proceedings of the WINE. Springer","author":"Bharathi Shishir","year":"2007"},{"key":"e_1_2_1_7_1","unstructured":"Christian Borgs Michael Brautbar Jennifer T. Chayes and Brendan Lucier. 2012. Influence maximization in social networks: Towards an optimal algorithmic solution. arXiv preprint arXiv:1212.0884 (2012).  Christian Borgs Michael Brautbar Jennifer T. Chayes and Brendan Lucier. 2012. Influence maximization in social networks: Towards an optimal algorithmic solution. arXiv preprint arXiv:1212.0884 (2012)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1086\/209118"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"D. Centola. 2010. The spread of behavior in an online social network experiment. Science 329 5996 (2010) 1194--1197.  D. Centola. 2010. The spread of behavior in an online social network experiment. Science 329 5996 (2010) 1194--1197.","DOI":"10.1126\/science.1185231"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/08073617X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939745"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Aaron Clauset Cristopher Moore and Mark EJ Newman. 2008. Hierarchical structure and the prediction of missing links in networks. Nature 453 7191 (2008) 98--101.  Aaron Clauset Cristopher Moore and Mark EJ Newman. 2008. Hierarchical structure and the prediction of missing links in networks. Nature 453 7191 (2008) 98--101.","DOI":"10.1038\/nature06830"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/2785979"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.100.1.35"},{"key":"e_1_2_1_17_1","first-page":"335","article-title":"Structural analysis of organizational fields: A blockmodel approach","volume":"8","author":"DiMaggio Paul","year":"1986","journal-title":"Res. Organiz. Behav."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata","volume":"9","author":"Goldenberg J.","year":"2001","journal-title":"Acad. Market. Sci. Rev."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214046"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1086\/226707"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939760"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Matthew O. Jackson. 2008. Social and Economic Networks. Princeton University Press.   Matthew O. Jackson. 2008. Social and Economic Networks. Princeton University Press.","DOI":"10.1515\/9781400833993"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_91"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the ICWSM. 90--97","author":"Lerman K."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134732"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the NIPS. 3804--3814","author":"Li Qiang","year":"2017"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783334"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2016.2634322"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1177\/002224299005400101"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00121"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958037"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963503"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.56"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the NIPS.","author":"Singer Yaron","year":"2016"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.082090499"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1086\/226141"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313904","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313904","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:46Z","timestamp":1750202626000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,2]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3313904"],"URL":"https:\/\/doi.org\/10.1145\/3313904","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,2]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}