{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T14:50:24Z","timestamp":1776351024823,"version":"3.51.2"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,5,30]],"date-time":"2020-05-30T00:00:00Z","timestamp":1590796800000},"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\/IMS Trans. Data Sci."],"published-print":{"date-parts":[[2020,5,31]]},"abstract":"<jats:p>Influence maximization with application to viral marketing is a well-studied problem of finding a small number of influential users in a social network to maximize the spread of influence under certain influence cascade models. However, almost all previous studies have focused on node-level mining, where they consider identifying nodes as the initial seeders to achieve the desired outcomes. In this article, instead of targeting nodes, we investigate a new boosted influence maximization problem from the edge-level perspective, which asks for finding an edge set that is added to the network to maximize the increased influence spread of a given seed set. We show that the problem is NP-hard and the influence spread function no longer exhibits the property of submodularity, which impose more challenging on the problem. Therefore, we devise a restricted form that is submodular and propose a greedy algorithm with approximate guarantee to solve the problem. However, because of its poor computational efficiency, we further propose an improved greedy algorithm that integrates several effective optimization strategies to significantly speed up the edge selection without sacrificing its accuracy. Extensive experiments over real-world available social networks of different sizes demonstrate the effectiveness and efficiency of the proposed methods.<\/jats:p>","DOI":"10.1145\/3364993","type":"journal-article","created":{"date-parts":[[2020,5,31]],"date-time":"2020-05-31T00:09:30Z","timestamp":1590883770000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Maximizing Boosted Influence Spread with Edge Addition in Online Social Networks"],"prefix":"10.1145","volume":"1","author":[{"given":"Lei","family":"Yu","sequence":"first","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, Hubei, China"}]},{"given":"Guohui","family":"Li","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, Hubei, China"}]},{"given":"Ling","family":"Yuan","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, Hubei, China"}]}],"member":"320","published-online":{"date-parts":[[2020,5,30]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"Link injection for boosting information spread in social networks","volume":"4","author":"Antaris Stefanos","year":"2014","unstructured":"Stefanos Antaris, Dimitrios Rafailidis, and Alexandros Nanopoulos. 2014. Link injection for boosting information spread in social networks. Soc. Netw. Anal. Min. 4, 1 (2014), 1--16.","journal-title":"Soc. Netw. Anal. Min."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS\u201918)","author":"Bogunovic Ilija","year":"2018","unstructured":"Ilija Bogunovic, Junyao Zhao, and Volkan Cevher. 2018. Robust maximization of nonsubmodular objectives. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS\u201918)."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 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 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 946--957."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-011-0815-0"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 21st ACM International Conference on World Wide Web, 529--539","author":"Chaoji Vineet","year":"2012","unstructured":"Vineet Chaoji, Sayan Ranu, Rajeev Rastogi, and Rushi Bhatt. 2012. Recommendations to boost content spread in social networks. In Proceedings of the 21st ACM International Conference on World Wide Web, 529--539."},{"key":"e_1_2_1_6_1","volume-title":"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 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1029--1038."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 10th IEEE International Conference on Data Mining, 88--97","author":"Chen Wei","year":"2011","unstructured":"Wei Chen, Yifei Yuan, and Li Zhang. 2011. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the 10th IEEE International Conference on Data Mining, 88--97."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2532549"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1509\/jmkr.43.3.345"},{"key":"e_1_2_1_10_1","article-title":"Greedily improving our own closeness centrality in a network","volume":"11","author":"Crescenzi Pierluigi","year":"2016","unstructured":"Pierluigi Crescenzi, Gianlorenzo D\u2019angelo, Lorenzo Severini, and Yllka Velaj. 2016. Greedily improving our own closeness centrality in a network. ACM Trans. Knowl. Discov. Data 11, 1, Article 9 (2016), 32 pages.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.01.017"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of International Conference on Machine Learning, 1057--1064","author":"Das Abhimanyu","year":"2011","unstructured":"Abhimanyu Das and David Kempe. 2011. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of International Conference on Machine Learning, 1057--1064."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of theScandinavian Conference on Algorithm\u00a0Theory, 420--431","author":"Erik","unstructured":"Erik D. Demaine and Morteza Zadimoghaddam. 2010. Minimizing the diameter of a network using shortcut edges. In Proceedings of theScandinavian Conference on Algorithm\u00a0Theory, 420--431."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 57--66","author":"Domingos Pedro","year":"2001","unstructured":"Pedro Domingos and Matthew Richardson. 2001. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 57--66."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9886-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","article-title":"The complexity of enumeration and reliability problems","volume":"8","author":"Valiant Leslie","year":"1979","unstructured":"Valiant Leslie G. 1979. The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 3 (1979), 410--421.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s10115-010-0321-0","article-title":"Network immunization and virus propagation in email networks: experimental evaluation and analysis","volume":"27","author":"Gao Chao","year":"2011","unstructured":"Chao Gao, Jiming Liu, and Ning Zhong. 2011. Network immunization and virus propagation in email networks: experimental evaluation and analysis. Knowl. Inf. Syst. 27, 2 (2011), 253--279.","journal-title":"Knowl. Inf. Syst."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the IEEE Conference on Decision and Control, 6605--6611","author":"Ghosh Arpita","year":"2006","unstructured":"Arpita Ghosh and Stephen Boyd. 2006. Growing well-connected graphs. In Proceedings of the IEEE Conference on Decision and Control, 6605--6611."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011122126881"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the ACM International Conference Companion on World Wide Web, 47--48","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 Proceedings of the ACM International Conference Companion on World Wide Web, 47--48."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the IEEE International Conference on Data Mining, 918--923","author":"Jung Kyomin","year":"2013","unstructured":"Kyomin Jung, Wooram Heo, and Wei Chen. 2013. IRIE: Scalable and robust influence maximization in social networks. In Proceedings of the IEEE International Conference on Data Mining, 918--923."},{"key":"e_1_2_1_22_1","first-page":"618","article-title":"Reducibility among combinatorial problems","volume":"40","author":"Karp Richard","year":"2010","unstructured":"Richard Karp. 2010. Reducibility among combinatorial problems. J. Symbol. Logic 40, 4 (2010), 618--619.","journal-title":"J. Symbol. Logic"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 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 Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 137--146."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 23rd National Conference on Artificial Intelligence, 1175--1180","author":"Kimura Masahiro","year":"2008","unstructured":"Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. 2008. Minimizing the spread of contamination by blocking links in a network. In Proceedings of the 23rd National Conference on Artificial Intelligence, 1175--1180."},{"key":"e_1_2_1_25_1","first-page":"50","article-title":"Solving the contamination minimization problem on networks for the linear threshold model. Malay","volume":"12","author":"Kimura Masahiro","year":"2008","unstructured":"Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. 2008. Solving the contamination minimization problem on networks for the linear threshold model. Malay. J. Med. Sci. 12, 2 (2008), 50--55.","journal-title":"J. Med. Sci."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514888.1514892"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the IEEE International Conference on Data Mining, 399--408","author":"Kuhlman Chris J.","unstructured":"Chris J. Kuhlman, Gaurav Tuli, Samarth Swarup, Madhav V. Marathe, and S. S. Ravi. 2013. Blocking simple and complex contagion by edge removal. In Proceedings of the IEEE International Conference on Data Mining, 399--408."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the ACM International Conference on Web Search and Data Mining, 657--666","author":"Li Yanhua","year":"2013","unstructured":"Yanhua Li, Wei Chen, Yajun Wang, and Zhi-Li Zhang. 2013. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. Proceedings of the ACM International Conference on Web Search and Data Mining, 657--666."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 128--134","author":"Mossel Elchanan","year":"2007","unstructured":"Elchanan Mossel and Sebastien Roch. 2007. On the submodularity of influence in social networks. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 128--134."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the ACM International Conference on Management of Data, 695--710","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 Proceedings of the ACM International Conference on Management of Data, 695--710."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2757281"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.tcs.2011.05.014","article-title":"Improved approximability and non-approximability results for graph diameter decreasing problems","volume":"417","author":"Proietti Guido","year":"2012","unstructured":"Guido Proietti. 2012. Improved approximability and non-approximability results for graph diameter decreasing problems. Theor. Comput. Sci. 417, 1 (2012), 12--22.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2014.09.037"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 61--70","author":"Richardson Matthew","year":"2002","unstructured":"Matthew Richardson and Pedro Domingos. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 61--70."},{"key":"e_1_2_1_38_1","unstructured":"SNAP Datasets. 2014. Retrieved from http:\/\/snap.stanford.edu\/data\/."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data, 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 Proceedings of ACM SIGMOD International Conference on Management of Data, 1539--1554."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of 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 ACM SIGMOD International Conference on Management of Data, 75--86."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 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 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1039--1048."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the ACM International Conference on World Wide Web, 423--424","author":"Zhou Chuan","year":"2014","unstructured":"Chuan Zhou, Peng Zhang, Wenyu Zang, and Li Guo. 2014. Maximizing the long-term integral influence in social networks under the voter model. In Proceedings of the ACM International Conference on World Wide Web, 423--424."}],"container-title":["ACM\/IMS Transactions on Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364993","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3364993","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T13:56:29Z","timestamp":1776347789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364993"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,30]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,5,31]]}},"alternative-id":["10.1145\/3364993"],"URL":"https:\/\/doi.org\/10.1145\/3364993","relation":{},"ISSN":["2691-1922"],"issn-type":[{"value":"2691-1922","type":"print"}],"subject":[],"published":{"date-parts":[[2020,5,30]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}