{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T18:30:37Z","timestamp":1775932237370,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T00:00:00Z","timestamp":1618963200000},"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":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            Influence Maximization (IM) problem is to select\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            influential users to maximize the influence spread, which plays an important role in many real-world applications such as product recommendation, epidemic control, and network monitoring. Nowadays multiple kinds of information can propagate in online social networks simultaneously, but current literature seldom discuss about this phenomenon. Accordingly, in this article, we propose Multiple Influence Maximization (MIM) problem where multiple information can propagate in a single network with different propagation probabilities. The goal of MIM problems is to maximize the overall accumulative influence spreads of different information with the limit of seed budget\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . To solve MIM problems, we first propose a greedy framework to solve MIM problems which maintains an\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            -approximate ratio. We further propose parallel algorithms based on semaphores, an inter-thread communication mechanism, which significantly improves our algorithms efficiency. Then we conduct experiments for our framework using complex social network datasets with 12k, 154k, 317k, and 1.1m nodes, and the experimental results show that our greedy framework outperforms other heuristic algorithms greatly for large influence spread and parallelization of algorithms reduces running time observably with acceptable memory overhead.\n          <\/jats:p>","DOI":"10.1145\/3442341","type":"journal-article","created":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T15:42:54Z","timestamp":1619019774000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Parallel Greedy Algorithm\u00a0to Multiple Influence Maximization in Social Network"],"prefix":"10.1145","volume":"15","author":[{"given":"Guanhao","family":"Wu","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofeng","family":"Gao","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ge","family":"Yan","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guihai","family":"Chen","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Open Proceedings International Conference on Extending Database Technology (EDBT\u201914)","author":"Aslay Cigdem","unstructured":"Cigdem Aslay , Nicola Barbieri , Francesco Bonchi , and Ricardo A . Baeza-Yates. 2014. Online topic-aware influence maximization queries . In Open Proceedings International Conference on Extending Database Technology (EDBT\u201914) . 295\u2013306. Cigdem Aslay, Nicola Barbieri, Francesco Bonchi, and Ricardo A. Baeza-Yates. 2014. Online topic-aware influence maximization queries. In Open Proceedings International Conference on Extending Database Technology (EDBT\u201914). 295\u2013306."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0646-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.70"},{"key":"e_1_2_1_4_1","first-page":"666","article-title":"Online topic-aware influence maximization","volume":"8","author":"Chen Shuo","year":"2015","unstructured":"Shuo Chen , Ju Fan , Guoliang Li , Jianhua Feng , Kian-lee Tan, and Jinhui Tang . 2015 . Online topic-aware influence maximization . The International Journal on Very Large Data Bases 8 , 6 (2015), 666 \u2013 677 . Shuo Chen, Ju Fan, Guoliang Li, Jianhua Feng, Kian-lee Tan, and Jinhui Tang. 2015. Online topic-aware influence maximization. The International Journal on Very Large Data Bases 8, 6 (2015), 666\u2013677.","journal-title":"The International Journal on Very Large Data Bases"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939745"},{"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\/1557019.1557047"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505541"},{"key":"e_1_2_1_10_1","volume-title":"The Origin of Concurrent Programming","author":"Dijkstra Edsger W.","unstructured":"Edsger W. Dijkstra . 1968. Cooperating sequential processes . In The Origin of Concurrent Programming . Springer , 65\u2013138. Edsger W. Dijkstra. 1968. Cooperating sequential processes. In The Origin of Concurrent Programming. Springer, 65\u2013138."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_12_1","volume-title":"Wolsey","author":"Fisher Marshall L.","year":"1978","unstructured":"Marshall L. Fisher , George L. Nemhauser , and Laurence A . Wolsey . 1978 . An analysis of approximations for maximizing submodular set functions\u2014II. In Polyhedral Combinatorics. Springer , 73\u201387. Marshall L. Fisher, George L. Nemhauser, and Laurence A. Wolsey. 1978. An analysis of approximations for maximizing submodular set functions\u2014II. In Polyhedral Combinatorics. Springer, 73\u201387."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882929"},{"key":"e_1_2_1_14_1","volume-title":"ACM International Conference Companion on World Wide Web (WWW\u201911)","author":"Goyal Amit","unstructured":"Amit Goyal , Wei Lu , and Laks V.S. Lakshmanan . 2011. CELF++: Optimizing the greedy algorithm for influence maximization in social networks . In ACM International Conference Companion on World Wide Web (WWW\u201911) . 47\u201348. Amit Goyal, Wei Lu, and Laks V.S. Lakshmanan. 2011. CELF++: Optimizing the greedy algorithm for influence maximization in social networks. In ACM International Conference Companion on World Wide Web (WWW\u201911). 47\u201348."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.132"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623746"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939760"},{"key":"e_1_2_1_18_1","volume-title":"Stability and robustness in influence maximization. ACM Transactions on Knowledge Discovery from Data 12, 6","author":"He Xinran","year":"2018","unstructured":"Xinran He and David Kempe . 2018. Stability and robustness in influence maximization. ACM Transactions on Knowledge Discovery from Data 12, 6 ( 2018 ), 1\u201334. Xinran He and David Kempe. 2018. Stability and robustness in influence maximization. ACM Transactions on Knowledge Discovery from Data 12, 6 (2018), 1\u201334."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.40"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.79"},{"key":"e_1_2_1_21_1","volume-title":"International Conference on Machine Learning (ICML\u201919)","volume":"97","author":"Kalimeris Dimitris","year":"2019","unstructured":"Dimitris Kalimeris , Gal Kaplun , and Yaron Singer . 2019 . Robust influence maximization for hyperparametric models . In International Conference on Machine Learning (ICML\u201919) . Vol. 97 . 3192\u20133200. Dimitris Kalimeris, Gal Kaplun, and Yaron Singer. 2019. Robust influence maximization for hyperparametric models. In International Conference on Machine Learning (ICML\u201919). Vol. 97. 3192\u20133200."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_23_1","volume-title":"Revenue maximization by viral marketing: A social network host\u2019s perspective","author":"Khan Arijit","unstructured":"Arijit Khan , Benjamin Zehnder , and Donald Kossmann . 2016. Revenue maximization by viral marketing: A social network host\u2019s perspective . In IEEE Data Engineering (ICDE\u2019 16). 37\u201348. Arijit Khan, Benjamin Zehnder, and Donald Kossmann. 2016. Revenue maximization by viral marketing: A social network host\u2019s perspective. In IEEE Data Engineering (ICDE\u201916). 37\u201348."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783271"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_26_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588561"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0366-x"},{"key":"e_1_2_1_29_1","volume-title":"International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201916)","author":"Lowalekar Meghna","year":"2016","unstructured":"Meghna Lowalekar , Pradeep Varakantham , and Akshat Kumar . 2016 . Robust influence maximization . In International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201916) . 1395\u20131396. Meghna Lowalekar, Pradeep Varakantham, and Akshat Kumar. 2016. Robust influence maximization. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201916). 1395\u20131396."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40649-014-0001-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.43"},{"key":"e_1_2_1_32_1","volume-title":"International Conference on Management of Data (SIGMOD\u201916)","author":"Nguyen Hung T.","unstructured":"Hung T. Nguyen , My T. Thai , and Thang N. Dinh . 2016. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks . In International Conference on Management of Data (SIGMOD\u201916) . 695\u2013710. Hung T. Nguyen, My T. Thai, and Thang N. Dinh. 2016. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In International Conference on Management of Data (SIGMOD\u201916). 695\u2013710."},{"key":"e_1_2_1_33_1","volume-title":"AAAI Conference on Artificial Intelligence (AAAI\u201914)","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 (AAAI\u201914) . 138\u2013144. 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 (AAAI\u201914). 138\u2013144."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064045"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3221269.3221291"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-016-2068-3"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_39_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K . Ahmed . 2015 . The network data repository with interactive graph analytics and visualization. In ACM Association for the Advancement of Artificial Intelligence (AAAI\u201915). 4292\u20134293. Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization. In ACM Association for the Advancement of Artificial Intelligence (AAAI\u201915). 4292\u20134293."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/831"},{"key":"e_1_2_1_43_1","first-page":"805","article-title":"Real-time influence maximization on dynamic social streams","volume":"10","author":"Wang Yanhao","year":"2017","unstructured":"Yanhao Wang , Qi Fan , Yuchen Li , and Kian-Lee Tan . 2017 . Real-time influence maximization on dynamic social streams . The International Journal on Very Large Data Bases 10 , 7 (2017), 805 \u2013 816 . Yanhao Wang, Qi Fan, Yuchen Li, and Kian-Lee Tan. 2017. Real-time influence maximization on dynamic social streams. The International Journal on Very Large Data Bases 10, 7 (2017), 805\u2013816.","journal-title":"The International Journal on Very Large Data Bases"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2019.2938575"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442341","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442341","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:15Z","timestamp":1750193295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442341"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,21]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3442341"],"URL":"https:\/\/doi.org\/10.1145\/3442341","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,21]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}