{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T01:18:50Z","timestamp":1773883130464,"version":"3.50.1"},"reference-count":32,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T00:00:00Z","timestamp":1614470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2019-104156GB-I00"],"award-info":[{"award-number":["PID2019-104156GB-I00"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper presents a performance comparison of greedy heuristics for a recent variant of the dominating set problem known as the minimum positive influence dominating set (MPIDS) problem. This APX-hard combinatorial optimization problem has applications in social networks. Its aim is to identify a small subset of key influential individuals in order to facilitate the spread of positive influence in the whole network. In this paper, we focus on the development of a fast and effective greedy heuristic for the MPIDS problem, because greedy heuristics are an essential component of more sophisticated metaheuristics. Thus, the development of well-working greedy heuristics supports the development of efficient metaheuristics. Extensive experiments conducted on a wide range of social networks and complex networks confirm the overall superiority of our greedy algorithm over its competitors, especially when the problem size becomes large. Moreover, we compare our algorithm with the integer linear programming solver CPLEX. While the performance of CPLEX is very strong for small and medium-sized networks, it reaches its limits when being applied to the largest networks. However, even in the context of small and medium-sized networks, our greedy algorithm is only 2.53% worse than CPLEX.<\/jats:p>","DOI":"10.3390\/a14030079","type":"journal-article","created":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T20:43:32Z","timestamp":1614545012000},"page":"79","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["An Improved Greedy Heuristic for the Minimum Positive Influence Dominating Set Problem in Social Networks"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5842-2850","authenticated-orcid":false,"given":"Salim","family":"Bouamama","sequence":"first","affiliation":[{"name":"Mechatronics Laboratory (LMETR)\u2014E1764200, Department of Computer Science, Ferhat Abbas University S\u00e9tif 1, S\u00e9tif 19000, Algeria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1736-3559","authenticated-orcid":false,"given":"Christian","family":"Blum","sequence":"additional","affiliation":[{"name":"Artificial Intelligence Research Institute (IIIA-CSIC), Campus of the UAB, 08193 Bellaterra, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cai, S., Hou, W., Wang, Y., Luo, C., and Lin, Q. (2020, January 11\u201317). Two-goal Local Search and Inference Rules for Minimum Dominating Set. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, Yokohama, Japan.","DOI":"10.24963\/ijcai.2020\/204"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Li, J., Potru, R., and Shahrokhi, F. (2020). A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph. Algorithms, 13.","DOI":"10.3390\/a13120339"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Li, R., Hu, S., Liu, H., Li, R., Ouyang, D., and Yin, M. (2019). Multi-Start Local Search Algorithm for the Minimum Connected Dominating Set Problems. Mathematics, 7.","DOI":"10.3390\/math7121173"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Yuan, F., Li, C., Gao, X., Yin, M., and Wang, Y. (2019). A novel hybrid algorithm for minimum total dominating set problem. Mathematics, 7.","DOI":"10.3390\/math7030222"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Li, J., Liu, Y., Lv, S., Lai, Y., and Wang, J. (2020). Improved Memetic Algorithm for Solving the Minimum Weight Vertex Independent Dominating Set. Mathematics, 8.","DOI":"10.3390\/math8071155"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Wang, F., Camacho, E., and Xu, K. (2009). Positive influence dominating set in online social networks. International Conference on Combinatorial Optimization and Applications, Springer.","DOI":"10.1007\/978-3-642-02026-1_29"},{"key":"ref_7","unstructured":"Tankovska, H. (2021, February 22). Global Social Networks Ranked by Number of Users 2021. Available online: https:\/\/www.statista.com\/statistics\/272014\/global-social-networks-ranked-by-number-of-users\/."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1037\/a0032097","article-title":"Alcohol and the social network: Online social networking sites and college students\u2019 perceived drinking norms","volume":"2","author":"Fournier","year":"2013","journal-title":"Psychol. Pop. Media Cult."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Long, C., and Wong, R.C.W. (2011, January 11\u201314). Minimizing seed set for viral marketing. Proceedings of the 2011 11th IEEE International Conference on Data Mining, Vancouver, BC, Canada.","DOI":"10.1109\/ICDM.2011.99"},{"key":"ref_10","first-page":"289","article-title":"Least-cost influence maximization on social networks","volume":"32","author":"Raghavan","year":"2020","journal-title":"Informs J. Comput."},{"key":"ref_11","unstructured":"Wang, G. (2014). Domination Problems in Social Networks. [Ph.D. Thesis, University of Southern Queensland]."},{"key":"ref_12","unstructured":"Rad, A.A., and Benyoucef, M. (2011). Towards detecting influential users in social networks. E-Technologies: Transformation in a Connected World, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.tcs.2009.10.001","article-title":"On positive influence dominating sets in social networks","volume":"412","author":"Wang","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_14","unstructured":"Jungnickel, D. (2005). Graphs, Networks and Algorithms, Springer."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Raei, H., Yazdani, N., and Asadpour, M. (2012, January 26\u201329). A new algorithm for positive influence dominating set in social networks. Proceedings of the 2012 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, Istanbul, Turkey.","DOI":"10.1109\/ASONAM.2012.51"},{"key":"ref_16","first-page":"59","article-title":"An improved algorithm for finding minimum positive influence dominating sets in social networks","volume":"48","author":"Fei","year":"2016","journal-title":"J. South China Norm. Univ."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Pan, J., and Bu, T.M. (May, January 29). A Fast Greedy Algorithm for Finding Minimum Positive Influence Dominating Sets in Social Networks. Proceedings of the IEEE INFOCOM 2019-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Paris, France.","DOI":"10.1109\/INFCOMW.2019.8845129"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/937503.937505","article-title":"Metaheuristics in combinatorial optimization: Overview and conceptual comparison","volume":"35","author":"Blum","year":"2003","journal-title":"ACM Comput. Surv."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2191","DOI":"10.1007\/s10462-017-9605-z","article-title":"Metaheuristic research: A comprehensive survey","volume":"52","author":"Hussain","year":"2019","journal-title":"Artif. Intell. Rev."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.physa.2018.02.119","article-title":"An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks","volume":"500","author":"Lin","year":"2018","journal-title":"Phys. Stat. Mech. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01096763","article-title":"Greedy randomized adaptive search procedures","volume":"6","author":"Feo","year":"1995","journal-title":"J. Glob. Optim."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Lin, G., Luo, J., Xu, H., and Xu, M. (2019). A Hybrid Swarm Intelligence-Based Algorithm for Finding Minimum Positive Influence Dominating Sets. The International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery, Springer.","DOI":"10.1007\/978-3-030-32456-8_55"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.simpat.2015.11.001","article-title":"A hybrid algorithmic model for the minimum weight dominating set problem","volume":"64","author":"Bouamama","year":"2016","journal-title":"Simul. Model. Pract. Theory"},{"key":"ref_24","unstructured":"Biggs, N., Lloyd, E.K., and Wilson, R.J. (1986). Graph Theory, 1736\u20131936, Oxford University Press."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","article-title":"An information flow model for conflict and fission in small groups","volume":"33","author":"Zachary","year":"1977","journal-title":"J. Anthropol. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/s00265-003-0651-y","article-title":"The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations","volume":"54","author":"Lusseau","year":"2003","journal-title":"Behav. Ecol. Sociobiol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1142\/S0219525903001067","article-title":"Community structure in jazz","volume":"6","author":"Gleiser","year":"2003","journal-title":"Adv. Complex Syst."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Rossi, R.A., and Ahmed, N.K. (2015, January 25\u201330). The Network Data Repository with Interactive Graph Analytics and Visualization. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Austin, TX, USA.","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"ref_30","unstructured":"Leskovec, J., and Krevl, A. (2021, February 26). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: https:\/\/snap.stanford.edu\/data\/."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"248","DOI":"10.32614\/RJ-2016-017","article-title":"scmamp: Statistical Comparison of Multiple Algorithms in Multiple Problems","volume":"8","author":"Calvo","year":"2016","journal-title":"R. J."},{"key":"ref_32","first-page":"2677","article-title":"An Extension on \u201cStatistical Comparisons of Classifiers over Multiple Data Sets\u201d for all Pairwise Comparisons","volume":"9","author":"Herrera","year":"2008","journal-title":"J. Mach. Learn. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/79\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:30:34Z","timestamp":1760160634000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/79"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,28]]},"references-count":32,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["a14030079"],"URL":"https:\/\/doi.org\/10.3390\/a14030079","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,28]]}}}