{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T22:02:14Z","timestamp":1772143334540,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T00:00:00Z","timestamp":1622246400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T00:00:00Z","timestamp":1622246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"The National Key Research 849 & Development Program of China","award":["2018YFB1004002"],"award-info":[{"award-number":["2018YFB1004002"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61932004"],"award-info":[{"award-number":["61932004"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62072205"],"award-info":[{"award-number":["62072205"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Now, with the prevalence of social media, such as Facebook, Weibo, how to maximize influence of individuals, products, actions in new media is of practical significance. Generally, maximizing influence first needs to identify the most influential individuals since they can spread their influence to most of others in the social media. Many studies on influence maximization aimed to select a subset of nodes in static graphs once. Actually, real graphs are evolving. So, influential individuals are also changing. In these scenarios, people tend to select influential individuals multiple times instead of once. Namely, selections are raised sequentially, forming a sequence (query sequence). It raises several new challenges due to changing influential individuals. In this paper, we explore the problem of Influence Maximization over Streaming Graph (SGIM). Then, we design a compact solution for storing and indexing streaming graphs and influential nodes that eliminates the redundant computation. The solution includes Influence-Increment-Index along with two sketch-centralized indices called Influence-Index and Reverse-Influence-Index. Computing influence set of nodes will incur a large number of redundant computations. So, these indices are designed to keep track of the nodes\u2019 influence in sketches. Finally, with the indexing scheme, we present the algorithm to answer SGIM queries. Extensive experiments on several real-world datasets demonstrate that our method is competitive in terms of both efficiency and effectiveness owing to the design of index.<\/jats:p>","DOI":"10.1007\/s41019-021-00158-0","type":"journal-article","created":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T08:04:27Z","timestamp":1622275467000},"page":"339-357","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Maximizing Influence Over Streaming Graphs with Query Sequence"],"prefix":"10.1007","volume":"6","author":[{"given":"Yuying","family":"Zhao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunfei","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1656-5634","authenticated-orcid":false,"given":"Pingpeng","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,29]]},"reference":[{"key":"158_CR1","doi-asserted-by":"crossref","unstructured":"Budak C, Agrawal D, Abbadi AE (2011) Limiting the spread of misinformation in social networks. In: WWW, pp 665\u2013674","DOI":"10.1145\/1963405.1963499"},{"key":"158_CR2","doi-asserted-by":"crossref","unstructured":"He X, Song G, Chen W, Jiang Q (2012) Influence blocking maximization in social networks under the competitive linear threshold model. In: SDM, pp 463\u2013474","DOI":"10.1137\/1.9781611972825.40"},{"key":"158_CR3","doi-asserted-by":"crossref","unstructured":"Ye M, Liu X, Lee W (2012) Exploring social influence for recommendation: a generative model approach. In: SIGIR, pp 671\u2013680","DOI":"10.1145\/2348283.2348373"},{"issue":"2","key":"158_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/2503792.2503797","volume":"42","author":"A Guille","year":"2013","unstructured":"Guille A, Hacid H, Favre C, Zighed DA (2013) Information diffusion in online social networks: a survey. SIGMOD Rec 42(2):17\u201328","journal-title":"SIGMOD Rec"},{"key":"158_CR5","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9 (2003) Maximizing the spread of influence through a social network. In: KDD, pp 137\u2013146","DOI":"10.1145\/956750.956769"},{"key":"158_CR6","doi-asserted-by":"crossref","unstructured":"Domingos P, Richardson M (2001) Mining the network value of customers. In: KDD, pp 57\u201366","DOI":"10.1145\/502512.502525"},{"key":"158_CR7","doi-asserted-by":"crossref","unstructured":"Myers SA, Leskovec J (2014) The bursty dynamics of the twitter information network. In: WWW, pp 913\u2013924","DOI":"10.1145\/2566486.2568043"},{"issue":"2","key":"158_CR8","first-page":"359","volume":"29","author":"G Song","year":"2017","unstructured":"Song G, Li Y, Chen X, He X, Tang J (2017) Influential node tracking on dynamic social network: an interchange greedy approach. TKDE 29(2):359\u2013372","journal-title":"TKDE"},{"issue":"12","key":"158_CR9","first-page":"1077","volume":"9","author":"N Ohsaka","year":"2016","unstructured":"Ohsaka N, Akiba T, Yoshida Y, Kawarabayashi KI (2016) Dynamic influence analysis in evolving networks. VLDB 9(12):1077\u20131088","journal-title":"VLDB"},{"issue":"11","key":"158_CR10","first-page":"2615","volume":"29","author":"Y Yang","year":"2017","unstructured":"Yang Y, Wang Z, Pei J, Chen E (2017) Tracking influential individuals in dynamic networks. TKDE 29(11):2615\u20132628","journal-title":"TKDE"},{"key":"158_CR11","doi-asserted-by":"crossref","unstructured":"Zhao J, Shang S, Wang P, Lui JCS, Zhang X (2019) Tracking influential nodes in time-decaying dynamic interaction networks. In: ICDE, pp 1106\u20131117","DOI":"10.1109\/ICDE.2019.00102"},{"key":"158_CR12","doi-asserted-by":"crossref","unstructured":"Huang S, Bao Z, Culpepper JS, Zhang B (2019) Finding temporal influential users over evolving social networks. In: ICDE, pp 398\u2013409","DOI":"10.1109\/ICDE.2019.00043"},{"issue":"6","key":"158_CR13","doi-asserted-by":"publisher","first-page":"1794","DOI":"10.1137\/S0097539701398363","volume":"31","author":"M Datar","year":"2002","unstructured":"Datar M, Gionis A, Indyk P, Motwani R (2002) Maintaining stream statistics over sliding windows. SIAM J Comput 31(6):1794\u20131813","journal-title":"SIAM J Comput"},{"key":"158_CR14","doi-asserted-by":"crossref","unstructured":"Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen JM, Glance NS (2007) Cost-effective outbreak detection in networks. In: KDD, pp 420\u2013429","DOI":"10.1145\/1281192.1281239"},{"key":"158_CR15","doi-asserted-by":"crossref","unstructured":"Goyal A, Lu W, Lakshmanan LVS (2011) CELF++: optimizing the greedy algorithm for influence maximization in social networks. In: WWW, pp 47\u201348","DOI":"10.1145\/1963192.1963217"},{"key":"158_CR16","doi-asserted-by":"crossref","unstructured":"Wang Y, Cong G, Song G, Xie K (2010) Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In: KDD, pp 1039\u20131048","DOI":"10.1145\/1835804.1835935"},{"key":"158_CR17","doi-asserted-by":"crossref","unstructured":"Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: KDD, pp 199\u2013208","DOI":"10.1145\/1557019.1557047"},{"key":"158_CR18","doi-asserted-by":"crossref","unstructured":"Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: KDD, pp 1029\u20131038","DOI":"10.1145\/1835804.1835934"},{"key":"158_CR19","doi-asserted-by":"crossref","unstructured":"Cheng S, Shen H, Huang J, Zhang G, Cheng X (2013) Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In: CIKM, pp 509\u2013518","DOI":"10.1145\/2505515.2505541"},{"key":"158_CR20","doi-asserted-by":"crossref","unstructured":"Ohsaka N, Akiba T, Yoshida Y, Kawarabayashi K (2014) Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In: AAAI, pp 138\u2013144","DOI":"10.1609\/aaai.v28i1.8726"},{"key":"158_CR21","doi-asserted-by":"crossref","unstructured":"Cohen E, Delling D, Pajor T, Werneck RF (2014) Sketch-based influence maximization and computation: scaling up with guarantees. In: CIKM, pp 629\u2013638","DOI":"10.1145\/2661829.2662077"},{"key":"158_CR22","doi-asserted-by":"crossref","unstructured":"Borgs C, Brautbar M, Chayes JT, Lucier B (2014) Maximizing social influence in nearly optimal time. In: SODA, pp 946\u2013957","DOI":"10.1137\/1.9781611973402.70"},{"key":"158_CR23","doi-asserted-by":"crossref","unstructured":"Tang Y, Xiao X, Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: SIGMOD, pp 75\u201386","DOI":"10.1145\/2588555.2593670"},{"key":"158_CR24","doi-asserted-by":"crossref","unstructured":"Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach. In: SIGMOD, pp 1539\u20131554","DOI":"10.1145\/2723372.2723734"},{"issue":"9","key":"158_CR25","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.14778\/3213880.3213883","volume":"11","author":"K Han","year":"2018","unstructured":"Han K, Huang K, Xiao X, Tang J, Sun A, Tang X (2018) Efficient algorithms for adaptive influence maximization. Proc VLDB Endow 11(9):1029\u20131040","journal-title":"Proc VLDB Endow"},{"key":"158_CR26","first-page":"427","volume":"42","author":"D Golovin","year":"2011","unstructured":"Golovin D, Krause A (2011) Adaptive submodularity: theory and applications in active learning and stochastic optimization. J Artif Intell Res 42:427\u2013486","journal-title":"J Artif Intell Res"},{"key":"158_CR27","doi-asserted-by":"crossref","unstructured":"Yuan J, Tang S (2017) No time to observe: adaptive influence maximization with partial feedback. In: Proceedings of the 26th international joint conference on artificial intelligence, pp 3908\u20133914","DOI":"10.24963\/ijcai.2017\/546"},{"issue":"1","key":"158_CR28","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1109\/TNET.2016.2563397","volume":"25","author":"G Tong","year":"2016","unstructured":"Tong G, Wu W, Tang S, Du D-Z (2016) Adaptive influence maximization in dynamic social networks. IEEE\/ACM Trans Netw 25(1):112\u2013125","journal-title":"IEEE\/ACM Trans Netw"},{"key":"158_CR29","doi-asserted-by":"crossref","unstructured":"Huang K, Tang J, Han K, Xiao X, Chen W, Sun A, Tang X, Lim A (2020) Efficient approximation algorithms for adaptive influence maximization. VLDB J 29:1\u201322","DOI":"10.1007\/s00778-020-00615-8"},{"issue":"7","key":"158_CR30","doi-asserted-by":"publisher","first-page":"805","DOI":"10.14778\/3067421.3067429","volume":"10","author":"Y Wang","year":"2017","unstructured":"Wang Y, Fan Q, Li Y, Tan K (2017) Real-time influence maximization on dynamic social streams. Proc VLDB Endow 10(7):805\u2013816","journal-title":"Proc VLDB Endow"},{"key":"158_CR31","doi-asserted-by":"crossref","unstructured":"Aggarwal CC, Lin S, Yu PS (2012) On influential node discovery in dynamic social networks. In: SDM, pp 636\u2013647","DOI":"10.1137\/1.9781611972825.55"},{"key":"158_CR32","doi-asserted-by":"crossref","unstructured":"Zhuang H, Sun Y, Tang J, Zhang J, Sun X (2013) Influence maximization in dynamic social networks. In: ICDE, pp 1313\u20131318","DOI":"10.1109\/ICDM.2013.145"},{"issue":"10","key":"158_CR33","first-page":"1852","volume":"30","author":"Y Li","year":"2018","unstructured":"Li Y, Fan J, Wang Y, Tan K (2018) Influence maximization on social graphs: a survey. TKDE 30(10):1852\u20131872","journal-title":"TKDE"},{"key":"158_CR34","doi-asserted-by":"crossref","unstructured":"Paranjape A, Benson AR, Leskovec J (2017) Motifs in temporal networks. In: WSDM, pp 601\u2013610","DOI":"10.1145\/3018661.3018731"},{"key":"158_CR35","doi-asserted-by":"publisher","first-page":"2980","DOI":"10.1038\/srep02980","volume":"3","author":"M De Domenico","year":"2013","unstructured":"De Domenico M, Lima A, Mougel P, Musolesi M (2013) The anatomy of a scientific rumor. Sci Rep 3:2980","journal-title":"Sci Rep"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-021-00158-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-021-00158-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-021-00158-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T01:31:18Z","timestamp":1672277478000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-021-00158-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,29]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["158"],"URL":"https:\/\/doi.org\/10.1007\/s41019-021-00158-0","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,29]]},"assertion":[{"value":"6 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}