{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:06:01Z","timestamp":1761599161131,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,8,21]],"date-time":"2017-08-21T00:00:00Z","timestamp":1503273600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"International Conference on Computational Social Networks"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>\n            Given a social network, the Influence Maximization (InfMax) problem seeks a seed set of\n            <jats:italic>k<\/jats:italic>\n            people that maximizes the expected influence for a viral marketing campaign. However, a solution for a particular seed size\n            <jats:italic>k<\/jats:italic>\n            is often not enough to make an informed choice regarding budget and cost-effectiveness.\n          <\/jats:p>\n          <jats:p>\n            In this article, we propose the computation of\n            <jats:italic>Influence Spectrum<\/jats:italic>\n            (InfSpec), the maximum influence at\n            <jats:bold>each<\/jats:bold>\n            possible seed set size\n            <jats:italic>k<\/jats:italic>\n            within a given range [\n            <jats:italic>k<\/jats:italic>\n            <jats:sub>lower<\/jats:sub>\n            ,\n            <jats:italic>k<\/jats:italic>\n            <jats:sub>upper<\/jats:sub>\n            ], thus providing optimal decision making for any availability of budget or influence requirements. As none of the existing methods for InfMax are efficient enough for the task in large networks, we propose LISA (sub-Linear Influence Spectrum Approximation), an efficient approximation algorithm for InfSpec (and also InfMax) with the best-known worst-case guarantees for billion-scale networks. LISA returns an (1-1\/e -\u03f5)-approximate influence spectrum with high probability (1-\u03b4), where \u03f5, \u03b4 are precision parameters provided by users. Using statistical decision theory, LISA has an asymptotic optimal running time (in addition to optimal approximation guarantee). In practice, LISA surpasses the state-of-the-art InfMax methods, taking less than 15 minutes to process a network of 41.7 million nodes and 1.5 billions edges.\n          <\/jats:p>","DOI":"10.1145\/3086700","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Social Influence Spectrum at Scale"],"prefix":"10.1145","volume":"36","author":[{"given":"Hung T.","family":"Nguyen","sequence":"first","affiliation":[{"name":"Virginia Commonwealth University, Richmond, Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Preetam","family":"Ghosh","sequence":"additional","affiliation":[{"name":"Virginia Commonwealth University, Richmond, Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael L.","family":"Mayo","sequence":"additional","affiliation":[{"name":"US Army Engineer Research and Development Center, Halls Ferry Road, Mississippi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thang N.","family":"Dinh","sequence":"additional","affiliation":[{"name":"Virginia Commonwealth University, Richmond, Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,8,21]]},"reference":[{"volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Borgs C.","key":"e_1_2_1_1_1","unstructured":"C. Borgs , M. Brautbar , J. Chayes , and B. Lucier . 2014. Maximizing social influence in nearly optimal time . In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914) . SIAM, 946--957 C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. 2014. Maximizing social influence in nearly optimal time. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914). SIAM, 946--957"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526806"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/08073617X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00527ED1V01Y201308DTM037"},{"volume-title":"Proceedings of the 26th AAAI Conference on Artificial Intelligence.","author":"Chen W.","key":"e_1_2_1_5_1","unstructured":"W. Chen , W. Lu , and N. Zhang . 2012. Time-critical influence maximization in social networks with time-delayed diffusion process . In Proceedings of the 26th AAAI Conference on Artificial Intelligence. W. Chen, W. Lu, and N. Zhang. 2012. Time-critical influence maximization in social networks with time-delayed diffusion process. In Proceedings of the 26th AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662077"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797315306"},{"volume-title":"International Conference on Computational Social Networks. Springer, 84--103","author":"Dinh T.","key":"e_1_2_1_9_1","unstructured":"T. Dinh , H. Nguyen , P. Ghosh , and M. Mayo . 2015. Social influence spectrum with guarantees: Computing more in less time . In International Conference on Computational Social Networks. Springer, 84--103 . T. Dinh, H. Nguyen, P. Ghosh, and M. Mayo. 2015. Social influence spectrum with guarantees: Computing more in less time. In International Conference on Computational Social Networks. Springer, 84--103."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2290714"},{"key":"e_1_2_1_11_1","unstructured":"N. Du L. Song M. Gomez-Rodriguez and H. Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. In Advances in Neural Information Processing Systems. 3147--3155.   N. Du L. Song M. Gomez-Rodriguez and H. Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. In Advances in Neural Information Processing Systems. 3147--3155."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2824253"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718518"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963192.1963217"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.132"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_91"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487657"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433478"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871467"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.99"},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Control and Information Sciences","volume-title":"Accelerated greedy algorithms for maximizing submodular set functions","author":"Minoux M.","unstructured":"M. Minoux . 1978. Accelerated greedy algorithms for maximizing submodular set functions . In Optimization Techniques, J. Stoer (Ed.). Lecture Notes in Control and Information Sciences , Vol. 7 . Springer , 234--243. M. Minoux. 1978. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques, J. Stoer (Ed.). Lecture Notes in Control and Information Sciences, Vol. 7. Springer, 234--243."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E. Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.   M. Mitzenmacher and E. Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_28_1","first-page":"1550","volume-title":"Proceedings of the 2013 IEEE 13th International Conference on Data Mining (ICDM\u201913)","author":"Nguyen D. T.","unstructured":"D. T. Nguyen , Huiyuan Zhang , S. Das , M. T. Thai , and T. N. Dinh . 2013. Least cost influence in multiplex social networks: Model representation and analysis . In Proceedings of the 2013 IEEE 13th International Conference on Data Mining (ICDM\u201913) . 567--576. 1550 - 4786 D. T. Nguyen, Huiyuan Zhang, S. Das, M. T. Thai, and T. N. Dinh. 2013. Least cost influence in multiplex social networks: Model representation and analysis. In Proceedings of the 2013 IEEE 13th International Conference on Data Mining (ICDM\u201913). 567--576. 1550-4786"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915207"},{"volume-title":"Proceedings of the 28th International Conference of the Association for the Advancement of Artificial Intelligence (AAAI\u201914)","author":"Ohsaka N.","key":"e_1_2_1_30_1","unstructured":"N. Ohsaka , Y. Akiba , T. Yoshida , and K. Kawarabayashi . 2014. Fast and accurate influence maximization on large networks with pruned monte-carlo simulations . In Proceedings of the 28th International Conference of the Association for the Advancement of Artificial Intelligence (AAAI\u201914) . N. Ohsaka, Y. Akiba, T. Yoshida, and K. Kawarabayashi. 2014. Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In Proceedings of the 28th International Conference of the Association for the Advancement of Artificial Intelligence (AAAI\u201914)."},{"volume-title":"Proceedings of the 2012 International Conference on Machine Learning (ICML'12)","author":"Rodriguez M. G.","key":"e_1_2_1_31_1","unstructured":"M. G. Rodriguez and B. Sch\u00f6lkopf . 2012. Influence maximization in continuous time diffusion networks . In Proceedings of the 2012 International Conference on Machine Learning (ICML'12) . 313--320. M. G. Rodriguez and B. Sch\u00f6lkopf. 2012. Influence maximization in continuous time diffusion networks. In Proceedings of the 2012 International Conference on Machine Learning (ICML'12). 313--320."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85567-5_9"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398525"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557108"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"volume-title":"Approximation Algorithms","author":"Vazirani V. V.","key":"e_1_2_1_37_1","unstructured":"V. V. Vazirani . 2001. Approximation Algorithms . Springer . Retrieved from http:\/\/books.google.com\/books?id&equals;EILqAmzKgYIC. V. V. Vazirani. 2001. Approximation Algorithms. Springer. Retrieved from http:\/\/books.google.com\/books?id&equals;EILqAmzKgYIC."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2013.37"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2885494"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2717314"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3086700","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3086700","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:13Z","timestamp":1750217413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3086700"}},"subtitle":["Near-Optimal Solutions for Multiple Budgets at Once"],"short-title":[],"issued":{"date-parts":[[2017,8,21]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3086700"],"URL":"https:\/\/doi.org\/10.1145\/3086700","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2017,8,21]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}