{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T14:43:38Z","timestamp":1781621018386,"version":"3.54.5"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,8]]},"abstract":"<jats:p>\n            We propose the first real-time fully-dynamic index data structure designed for influence analysis on evolving networks. With this aim, we carefully redesign the data structure of the state-of-the-art sketching method introduced by Borgs\n            <jats:italic>et al.<\/jats:italic>\n            , and construct corresponding update algorithms. Using this index, we present algorithms for two kinds of queries,\n            <jats:italic>influence estimation<\/jats:italic>\n            and\n            <jats:italic>influence maximization<\/jats:italic>\n            , which are strongly motivated by practical applications, such as viral marketing. We provide a thorough theoretical analysis, which guarantees the non-degeneracy of the solution accuracy after an arbitrary number of updates. Furthermore, we introduce a\n            <jats:italic>reachability-tree-based technique<\/jats:italic>\n            and a\n            <jats:italic>skipping method<\/jats:italic>\n            , which greatly reduce the time consumption required for edge\/vertex deletions and vertex additions, respectively, and\n            <jats:italic>counter-based random number generators<\/jats:italic>\n            , which improve the space efficiency.\n          <\/jats:p>\n          <jats:p>Experimental evaluations using real dynamic networks with tens of millions of edges demonstrate the efficiency, scalability, and accuracy of our proposed indexing scheme. Specifically, it can reflect a graph modification within a time of several orders of magnitude smaller than that required to reconstruct an index from scratch, estimate the influence spread of a vertex set accurately within a millisecond, and select highly influential vertices at least ten times faster than state-of-the-art static algorithms.<\/jats:p>","DOI":"10.14778\/2994509.2994525","type":"journal-article","created":{"date-parts":[[2016,9,6]],"date-time":"2016-09-06T15:27:03Z","timestamp":1473175623000},"page":"1077-1088","source":"Crossref","is-referenced-by-count":67,"title":["Dynamic influence analysis in evolving networks"],"prefix":"10.14778","volume":"9","author":[{"given":"Naoto","family":"Ohsaka","sequence":"first","affiliation":[{"name":"The University of Tokyo and JST, ERATO, Kawarabayashi Large Graph Project"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Takuya","family":"Akiba","sequence":"additional","affiliation":[{"name":"National Institute of Informatics and JST, PRESTO and JST, ERATO, Kawarabayashi Large Graph Project"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[{"name":"National Institute of Informatics and Preferred Infrastructure, Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ken-ichi","family":"Kawarabayashi","sequence":"additional","affiliation":[{"name":"National Institute of Informatics and JST, ERATO, Kawarabayashi Large Graph Project"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2005.151"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401897"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634144"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.69"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2567997"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505541"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_10_1","first-page":"3147","volume-title":"NIPS","author":"Du N.","year":"2013","unstructured":"N. Du , L. Song , M. Gomez-Rodriguez , and H. Zha . Scalable influence estimation in continuous-time diffusion networks . In NIPS , pages 3147 -- 3155 , 2013 . N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable influence estimation in continuous-time diffusion networks. In NIPS, pages 3147--3155, 2013."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011122126881"},{"issue":"3","key":"e_1_2_1_12_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","unstructured":"J. Goldenberg , B. Libai , and E. Muller . Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata . Academy of Marketing Science Review , 9 ( 3 ): 1 -- 18 , 2001 . J. Goldenberg, B. Libai, and E. Muller. Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata. Academy of Marketing Science Review, 9(3):1--18, 2001.","journal-title":"Academy of Marketing Science Review"},{"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.1109\/ICDM.2012.79"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_16_1","first-page":"1371","volume-title":"AAAI","author":"Kimura M.","year":"2007","unstructured":"M. Kimura , K. Saito , and R. Nakano . Extracting influential nodes for information diffusion on a social network . In AAAI , pages 1371 -- 1376 , 2007 . M. Kimura, K. Saito, and R. Nakano. Extracting influential nodes for information diffusion on a social network. In AAAI, pages 1371--1376, 2007."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6515-8_13"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783334"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0006528"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339540"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2893873.2893897"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85567-5_9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063405"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835935"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.145"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2994509.2994525","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:53:27Z","timestamp":1672224807000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2994509.2994525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8]]},"references-count":31,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["10.14778\/2994509.2994525"],"URL":"https:\/\/doi.org\/10.14778\/2994509.2994525","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,8]]}}}