{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T08:11:42Z","timestamp":1769069502020,"version":"3.49.0"},"reference-count":40,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T00:00:00Z","timestamp":1707868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"The Center for Research and Development in Mathematics and Applications (CIDMA)"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Given a social network modelled by a graph, the goal of the influence maximization problem is to find k vertices that maximize the number of active vertices through a process of diffusion. For this diffusion, the linear threshold model is considered. A new algorithm, called ClusterGreedy, is proposed to solve the influence maximization problem. The ClusterGreedy algorithm creates a partition of the original set of nodes into small subsets (the clusters), applies the SimpleGreedy algorithm to the subgraphs induced by each subset of nodes, and obtains the seed set from a combination of the seed set of each cluster by solving an integer linear program. This algorithm is further improved by exploring the submodularity property of the diffusion function. Experimental results show that the ClusterGreedy algorithm provides, on average, higher influence spread and lower running times than the SimpleGreedy algorithm on Watts\u2013Strogatz random graphs.<\/jats:p>","DOI":"10.3390\/info15020112","type":"journal-article","created":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T06:59:26Z","timestamp":1707893966000},"page":"112","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A New Algorithm Framework for the Influence Maximization Problem Using Graph Clustering"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4672-6099","authenticated-orcid":false,"given":"Agostinho","family":"Agra","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Aveiro, 3810-193 Aveiro, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6010-1530","authenticated-orcid":false,"given":"Jose Maria","family":"Samuco","sequence":"additional","affiliation":[{"name":"Center for Research & Development in Mathematics and Applications, University of Aveiro, 3810-193 Aveiro, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2024,2,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Domingos, P., 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_2","doi-asserted-by":"crossref","unstructured":"Richardson, M., and Domingos, P. (2002, January 23\u201326). Mining knowledge-sharing sites for viral marketing. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.","DOI":"10.1145\/775047.775057"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2684","DOI":"10.1007\/s10489-018-01398-w","article-title":"A reversed node ranking approach for influence maximization in social networks","volume":"49","author":"Rui","year":"2019","journal-title":"Appl. Intell."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/s10489-019-01529-x","article-title":"Community-based influence maximization in attributed networks","volume":"50","author":"Huang","year":"2020","journal-title":"Appl. Intell."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1232722.1232727","article-title":"The dynamics of viral marketing","volume":"1","author":"Leskovec","year":"2007","journal-title":"ACM Trans. Web TWEB"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Chen, W., Castillo, C., and Lakshmanan, L.V. (2013). Information and Influence Propagation in Social Networks, Morgan & Claypool Publishers.","DOI":"10.2200\/S00527ED1V01Y201308DTM037"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/s42979-023-02453-1","article-title":"Influence Maximization in Dynamic Networks Using Reinforcement Learning","volume":"5","author":"Haleh","year":"2024","journal-title":"SN Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"119646","DOI":"10.1016\/j.ins.2023.119646","article-title":"Equilibrium of individual concern-critical influence maximization in virtual and real blending network","volume":"648","author":"Ni","year":"2023","journal-title":"Inf. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Arora, A., Galhotra, S., and Ranu, S. (2002, January 14\u201319). Debunking the myths of influence maximization: An in-depth benchmarking study. Proceedings of the 2017 ACM International Conference on Management of Data, New York, NY, USA.","DOI":"10.1145\/3035918.3035924"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/2503792.2503797","article-title":"Information diffusion in online social networks: A survey","volume":"42","author":"Guille","year":"2013","journal-title":"In SIGMOD Rec."},{"key":"ref_11","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","year":"2018","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_12","unstructured":"Sun, J., and Tang, J. (2011). Social Network Data Analytics, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Tejaswi, V., Bindu, P.V., and Thilagam, P.S. (2016, January 21\u201324). Diffusion models and approaches for influence maximization in social networks. Proceedings of the 2016 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Jaipur, India.","DOI":"10.1109\/ICACCI.2016.7732235"},{"key":"ref_14","unstructured":"Zheng, Y. (2018). A Survey: Models, Techniques, and Applications of Influence Maximization Problem, Southern University of Science and Technology."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., and Tardos, E. (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_16","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.ins.2018.07.003","article-title":"Efficient and effective influence maximization in social networks: A hybrid-approach","volume":"465","author":"Ko","year":"2018","journal-title":"Inf. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., and Glance, N. (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_18","first-page":"25","article-title":"Optimizing CELF Agorithm for Influence Maximization Problem in Social Networks","volume":"10","author":"Taherinia","year":"2022","journal-title":"J. Data Min."},{"key":"ref_19","unstructured":"Goyal, A., Lu, W., and Lakshmanan, L.V.S. (April, January 28). Celf++ optimizing the greedy algorithm for influence maximization in social networks. Proceedings of the 20th International Conference Companion on World Wide Web, Hyderabad, India."},{"key":"ref_20","unstructured":"Chen, W., Wang, Y., and Yang, S. (July, January 28). Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France."},{"key":"ref_21","unstructured":"Cheng, S., Shen, H., Huang, J., Zhang, G., and Cheng, X. (November, January 27). Staticgreedy: Solving the scalability-accuracy dilemma in influence maximization. Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, San Francisco, CA, USA."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Goyal, A., Lu, W., and Lakshmanan, L.V.S. (2011, January 11\u201314). Simpath: An efficient algorithm for influence maximization under the linear threshold model. Proceedings of the 2011 IEEE 11th International Conference on Data Mining, Vancouver, BC, Canada.","DOI":"10.1109\/ICDM.2011.132"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1353","DOI":"10.1016\/j.eswa.2014.09.037","article-title":"A fast algorithm for finding most influential people based on the linear threshold model","volume":"42","author":"Rahimkhani","year":"2015","journal-title":"Expert Syst. Appl."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.knosys.2016.09.029","article-title":"COFIM: A community-based framework for influence maximization on large-scale networks","volume":"117","author":"Shang","year":"2017","journal-title":"Knowl. Based Syst."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1188","DOI":"10.1016\/j.ipm.2016.05.006","article-title":"Incim: A community-based algorithm for influence maximization problem under the linear threshold model","volume":"52","author":"Bozorgi","year":"2016","journal-title":"Inf. Process. Manag."},{"key":"ref_26","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_27","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s13278-020-00704-0","article-title":"Mlpr: Efficient influence maximization in linear threshold propagation model using linear programming","volume":"11","author":"Asadpour","year":"2021","journal-title":"Soc. Netw. Anal. Min."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1007\/s40998-019-00178-7","article-title":"Integer linear programming for influence maximization","volume":"43","author":"Baghbani","year":"2019","journal-title":"Iran. J. Sci. Technol. Trans. Electr. Eng."},{"key":"ref_29","first-page":"3383","article-title":"Influence maximization in social networks: An integer programming approach","volume":"26","author":"Keskin","year":"2018","journal-title":"Turk. J. Electr. Eng. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/s10589-017-9958-x","article-title":"A Two-stage Stochastic Programming Approach for Influence Maximization in Social Networks","volume":"69","author":"Wu","year":"2018","journal-title":"Comput. Optim. Appl."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"4017","DOI":"10.1016\/j.tcs.2010.08.021","article-title":"Combinatorial model and bounds for target set selection","volume":"411","author":"Ackerman","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Graph clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Comput. Sci. Rev."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Vlasblom, J., and Wodak, S.J. (2009). Markov Clustering versus Affinity Propagation for the Partitioning of Protein Interaction Graphs. BMC Bioinform., 10.","DOI":"10.1186\/1471-2105-10-99"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1137\/040608635","article-title":"Graph Clustering Via a Discrete Uncoupling Process","volume":"30","year":"2008","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_35","unstructured":"Van Dongen, S. (2000). Graph Clustering by Flow Simulation. [Ph.D. Thesis, Utrecht University]."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1007\/s10958-009-9612-y","article-title":"The linking set problem: A polynomial special case of the multiple-choice knapsack problem","volume":"161","author":"Agra","year":"2009","journal-title":"J. Math. Sci."},{"key":"ref_37","unstructured":"Fairbanks, J., Besan\u00e7on, M., Simon, S., Hoffiman, J., Eubank, N., and Karpinski, S. (2024, February 06). Juliagraphs\/Graphs.jl: An Optimized Graph Package for the Julia Programming Language. Available online: https:\/\/github.com\/JuliaGraphs\/Graphs.Jl."},{"key":"ref_38","unstructured":"Leskovec, J., and Krevl, A. (2024, February 06). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0378-8733(01)00042-9","article-title":"Peer Influence Groups: Identifying Dense Clusters in Large Networks","volume":"23","author":"Moody","year":"2001","journal-title":"Soc. Netw."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.cor.2017.05.006","article-title":"A decomposition approach for the p-median problem on disconnected graphs","volume":"86","author":"Agra","year":"2017","journal-title":"Comput. Oper. Res."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/2\/112\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T13:59:39Z","timestamp":1760104779000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/2\/112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,14]]},"references-count":40,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,2]]}},"alternative-id":["info15020112"],"URL":"https:\/\/doi.org\/10.3390\/info15020112","relation":{},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,14]]}}}