{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:08Z","timestamp":1775638448467,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2017,6,13]]},"abstract":"<jats:p>\n            Estimating cascade size and nodes' influence is a fundamental task in social, technological, and biological networks. Yet this task is extremely challenging due to the sheer size and the structural heterogeneity of networks. We investigate a new influence measure, termed\n            <jats:italic>outward influence<\/jats:italic>\n            (OI), defined as the (expected) number of nodes that a subset of nodes\n            <jats:italic>S<\/jats:italic>\n            will activate,\n            <jats:italic>excluding the nodes in S<\/jats:italic>\n            . Thus, OI equals, the de facto standard measure,\n            <jats:italic>influence spread<\/jats:italic>\n            of\n            <jats:italic>S<\/jats:italic>\n            minus |\n            <jats:italic>S<\/jats:italic>\n            |. OI is not only more informative for nodes with small influence, but also, critical in designing new effective sampling and statistical estimation methods.\n          <\/jats:p>\n          <jats:p>\n            Based on OI, we propose SIEA\/SOIEA, novel methods to estimate influence spread\/outward influence\n            <jats:italic>at scale and with rigorous theoretical guarantees<\/jats:italic>\n            . The proposed methods are built on two novel components 1) IICP an important sampling method for outward influence; and 2) RSA, a robust mean estimation method that minimize the number of samples through analyzing variance and range of random variables. Compared to the state-of-the art for influence estimation, SIEA is \u03a9(log\n            <jats:sup>\n              4\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ) times faster in theory and up to\n            <jats:italic>several orders of magnitude faster<\/jats:italic>\n            in practice. For the first time, influence of nodes in the networks of billions of edges can be estimated with high accuracy within a few minutes. Our comprehensive experiments on real-world networks also give evidence against the popular practice of using a fixed number, e.g. 10K or 20K, of samples to compute the \"ground truth\" for influence spread.\n          <\/jats:p>","DOI":"10.1145\/3084457","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Outward Influence and Cascade Size Estimation in Billion-scale Networks"],"prefix":"10.1145","volume":"1","author":[{"given":"Hung T.","family":"Nguyen","sequence":"first","affiliation":[{"name":"Virginia Commonwealth University, Richmond, VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tri P.","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Virginia Commonwealth University, Richmond, VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tam N.","family":"Vu","sequence":"additional","affiliation":[{"name":"University of Colorado Boulder &amp; UC Denver, Boulder, VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thang N.","family":"Dinh","sequence":"additional","affiliation":[{"name":"Virginia Commonwealth University, Richmond, VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.46"},{"key":"e_1_2_1_2_1","volume-title":"Gtgraph: A synthetic graph generator suite.","author":"Bader D. A.","year":"2006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"C. Borgs M. Brautbar J. Chayes and B. Lucier. 2014. Maximizing Social Influence in Nearly Optimal Time. In SODA. SIAM 946--957.   C. Borgs M. Brautbar J. Chayes and B. Lucier. 2014. Maximizing Social Influence in Nearly Optimal Time. In SODA. SIAM 946--957.","DOI":"10.1137\/1.9781611973402.70"},{"key":"e_1_2_1_4_1","volume-title":"A clustering approach for data and structural anonymity in social networks. PinKDD","author":"Campan A.","year":"2008"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526806"},{"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":"crossref","unstructured":"F. Chung and L. Lu. 2006. Concentration inequalities and martingale inequalities: a survey. Internet Mathematics (2006) 79--127.  F. Chung and L. Lu. 2006. Concentration inequalities and martingale inequalities: a survey. Internet Mathematics (2006) 79--127.","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662077"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797315306"},{"key":"e_1_2_1_10_1","unstructured":"D. J. Daley J. Gani and J. M. Gani. 2001. Epidemic modelling: an introduction. Vol. 15. Cambridge University Press.  D. J. Daley J. Gani and J. M. Gani. 2001. Epidemic modelling: an introduction. Vol. 15. Cambridge University Press."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"T. N. Dinh and M. T. Thai. 2015. Assessing attack vulnerability in networks with uncertainty. In INFOCOM. IEEE 2380--2388.  T. N. Dinh and M. T. Thai. 2015. Assessing attack vulnerability in networks with uncertainty. In INFOCOM. IEEE 2380--2388.","DOI":"10.1109\/INFOCOM.2015.7218626"},{"key":"e_1_2_1_12_1","unstructured":"N. Du L. Song M. Gomez-Rodriguez and H. Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. In NIPS. 3147--3155.   N. Du L. Song M. Gomez-Rodriguez and H. Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. In NIPS. 3147--3155."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718518"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488433"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038037.1941590"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Y. M. Ioannides and L. L. Datcher. 2004. Job information networks neighborhood effects and inequality. Journal of economic literature (2004) 1056--1093.  Y. M. Ioannides and L. L. Datcher. 2004. Job information networks neighborhood effects and inequality. Journal of economic literature (2004) 1056--1093.","DOI":"10.1257\/0022051043004595"},{"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","unstructured":"A. Krause A. Singh and C. Guestrin. 2008. Near-optimal sensor placements in Gaussian processes: Theory efficient algorithms and empirical studies. JMLR (2008) 235--284.   A. Krause A. Singh and C. Guestrin. 2008. Near-optimal sensor placements in Gaussian processes: Theory efficient algorithms and empirical studies. JMLR (2008) 235--284."},{"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\/1830252.1830263"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783334"},{"key":"e_1_2_1_24_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_25_1","doi-asserted-by":"crossref","unstructured":"D. T. Nguyen Z. Huiyuan S. Das M. T. Thai and T. N. Dinh. 2013. Least Cost Influence in Multiplex Social Networks: Model Representation and Analysis. In ICDM. 567--576.  D. T. Nguyen Z. Huiyuan S. Das M. T. Thai and T. N. Dinh. 2013. Least Cost Influence in Multiplex Social Networks: Model Representation and Analysis. In ICDM. 567--576.","DOI":"10.1109\/ICDM.2013.24"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983817"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"H. T. Nguyen M. T. Thai and T. N. Dinh. 2016. Cost-aware targeted viral marketing in billion-scale networks. In INFOCOM. IEEE 1--9.  H. T. Nguyen M. T. Thai and T. N. Dinh. 2016. Cost-aware targeted viral marketing in billion-scale networks. In INFOCOM. IEEE 1--9.","DOI":"10.1109\/INFOCOM.2016.7524377"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915207"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994525"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"V. M. Preciado M. Zargham C. Enyioha A. Jadbabaie and G. Pappas. 2013. Optimal vaccine allocation to control epidemic outbreaks in arbitrary networks. In CDC. IEEE 7486--7491.  V. M. Preciado M. Zargham C. Enyioha A. Jadbabaie and G. Pappas. 2013. Optimal vaccine allocation to control epidemic outbreaks in arbitrary networks. In CDC. IEEE 7486--7491.","DOI":"10.1109\/CDC.2013.6761078"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084457","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084457","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:22Z","timestamp":1750217422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,6,13]]}},"alternative-id":["10.1145\/3084457"],"URL":"https:\/\/doi.org\/10.1145\/3084457","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,13]]},"assertion":[{"value":"2017-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}