{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T01:58:17Z","timestamp":1768355897290,"version":"3.49.0"},"reference-count":42,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2020,7,29]],"date-time":"2020-07-29T00:00:00Z","timestamp":1595980800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Influence Maximization (IM) problem, which finds a set of k nodes (called seedset) in a social network to initiate the influence spread so that the number of influenced nodes after propagation process is maximized, is an important problem in information propagation and social network analysis. However, previous studies ignored the constraint of priority that led to inefficient seed collections. In some real situations, companies or organizations often prioritize influencing potential users during their influence diffusion campaigns. With a new approach to these existing works, we propose a new problem called Influence Maximization with Priority (IMP) which finds out a set seed of k nodes in a social network to be able to influence the largest number of nodes subject to the influence spread to a specific set of nodes U (called priority set) at least a given threshold T in this paper. We show that the problem is NP-hard under well-known IC model. To find the solution, we propose two efficient algorithms, called Integrated Greedy (IG) and Integrated Greedy Sampling (IGS) with provable theoretical guarantees. IG provides a 1\u2212(1\u22121k)t-approximation solution with t is an outcome of algorithm and t\u22651. The worst-case approximation ratio is obtained when t=1 and it is equal to 1\/k. In addition, IGS is an efficient randomized approximation algorithm based on sampling method that provides a 1\u2212(1\u22121k)t\u2212\u03f5-approximation solution with probability at least 1\u2212\u03b4 with \u03f5&gt;0,\u03b4\u2208(0,1) as input parameters of the problem. We conduct extensive experiments on various real networks to compare our IGS algorithm to the state-of-the-art algorithms in IM problem. The results indicate that our algorithm provides better solutions interns of influence on the priority sets when approximately give twice to ten times higher than threshold T while running time, memory usage and the influence spread also give considerable results compared to the others.<\/jats:p>","DOI":"10.3390\/a13080183","type":"journal-article","created":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T03:36:38Z","timestamp":1596080198000},"page":"183","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Influence Maximization with Priority in Online Social Networks"],"prefix":"10.3390","volume":"13","author":[{"given":"Canh V.","family":"Pham","sequence":"first","affiliation":[{"name":"Faculty of Information and Security Technology, People\u2019s Security Academy, Hanoi 100000, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dung K. T.","family":"Ha","sequence":"additional","affiliation":[{"name":"Faculty of Information and Security Technology, People\u2019s Security Academy, Hanoi 100000, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quang C.","family":"Vu","sequence":"additional","affiliation":[{"name":"Faculty of Information and Security Technology, People\u2019s Security Academy, Hanoi 100000, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anh N.","family":"Su","sequence":"additional","affiliation":[{"name":"Faculty of Information and Security Technology, People\u2019s Security Academy, Hanoi 100000, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huan X.","family":"Hoang","sequence":"additional","affiliation":[{"name":"Vietnam National University, Hanoi 100000, Vietnam"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,7,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J.M., and Tardos, \u00c9. (2003, January 24\u201327). Maximizing the spread of influence through a social network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/956750.956769"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2419","DOI":"10.1109\/TNET.2017.2691544","article-title":"A Billion-Scale Approximation Algorithm for Maximizing Benefit in Viral Marketing","volume":"25","author":"Nguyen","year":"2017","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_3","first-page":"1070","article-title":"Real-time Targeted Influence Maximization for Online Advertisements","volume":"8","author":"Li","year":"2015","journal-title":"PVLDB"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1202","DOI":"10.1007\/s10878-018-0252-3","article-title":"Maximizing misinformation restriction within time and budget constraints","volume":"35","author":"Pham","year":"2018","journal-title":"J. Comb. Optim."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Tong, G.A., Wu, W., Guo, L., Li, D., Liu, C., Liu, B., and Du, D. (2017, January 1\u20134). An efficient randomized algorithm for rumor blocking in online social networks. Proceedings of the 2017 IEEE Conference on Computer Communications, INFOCOM 2017, Atlanta, GA, USA.","DOI":"10.1109\/INFOCOM.2017.8056957"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Budak, C., Agrawal, D., and El Abbadi, A. (April, January 28). Limiting the spread of misinformation in social networks. Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India.","DOI":"10.1145\/1963405.1963499"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1109\/TKDE.2019.2904969","article-title":"Blocking Self-avoiding Walks Stops Cyber-epidemics: A Scalable GPU-based Approach","volume":"32","author":"Nguyen","year":"2020","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2133","DOI":"10.1016\/j.comnet.2013.04.002","article-title":"Analysis of misinformation containment in online social networks","volume":"57","author":"Nguyen","year":"2013","journal-title":"Comput. Netw."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"18:1","DOI":"10.1145\/2885494","article-title":"Misinformation in Online Social Networks: Detect Them All with a Limited Budget","volume":"34","author":"Zhang","year":"2016","journal-title":"ACM Trans. Inf. Syst."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Zhang, H., Kuhnle, A., Zhang, H., and Thai, M.T. (2016, January 18\u201321). Detecting misinformation in online social networks before it is too late. Proceedings of the 2016 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016, San Francisco, CA, USA.","DOI":"10.1109\/ASONAM.2016.7752288"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ye, M., Liu, X., and Lee, W. (2012, January 12\u201316). Exploring social influence for recommendation: A generative model approach. Proceedings of the 35th International ACM SIGIR conference on research and development in Information Retrieval, SIGIR \u201912, Portland, OR, USA.","DOI":"10.1145\/2348283.2348373"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Chen, W., Collins, A., Cummings, R., Ke, T., Liu, Z., Rinc\u00f3n, D., Sun, X., Wang, Y., Wei, W., and Yuan, Y. (2011, January 28\u201330). Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate. Proceedings of the Eleventh SIAM International Conference on Data Mining, SDM 2011, Mesa, AZ, USA.","DOI":"10.1137\/1.9781611972818.33"},{"key":"ref_13","unstructured":"Borodin, A., Filmus, Y., and Oren, J. (2010, January 13\u201317). Threshold Models for Competitive Influence in Social Networks. Proceedings of the Internet and Network Economics\u20146th International Workshop, WINE 2010, Stanford, CA, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Tang, Y., Shi, Y., and Xiao, X. (June, January 31). Influence Maximization in Near-Linear Time: A Martingale Approach. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia.","DOI":"10.1145\/2723372.2723734"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Nguyen, H.T., Thai, M.T., and Dinh, T.N. (July, January 26). Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks. Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA.","DOI":"10.1145\/2882903.2915207"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Chen, W., Yuan, Y., and Zhang, L. (2010, January 14\u201317). Scalable Influence Maximization in Social Networks under the Linear Threshold Model. Proceedings of the ICDM 2010, The 10th IEEE International Conference on Data Mining, Sydney, Australia.","DOI":"10.1109\/ICDM.2010.118"},{"key":"ref_17","first-page":"666","article-title":"Online Topic-Aware Influence Maximization","volume":"8","author":"Chen","year":"2015","journal-title":"PVLDB"},{"key":"ref_18","unstructured":"Aslay, \u00c7., Barbieri, N., Bonchi, F., and Baeza-Yates, R.A. (2014, January 24\u201328). Online Topic-aware Influence Maximization Queries. Proceedings of the 17th International Conference on Extending Database Technology, EDBT 2014, Athens, Greece."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Pham, C.V., Duong, H.V., Hoang, H.X., and Thai, M.T. (2019). Competitive Influence Maximization within Time and Budget Constraints in Online Social Networks: An Algorithmic Approach. Appl. Sci., 9.","DOI":"10.3390\/app9112274"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Tang, Y., Xiao, X., and Shi, Y. (2014, January 22\u201327). Influence maximization: Near-optimal time complexity meets practical efficiency. Proceedings of the International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA.","DOI":"10.1145\/2588555.2593670"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Domingos, P.M., and Richardson, M. (2001, January 26\u201329). Mining the network value of customers. Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, San Francisco, CA, USA.","DOI":"10.1145\/502512.502525"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J.M., and Glance, N.S. (2007, January 12\u201315). Cost-effective outbreak detection in networks. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, CA, USA.","DOI":"10.1145\/1281192.1281239"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Tang, J., Tang, X., Xiao, X., and Yuan, J. (2018, January 10\u201315). Online Processing Algorithms for Influence Maximization. Proceedings of the 2018 International Conference on Management of Data (SIGMOD\u2019 18), Houston, TX, USA.","DOI":"10.1145\/3183713.3183749"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1084","DOI":"10.1109\/JSAC.2013.130610","article-title":"On Budgeted Influence Maximization in Social Networks","volume":"31","author":"Nguyen","year":"2013","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Pham, C.V., Duong, H.V., and Thai, M.T. (2019, January 18\u201320). Importance Sample-Based Approximation Algorithm for Cost-Aware Targeted Viral Marketing. Proceedings of the Computational Data and Social Networks\u20148th International Conference, CSoNet 2019, Ho Chi Minh City, Vietnam.","DOI":"10.1007\/978-3-030-34980-6_14"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1109\/TNET.2019.2898413","article-title":"TipTop: (Almost) Exact Solutions for Influence Maximization in Billion-Scale Networks","volume":"27","author":"Li","year":"2019","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/s10115-013-0646-6","article-title":"Topic-aware social influence propagation models","volume":"37","author":"Barbieri","year":"2013","journal-title":"Knowl. Inf. Syst."},{"key":"ref_28","unstructured":"Li, G., Chen, S., Feng, J., Tan, K.-L., and Li, W.-S. (2018, January 16\u201319). Efficient Location-Aware Influence Maximization. Proceedings of the 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/TKDE.2016.2633472","article-title":"Efficient Distance-Aware Influence Maximization in Geo-Social Networks","volume":"29","author":"Wang","year":"2017","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_30","unstructured":"Bharathi, S., Kempe, D., and Salek, M. (2007, January 12\u201314). Competitive Influence Maximization in Social Networks. Proceedings of the Internet and Network Economics, Third International Workshop, WINE 2007, San Diego, CA, USA."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1016\/j.knosys.2016.07.008","article-title":"Containment of competitive influence spread in social networks","volume":"109","author":"Liu","year":"2016","journal-title":"Knowl.-Based Syst."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"He, X., Song, G., Chen, W., and Jiang, Q. (2012, January 26\u201328). Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model. Proceedings of the Twelfth SIAM International Conference on Data Mining, Anaheim, CA, USA.","DOI":"10.1137\/1.9781611972825.40"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Lu, W., Bonchi, F., Goyal, A., and Lakshmanan, L.V.S. (2013, January 11\u201314). The bang for the buck: Fair competitive viral marketing from the host perspective. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, IL, USA.","DOI":"10.1145\/2487575.2487649"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Chen, W., Lakshmanan, L.V.S., and Castillo, C. (2013). Information and Influence Propagation in Social Networks, Morgan & Claypool Publishers. Synthesis Lectures on Data Management.","DOI":"10.2200\/S00527ED1V01Y201308DTM037"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.knosys.2017.07.029","article-title":"Community-based influence maximization in social networks under a competitive linear threshold model","volume":"134","author":"Bozorgi","year":"2017","journal-title":"Knowl.-Based Syst."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Tsang, A., Wilder, B., Rice, E., Tambe, M., and Zick, Y. (2019, January 10\u201316). Group-Fairness in Influence Maximization. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China.","DOI":"10.24963\/ijcai.2019\/831"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Farnadi, G., Babaki, B., and Gendreau, M. (2020, January 20\u201324). A Unifying Framework for Fairness-Aware Influence Maximization. Proceedings of the Companion of The 2020 Web Conference 2020, Taipei, Taiwan.","DOI":"10.1145\/3366424.3383555"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Stoica, A., Han, J.X., and Chaintreau, A. (2020, January 20\u201324). Seeding Network Influence in Biased Networks and the Benefits of Diversity. Proceedings of the WWW \u201920: The Web Conference 2020, Taipei, Taiwan.","DOI":"10.1145\/3366423.3380275"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Nguyen, L.N., Zhou, K., and Thai, M.T. (2019, January 7\u201310). Influence Maximization at Community Level: A New Challenge with Non-submodularity. Proceedings of the 39th IEEE International Conference on Distributed Computing Systems, ICDCS 2019, Dallas, TX, USA.","DOI":"10.1109\/ICDCS.2019.00040"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Borgs, C., Brautbar, M., Chayes, J.T., and Lucier, B. (2014, January 5\u20137). Maximizing Social Influence in Nearly Optimal Time. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, USA.","DOI":"10.1137\/1.9781611973402.70"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1080\/15427951.2006.10129115","article-title":"Survey: Concentration Inequalities and Martingale Inequalities: A Survey","volume":"3","author":"Chung","year":"2006","journal-title":"Internet Math."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Rossi, R.A., and Ahmed, N.K. (2015). The Network Data Repository with Interactive Graph Analytics and Visualization, AAAI.","DOI":"10.1609\/aaai.v29i1.9277"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/183\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:52:46Z","timestamp":1760176366000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,29]]},"references-count":42,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2020,8]]}},"alternative-id":["a13080183"],"URL":"https:\/\/doi.org\/10.3390\/a13080183","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,29]]}}}