{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:55:04Z","timestamp":1780635304824,"version":"3.54.1"},"reference-count":89,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:p>Influence Maximization (IM) is a crucial problem in data science. The goal is to find a fixed-size set of highly influential<jats:italic>seed<\/jats:italic>vertices on a network to maximize the influence spread along the edges. While IM is NP-hard on commonly used diffusion models, a greedy algorithm can achieve (1 - 1\/<jats:italic>e<\/jats:italic>)-approximation by repeatedly selecting the vertex with the highest<jats:italic>marginal gain<\/jats:italic>in influence as the seed. However, we observe two performance issues in the existing work that prevent them from scaling to today's large-scale graphs: space-inefficient memorization to estimate marginal gain, and time-inefficient seed selection process due to a lack of parallelism.<\/jats:p><jats:p>This paper significantly improves the scalability of IM using two key techniques. The first is a<jats:italic>sketch-compression<\/jats:italic>technique for the independent cascading model on undirected graphs. It allows combining the simulation and sketching approaches to achieve a time-space tradeoff. The second technique includes new data structures for parallel seed selection. Using our new approaches, we implemented<jats:italic>PaC-IM<\/jats:italic>: Parallel and Compressed IM.<\/jats:p><jats:p>We compare<jats:italic>PaC-IM<\/jats:italic>with state-of-the-art parallel IM systems on a 96-core machine with 1.5TB memory.<jats:italic>PaC-IM<\/jats:italic>can process the ClueWeb graph with 978M vertices and 75B edges in about 2 hours. On average, across all tested graphs, our uncompressed version is 5--18x faster and about 1.4x more space-efficient than existing parallel IM systems. Using compression further saves 3.8x space with only 70% overhead in time on average.<\/jats:p>","DOI":"10.14778\/3632093.3632104","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:26:31Z","timestamp":1705749991000},"page":"400-413","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Fast and Space-Efficient Parallel Algorithms for Influence Maximization"],"prefix":"10.14778","volume":"17","author":[{"given":"Letong","family":"Wang","sequence":"first","affiliation":[{"name":"UC Riverside"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiangyun","family":"Ding","sequence":"additional","affiliation":[{"name":"UC Riverside"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"UC Riverside"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"UC Riverside"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2010. OpenStreetMap \u00a9 OpenStreetMap contributors. https:\/\/www.openstreetmap.org\/."},{"key":"e_1_2_1_2_1","volume-title":"ACM SIGMOD International Conference on Management of Data (SIGMOD). 651--666","author":"Arora Akhil","year":"2017","unstructured":"Akhil Arora, Sainyam Galhotra, and Sayan Ranu. 2017. Debunking the myths of influence maximization: An in-depth benchmarking study. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 651--666."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"N. S. Arora R. D. Blumofe and C. G. Plaxton. 2001. Thread Scheduling for Multiprogrammed Multiprocessors. Theory of Computing Systems (TOCS) 34 2 (01 Apr 2001).","DOI":"10.1007\/s002240011004"},{"key":"e_1_2_1_4_1","first-page":"28","article-title":"Flash in a DBMS: Where and How","volume":"33","author":"Athanassoulis M.","year":"2010","unstructured":"M. Athanassoulis, A. Ailamaki, S. Chen, P. B. Gibbons, and R. Stoica. 2010. Flash in a DBMS: Where and How? IEEE Data Engineering Bulletin 33, 4 (2010), 28--34. Special issue on data management using modern storage hardware.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_5_1","volume-title":"ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 44--54","author":"Backstrom Lars","year":"2006","unstructured":"Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan. 2006. Group formation in large social networks: membership, growth, and evolution. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 44--54."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"3417","DOI":"10.1007\/s10115-020-01461-4","article-title":"A survey on influence maximization in a social network","volume":"62","author":"Banerjee Suman","year":"2020","unstructured":"Suman Banerjee, Mamata Jenamani, andDilip Kumar Pratihar. 2020. A survey on influence maximization in a social network. Knowledge and Information Systems 62, 9 (2020), 3417--3455.","journal-title":"Knowledge and Information Systems"},{"key":"e_1_2_1_7_1","volume-title":"Implicit Decomposition for Write-Efficient Connectivity Algorithms. In IEEE International Parallel and Distributed Processing Symposium (IPDPS).","author":"Ben-David Naama","year":"2018","unstructured":"Naama Ben-David, Guy E. Blelloch, Jeremy T Fineman, Phillip B Gibbons, Yan Gu, Charles McGuffey, and Julian Shun. 2018. Implicit Decomposition for Write-Efficient Connectivity Algorithms. In IEEE International Parallel and Distributed Processing Symposium (IPDPS)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"1498","DOI":"10.14778\/3397230.3397244","article-title":"Efficient algorithms for budgeted influence maximization on massive social networks","volume":"13","author":"Bian Song","year":"2020","unstructured":"Song Bian, Qintian Guo, Sibo Wang, and Jeffrey Xu Yu. 2020. Efficient algorithms for budgeted influence maximization on massive social networks. Proceedings of the VLDB Endowment 13, 9 (2020), 1498--1510.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_9_1","volume-title":"International Symposium on Experimental Algorithms (SEA). Springer, 28--40","author":"Bingmann Timo","year":"2015","unstructured":"Timo Bingmann, Thomas Keh, and Peter Sanders. 2015. A bulk-parallel priority queue in external memory with STXXL. In International Symposium on Experimental Algorithms (SEA). Springer, 28--40."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3512769","article-title":"Joinable Parallel Balanced Binary Trees","volume":"9","author":"Blelloch Guy","year":"2022","unstructured":"Guy Blelloch, Daniel Ferizovic, and Yihan Sun. 2022. Joinable Parallel Balanced Binary Trees. ACM Transactions on Parallel Computing (TOPC) 9, 2 (2022), 1--41.","journal-title":"ACM Transactions on Parallel Computing (TOPC)"},{"key":"e_1_2_1_11_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 507--509","author":"Blelloch Guy E.","year":"2020","unstructured":"Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib --- a toolkit for parallel algorithms on shared-memory multicore machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 507--509."},{"key":"e_1_2_1_12_1","volume-title":"Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E.","year":"2016","unstructured":"Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. 2016. Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_2_1_13_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 89--102","author":"Blelloch Guy E.","year":"2020","unstructured":"Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. 2020. Optimal parallel algorithms in the binary-forking model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 89--102."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3402819","article-title":"Parallelism in Randomized Incremental Algorithms","volume":"67","author":"Blelloch Guy E.","year":"2020","unstructured":"Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun. 2020. Parallelism in Randomized Incremental Algorithms. J. ACM 67, 5 (2020), 1--27.","journal-title":"J. ACM"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/324133.324234","article-title":"Scheduling multithreaded computations by work stealing","volume":"46","author":"Blumofe Robert D.","year":"1999","unstructured":"Robert D. Blumofe and Charles E. Leiserson. 1999. Scheduling multithreaded computations by work stealing. J. ACM 46, 5 (1999), 720--748.","journal-title":"J. ACM"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 946--957","author":"Borgs Christian","year":"2014","unstructured":"Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. 2014. Maximizing social influence in nearly optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 946--957."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1137\/S0097539790190144","article-title":"Trading space for time in undirected s-t connectivity","volume":"23","author":"Broder Andrei Z","year":"1994","unstructured":"Andrei Z Broder, Anna R Karlin, Prabhakar Raghavan, and Eli Upfal. 1994. Trading space for time in undirected s-t connectivity. SIAM J. Comput. 23, 2 (1994), 324--334.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_18_1","volume-title":"AAAI Conference on Artificial Intelligence","volume":"26","author":"Chen Wei","year":"2012","unstructured":"Wei Chen, Wei Lu, and Ning Zhang. 2012. Time-critical influence maximization in social networks with time-delayed diffusion process. In AAAI Conference on Artificial Intelligence, Vol. 26. 591--598."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 1029--1038","author":"Chen Wei","year":"2010","unstructured":"Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 1029--1038."},{"key":"e_1_2_1_20_1","volume-title":"ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 199--208","author":"Chen Wei","year":"2009","unstructured":"Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 199--208."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 22nd ACM international conference on Information & Knowledge Management. 509--518","author":"Cheng Suqi","year":"2013","unstructured":"Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, and Xueqi Cheng. 2013. Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management. 509--518."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 23rd ACM international conference on conference on information and knowledge management. 629--638","author":"Cohen Edith","year":"2014","unstructured":"Edith Cohen, Daniel Delling, Thomas Pajor, and Renato F Werneck. 2014. Sketch-based influence maximization and computation: Scaling up with guarantees. In Proceedings of the 23rd ACM international conference on conference on information and knowledge management. 629--638."},{"key":"e_1_2_1_23_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd edition). MIT Press.","edition":"3"},{"key":"e_1_2_1_24_1","volume-title":"PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections. In ACM Conference on Programming Language Design and Implementation (PLDI).","author":"Dhulipala Laxman","year":"2022","unstructured":"Laxman Dhulipala, Guy E. Blelloch, Yan Gu, and Yihan Sun. 2022. PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections. In ACM Conference on Programming Language Design and Implementation (PLDI)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3434393","article-title":"Theoretically efficient parallel graph algorithms can be fast and scalable","volume":"8","author":"Dhulipala Laxman","year":"2021","unstructured":"Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2021. Theoretically efficient parallel graph algorithms can be fast and scalable. ACM Transactions on Parallel Computing (TOPC) 8, 1 (2021), 1--70.","journal-title":"ACM Transactions on Parallel Computing (TOPC)"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"653","DOI":"10.14778\/3436905.3436923","article-title":"ConnectIt: a framework for static and incremental parallel graph connectivity algorithms","volume":"14","author":"Dhulipala Laxman","year":"2020","unstructured":"Laxman Dhulipala, Changwan Hong, and Julian Shun. 2020. ConnectIt: a framework for static and incremental parallel graph connectivity algorithms. Proceedings of the VLDB Endowment (PVLDB) 14, 4 (2020), 653--667.","journal-title":"Proceedings of the VLDB Endowment (PVLDB)"},{"key":"e_1_2_1_27_1","volume-title":"Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 184--197","author":"Dong Xiaojun","year":"2021","unstructured":"Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang. 2021. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 184--197."},{"key":"e_1_2_1_28_1","unstructured":"Dheeru Dua and Casey Graf. 2017. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml\/."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"2257","DOI":"10.1137\/S0097539795295948","article-title":"Tight lower bounds for st-connectivity on the NNJAG model","volume":"28","author":"Edmonds Jeff","year":"1999","unstructured":"Jeff Edmonds, Chung Keung Poon, and Dimitris Achlioptas. 1999. Tight lower bounds for st-connectivity on the NNJAG model. SIAM J. Comput. 28, 6 (1999), 2257--2284.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1016\/j.snb.2015.03.028","article-title":"Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring","volume":"215","author":"Fonollosa Jordi","year":"2015","unstructured":"Jordi Fonollosa, Sadique Sheik, Ram\u00f3n Huerta, and Santiago Marco. 2015. Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring. Sensors and Actuators B: Chemical 215 (2015), 618--629.","journal-title":"Sensors and Actuators B: Chemical"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1109\/TPDS.2020.3038376","article-title":"Boosting parallel influence-maximization kernels for undirected networks with fusing and vectorization","volume":"32","author":"G\u00f6kt\u00fcrk G\u00f6khan","year":"2020","unstructured":"G\u00f6khan G\u00f6kt\u00fcrk and Kamer Kaya. 2020. Boosting parallel influence-maximization kernels for undirected networks with fusing and vectorization. IEEE Transactions on Parallel and Distributed Systems 32, 5 (2020), 1001--1013.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"e_1_2_1_32_1","volume-title":"Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing letters 12","author":"Goldenberg Jacob","year":"2001","unstructured":"Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing letters 12 (2001), 211--223."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 20th international conference companion on World wide web. 47--48","author":"Goyal Amit","year":"2011","unstructured":"Amit Goyal, Wei Lu, and Laks VS Lakshmanan. 2011. Celf++ optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference companion on World wide web. 47--48."},{"key":"e_1_2_1_34_1","volume-title":"Threshold models of collective behavior. American journal of sociology 83, 6","author":"Granovetter Mark","year":"1978","unstructured":"Mark Granovetter. 1978. Threshold models of collective behavior. American journal of sociology 83, 6 (1978), 1420--1443."},{"key":"e_1_2_1_35_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Gu Yan","year":"2023","unstructured":"Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan. 2023. Parallel Longest Increasing Subsequence and van Emde Boas Trees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_2_1_36_1","volume-title":"Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 46--60","author":"Gu Yan","year":"2022","unstructured":"Yan Gu, Zachary Napier, and Yihan Sun. 2022. Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 46--60."},{"key":"e_1_2_1_37_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 259--272","author":"Gu Yan","year":"2022","unstructured":"Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang. 2022. Parallel Cover Trees and their Applications. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 259--272."},{"key":"e_1_2_1_38_1","volume-title":"Parallel In-Place Algorithms: Theory and Practice. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). 114--128","author":"Gu Yan","year":"2021","unstructured":"Yan Gu, Omar Obeya, and Julian Shun. 2021. Parallel In-Place Algorithms: Theory and Practice. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). 114--128."},{"key":"e_1_2_1_39_1","volume-title":"ACM SIGMOD International Conference on Management of Data (SIGMOD). 2167--2181","author":"Guo Qintian","year":"2020","unstructured":"Qintian Guo, Sibo Wang, Zhewei Wei, and Ming Chen. 2020. Influence maximization revisited: Efficient reverse reachable set generation with bound tightened. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 2167--2181."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"180","DOI":"10.14778\/3565816.3565821","article-title":"Influence maximization in real-world closed social networks","volume":"16","author":"Huang Shixun","year":"2022","unstructured":"Shixun Huang, Wenqing Lin, Zhifeng Bao, and Jiachen Sun. 2022. Influence maximization in real-world closed social networks. Proceedings of the VLDB Endowment 16, 2 (2022), 180--192.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_41_1","volume-title":"2012 IEEE 12th international conference on data mining. IEEE, 918--923","author":"Jung Kyomin","year":"2012","unstructured":"Kyomin Jung, Wooram Heo, and Wei Chen. 2012. Irie: Scalable and robust influence maximization in social networks. In 2012 IEEE 12th international conference on data mining. IEEE, 918--923."},{"key":"e_1_2_1_42_1","volume-title":"ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 137--146","author":"Kempe David","year":"2003","unstructured":"David Kempe, Jon Kleinberg, and \u00c9va Tardos. 2003. Maximizing the spread of influence through a social network. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 137--146."},{"key":"e_1_2_1_43_1","volume-title":"2013 IEEE 29th international conference on data engineering (ICDE). IEEE, 266--277","author":"Kim Jinha","year":"2013","unstructured":"Jinha Kim, Seung-Keol Kim, and Hwanjo Yu. 2013. Scalable and parallelizable processing of influence maximization for large-scale social networks?. In 2013 IEEE 29th international conference on data engineering (ICDE). IEEE, 266--277."},{"key":"e_1_2_1_44_1","volume-title":"Knowledge Discovery in Databases: PKDD 2006: 10th European Conference on Principles and Practice of Knowledge Discovery in Databases Berlin, Germany, September 18--22, 2006 Proceedings 10","author":"Kimura Masahiro","year":"2006","unstructured":"Masahiro Kimura and Kazumi Saito. 2006. Tractable models for information diffusion in social networks. In Knowledge Discovery in Databases: PKDD 2006: 10th European Conference on Principles and Practice of Knowledge Discovery in Databases Berlin, Germany, September 18--22, 2006 Proceedings 10. Springer, 259--271."},{"key":"e_1_2_1_45_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). 1873--1883","author":"Kosowski Adrian","year":"2013","unstructured":"Adrian Kosowski. 2013. Faster walks in graphs: a \u00d5 (n2) time-space trade-off for undirected st connectivity. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 1873--1883."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1017\/CBO9781139177801.004","article-title":"Submodular function maximization","volume":"3","author":"Krause Andreas","year":"2014","unstructured":"Andreas Krause and Daniel Golovin. 2014. Submodular function maximization. Tractability 3 (2014), 71--104.","journal-title":"Tractability"},{"key":"e_1_2_1_47_1","volume-title":"International World Wide Web Conference (WWW). 591--600","author":"Kwak Haewoon","year":"2010","unstructured":"Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In International World Wide Web Conference (WWW). 591--600."},{"key":"e_1_2_1_48_1","volume-title":"International Conference on Scientific and Statistical Database Management. Springer, 132--150","author":"Kwon YongChul","year":"2010","unstructured":"YongChul Kwon, Dylan Nunley, Jeffrey P Gardner, Magdalena Balazinska, Bill Howe, and Sarah Loebman. 2010. Scalable clustering algorithm for N-body simulations in a shared-nothing cluster. In International Conference on Scientific and Statistical Database Management. Springer, 132--150."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. 420--429","author":"Leskovec Jure","year":"2007","unstructured":"Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. 2007. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. 420--429."},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","article-title":"Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters","volume":"6","author":"Leskovec Jure","year":"2009","unstructured":"Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. 2009. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6, 1 (2009), 29--123.","journal-title":"Internet Mathematics"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","first-page":"1852","DOI":"10.1109\/TKDE.2018.2807843","article-title":"Influence maximization on social graphs: A survey","volume":"30","author":"Li Yuchen","year":"2018","unstructured":"Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. 2018. Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering (TKDE) 30, 10 (2018), 1852--1872.","journal-title":"IEEE Transactions on Knowledge and Data Engineering (TKDE)"},{"key":"e_1_2_1_52_1","volume-title":"International Symposium on Algorithms and Computation (ISAAC). IEEE, 439--448","author":"Liu Bo","year":"2012","unstructured":"Bo Liu, Gao Cong, Dong Xu, and Yifeng Zeng. 2012. Time constrained influence maximization in social networks. In International Symposium on Algorithms and Computation (ISAAC). IEEE, 439--448."},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 23rd ACM international conference on conference on information and knowledge management. 171--180","author":"Liu Qi","year":"2014","unstructured":"Qi Liu, Biao Xiang, Enhong Chen, Hui Xiong, Fangshuang Tang, and Jeffrey Xu Yu. 2014. Influence maximization over large-scale social networks: Abounded linear approach. In Proceedings of the 23rd ACM international conference on conference on information and knowledge management. 171--180."},{"key":"e_1_2_1_54_1","unstructured":"Robert Meusel Oliver Lehmberg Christian Bizer and Sebastiano Vigna. 2014. Web Data Commons --- Hyperlink Graphs. http:\/\/webdatacommons.org\/hyperlinkgraph."},{"key":"e_1_2_1_55_1","volume-title":"International Conference for High Performance Computing, Networking, Storage, and Analysis (SC). 1--11","author":"Minutoli Marco","year":"2020","unstructured":"Marco Minutoli, Maurizio Drocco, Mahantesh Halappanavar, Antonino Tumeo, and Ananth Kalyanaraman. 2020. cuRipples: Influence maximization on multi-GPU systems. In International Conference for High Performance Computing, Networking, Storage, and Analysis (SC). 1--11."},{"key":"e_1_2_1_56_1","volume-title":"2019 IEEE International Conference on Cluster Computing (CLUSTER). IEEE, 1--12","author":"Minutoli Marco","year":"2019","unstructured":"Marco Minutoli, Mahantesh Halappanavar, Ananth Kalyanaraman, Arun Sathanur, Ryan Mcclure, and Jason McDermott. 2019. Fast and scalable implementations of influence maximization algorithms. In 2019 IEEE International Conference on Cluster Computing (CLUSTER). IEEE, 1--12."},{"key":"e_1_2_1_57_1","volume-title":"AAAI Conference on Artificial Intelligence","volume":"29","author":"Mirzasoleiman Baharan","year":"2015","unstructured":"Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrak, and Andreas Krause. 2015. Lazier than lazy greedy. In AAAI Conference on Artificial Intelligence, Vol. 29."},{"key":"e_1_2_1_58_1","volume-title":"ACM SIGMOD International Conference on Management of Data (SIGMOD). 2151--2166","author":"Ohsaka Naoto","year":"2020","unstructured":"Naoto Ohsaka. 2020. The solution distribution of influence maximization: A high-level experimental study on three algorithmic approaches. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 2151--2166."},{"key":"e_1_2_1_59_1","volume-title":"AAAI Conference on Artificial Intelligence.","author":"Ohsaka Naoto","year":"2014","unstructured":"Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. 2014. Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_60_1","unstructured":"Simona Mihaela Orzan. 2004. On distributed verification and verified distribution. (2004)."},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.jnca.2018.01.005","article-title":"Influence analysis in social networks: A survey","volume":"106","author":"Peng Sancheng","year":"2018","unstructured":"Sancheng Peng, Yongmei Zhou, Lihong Cao, Shui Yu, Jianwei Niu, and Weijia Jia. 2018. Influence analysis in social networks: A survey. Journal of Network and Computer Applications 106 (2018), 17--32.","journal-title":"Journal of Network and Computer Applications"},{"key":"e_1_2_1_63_1","volume-title":"Proceedings of the 30th International Conference on Scientific and Statistical Database Management. 1--12","author":"Popova Diana","year":"2018","unstructured":"Diana Popova, Naoto Ohsaka, Ken-ichi Kawarabayashi, and Alex Thomo. 2018. Nosingles: a space-efficient algorithm for influence maximization. In Proceedings of the 30th International Conference on Scientific and Statistical Database Management. 1--12."},{"key":"e_1_2_1_64_1","volume-title":"The Semantic Web-ISWC 2003: Second International Semantic Web Conference","author":"Richardson Matthew","year":"2003","unstructured":"Matthew Richardson, Rakesh Agrawal, and Pedro Domingos. 2003. Trust management for the semantic web. In The Semantic Web-ISWC 2003: Second International Semantic Web Conference, Sanibel Island, EL, USA, October 20--23, 2003. Proceedings 2. Springer, 351--368."},{"key":"e_1_2_1_65_1","unstructured":"Manuel Gomez Rodriguez David Balduzzi and Bernhard Sch\u00f6lkopf. 2011. Uncovering the temporal dynamics of diffusion networks. (2011) 561--568."},{"key":"e_1_2_1_66_1","volume-title":"Sequential and Parallel Algorithms and Data Structures","author":"Sanders Peter","unstructured":"Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, and Roman Dementiev. [n.d.]. Sequential and Parallel Algorithms and Data Structures. Springer."},{"key":"e_1_2_1_67_1","volume-title":"Micromotives and macrobehavior","author":"Schelling Thomas C","unstructured":"Thomas C Schelling. 2006. Micromotives and macrobehavior. WW Norton & Company."},{"key":"e_1_2_1_68_1","volume-title":"Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Shen Zheqi","year":"2022","unstructured":"Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun. 2022. Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_2_1_69_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). 431--448","author":"Shun Julian","year":"2015","unstructured":"Julian Shun, Yan Gu, Guy E. Blelloch, Jeremy T. Fineman, and Phillip B Gibbons. 2015. Sequential random permutation, list contraction and tree contraction are highly parallel. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 431--448."},{"key":"e_1_2_1_70_1","volume-title":"IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 550--559","author":"Slota George M.","year":"2014","unstructured":"George M. Slota, Sivasankaran Rajamanickam, and Kamesh Madduri. 2014. BFS and coloring-based parallel algorithms for strongly connected components and related problems. In IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 550--559."},{"key":"e_1_2_1_71_1","volume-title":"Implementing Parallel and Concurrent Tree Structures. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 447--450","author":"Sun Yihan","year":"2019","unstructured":"Yihan Sun and Guy Blelloch. 2019. Implementing Parallel and Concurrent Tree Structures. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 447--450."},{"key":"e_1_2_1_72_1","volume-title":"Segment and Rectangle Queries with Augmented Maps. In SIAM Symposium on Algorithm Engineering and Experiments (ALENEX). 159--173","author":"Sun Yihan","year":"2019","unstructured":"Yihan Sun and Guy E Blelloch. 2019. Parallel Range, Segment and Rectangle Queries with Augmented Maps. In SIAM Symposium on Algorithm Engineering and Experiments (ALENEX). 159--173."},{"key":"e_1_2_1_73_1","volume-title":"PAM: Parallel Augmented Maps. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP).","author":"Sun Yihan","year":"2018","unstructured":"Yihan Sun, Daniel Ferizovic, and Guy E Blelloch. 2018. PAM: Parallel Augmented Maps. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP)."},{"key":"e_1_2_1_74_1","volume-title":"ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 1539--1554","author":"Tang Youze","year":"2015","unstructured":"Youze Tang, Yanchen Shi, and Xiaokui Xiao. 2015. Influence maximization in near-linear time: A martingale approach. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD). 1539--1554."},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the 2014 ACM SIGMOD international conference on Management of data. 75--86","author":"Tang Youze","year":"2014","unstructured":"Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data. 75--86."},{"key":"e_1_2_1_76_1","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.14778\/3450980.3450981","article-title":"Collective influence maximization for multiple competing products with an awareness-to-influence model","volume":"14","author":"Tsaras Dimitris","year":"2021","unstructured":"Dimitris Tsaras, George Trimponias, Lefteris Ntaflos, and Dimitris Papadias. 2021. Collective influence maximization for multiple competing products with an awareness-to-influence model. Proceedings of the VLDB Endowment 14, 7 (2021), 1124--1136.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_77_1","doi-asserted-by":"crossref","unstructured":"Letong Wang Xiangyun Ding Yan Gu and Yihan Sun. 2023. Fast and Space-Efficient Parallel Algorithms for Influence Maximization. arXiv:2311.07554 [cs.DS]","DOI":"10.14778\/3632093.3632104"},{"key":"e_1_2_1_78_1","volume-title":"Parallel Strong Connectivity Based on Faster Reachability. In ACM SIGMOD International Conference on Management of Data (SIGMOD).","author":"Wang Letong","year":"2023","unstructured":"Letong Wang, Xiaojun Dong, Yan Gu, and Yihan Sun. 2023. Parallel Strong Connectivity Based on Faster Reachability. In ACM SIGMOD International Conference on Management of Data (SIGMOD)."},{"key":"e_1_2_1_79_1","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1109\/TKDE.2016.2624734","article-title":"Bring order into the samples: A novel scalable method for influence maximization","volume":"29","author":"Wang Xiaoyang","year":"2016","unstructured":"Xiaoyang Wang, Ying Zhang, Wenjie Zhang, Xuemin Lin, and Chen Chen. 2016. Bring order into the samples: A novel scalable method for influence maximization. IEEE Transactions on Knowledge and Data Engineering 29, 2 (2016), 243--256.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_80_1","volume-title":"Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 1039--1048","author":"Wang Yu","year":"2010","unstructured":"Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie. 2010. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 1039--1048."},{"key":"e_1_2_1_81_1","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/3469379.3469384","article-title":"GeoGraph: A Framework for Graph Processing on Geometric Data","volume":"55","author":"Wang Yiqiu","year":"2021","unstructured":"Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun. 2021. GeoGraph: A Framework for Graph Processing on Geometric Data. ACM SIGOPS Operating Systems Review 55, 1 (2021), 38--46.","journal-title":"ACM SIGOPS Operating Systems Review"},{"key":"e_1_2_1_82_1","volume-title":"ACM Symposium on Computational Geometry (SoCG).","author":"Wang Yiqiu","year":"2021","unstructured":"Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. 2021. A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem. In ACM Symposium on Computational Geometry (SoCG)."},{"key":"e_1_2_1_83_1","volume-title":"Hindering Influence Diffusion of Community. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 2518--2520","author":"Xie Jiadong","year":"2022","unstructured":"Jiadong Xie. 2022. Hindering Influence Diffusion of Community. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 2518--2520."},{"key":"e_1_2_1_84_1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s10115-013-0693-z","article-title":"Defining and evaluating network communities based on ground-truth","volume":"42","author":"Yang Jaewon","year":"2015","unstructured":"Jaewon Yang and Jure Leskovec. 2015. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42, 1 (2015), 181--213.","journal-title":"Knowledge and Information Systems"},{"key":"e_1_2_1_85_1","doi-asserted-by":"crossref","first-page":"2473","DOI":"10.14778\/3476249.3476295","article-title":"GRAIN: improving data efficiency of graph neural networks via diversified in fluence maximization","volume":"14","author":"Zhang Wentao","year":"2021","unstructured":"Wentao Zhang, Zhi Yang, Yexin Wang, Yu Shen, Yang Li, Liang Wang, and Bin Cui. 2021. GRAIN: improving data efficiency of graph neural networks via diversified in fluence maximization. Proceedings of the VLDB Endowment 14, 11 (2021), 2473--2482.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_86_1","volume-title":"International World Wide Web Conference (WWW). 247--256","author":"Zheng Yu","year":"2008","unstructured":"Yu Zheng, Like Liu, Longhao Wang, and Xing Xie. 2008. Learning transportation mode from raw gps data for geographic applications on the web. In International World Wide Web Conference (WWW). 247--256."},{"key":"e_1_2_1_87_1","doi-asserted-by":"crossref","first-page":"2770","DOI":"10.1109\/TKDE.2015.2419659","article-title":"On the upper bounds of spread for greedy algorithms in social network influence maximization","volume":"27","author":"Zhou Chuan","year":"2015","unstructured":"Chuan Zhou, Peng Zhang, Wenyu Zang, and Li Guo. 2015. On the upper bounds of spread for greedy algorithms in social network influence maximization. IEEE Transactions on Knowledge and Data Engineering 27, 10 (2015), 2770--2783.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_88_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3433000","article-title":"A survey of information cascade analysis: Models, predictions, and recent advances","volume":"54","author":"Zhou Fan","year":"2021","unstructured":"Fan Zhou, Xovee Xu, Goce Trajcevski, and Kunpeng Zhang. 2021. A survey of information cascade analysis: Models, predictions, and recent advances. ACM Computing Surveys (CSUR) 54, 2 (2021), 1--36.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"e_1_2_1_89_1","doi-asserted-by":"crossref","first-page":"348","DOI":"10.14778\/3489496.3489514","article-title":"Analysis of influence contribution in social advertising","volume":"15","author":"Zhu Yuqing","year":"2021","unstructured":"Yuqing Zhu, Jing Tang, Xueyan Tang, and Lei Chen. 2021. Analysis of influence contribution in social advertising. Proceedings of the VLDB Endowment 15, 2 (2021), 348--360.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_90_1","volume-title":"Influence Maximization in Dynamic Social Networks. In IEEE International Conference on Data Mining (ICDM).","author":"Zhuang Honglei","year":"2013","unstructured":"Honglei Zhuang, Yihan Sun, Jie Tang, Zhang Jialin, and Xiaoming Sun. 2013. Influence Maximization in Dynamic Social Networks. In IEEE International Conference on Data Mining (ICDM)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3632093.3632104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T17:58:27Z","timestamp":1731088707000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3632093.3632104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11]]},"references-count":89,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.14778\/3632093.3632104"],"URL":"https:\/\/doi.org\/10.14778\/3632093.3632104","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,11]]},"assertion":[{"value":"2024-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}