{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T19:07:08Z","timestamp":1778267228427,"version":"3.51.4"},"reference-count":41,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T00:00:00Z","timestamp":1624406400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>This work deals with a generalization of the minimum Target Set Selection (TSS) problem, a key algorithmic question in information diffusion research due to its potential commercial value. Firstly proposed by Kempe et al., the TSS problem is based on a linear threshold diffusion model defined on an input graph with node thresholds, quantifying the hardness to influence each node. The goal is to find the smaller set of items that can influence the whole network according to the diffusion model defined. This study generalizes the TSS problem on networks characterized by many-to-many relationships modeled via hypergraphs. Specifically, we introduce a linear threshold diffusion process on such structures, which evolves as follows. Let H=(V,E) be a hypergraph. At the beginning of the process, the nodes in a given set S\u2286V are influenced. Then, at each iteration, (i) the influenced hyperedges set is augmented by all edges having a sufficiently large number of influenced nodes; (ii) consequently, the set of influenced nodes is enlarged by all the nodes having a sufficiently large number of already influenced hyperedges. The process ends when no new nodes can be influenced. Exploiting this diffusion model, we define the minimum Target Set Selection problem on hypergraphs (TSSH). Being the problem NP-hard (as it generalizes the TSS problem), we introduce four heuristics and provide an extensive evaluation on real-world networks.<\/jats:p>","DOI":"10.3390\/e23070796","type":"journal-article","created":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T11:28:41Z","timestamp":1624447721000},"page":"796","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":44,"title":["Social Influence Maximization in Hypergraphs"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6366-0546","authenticated-orcid":false,"given":"Alessia","family":"Antelmi","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Salerno, 84084 Fisciano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9148-9769","authenticated-orcid":false,"given":"Gennaro","family":"Cordasco","sequence":"additional","affiliation":[{"name":"Dipartimento di Psicologia, Universit\u00e0 degli Studi della Campania \u201cLuigi Vanvitelli\u201d, 81100 Caserta, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmine","family":"Spagnuolo","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Salerno, 84084 Fisciano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Przemys\u0142aw","family":"Szufel","sequence":"additional","affiliation":[{"name":"Decision Analysis and Support Unit, SGH Warsaw School of Economics, 02-554 Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,6,23]]},"reference":[{"key":"ref_1","unstructured":"Wright, J.D. (2015). Sociology of Social Influence. International Encyclopedia of the Social & Behavioral Sciences, Elsevier. [2nd ed.]."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Chen, W., Wang, C., and Wang, Y. (2010, January 24\u201328). Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/1835804.1835934"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"5-es","DOI":"10.1145\/1232722.1232727","article-title":"The Dynamics of Viral Marketing","volume":"1","author":"Leskovec","year":"2007","journal-title":"ACM Trans. Web"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Song, X., Tseng, B.L., Lin, C.Y., and Sun, M.T. (2006, January 6\u201311). Personalized Recommendation Driven by Information Flow. Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, WA, USA.","DOI":"10.1145\/1148170.1148258"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1070","DOI":"10.14778\/2794367.2794376","article-title":"Real-Time Targeted Influence Maximization for Online Advertisements","volume":"8","author":"Li","year":"2015","journal-title":"VLDB Endow."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ye, M., Liu, X., and Lee, W.C. (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, Portland, OR, USA.","DOI":"10.1145\/2348283.2348373"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Agarwal, N., Liu, H., Tang, L., and Yu, P.S. (March, January 28). Identifying the Influential Bloggers in a Community. Proceedings of the 2008 International Conference on Web Search and Data Mining, Phoenix, AZ, USA.","DOI":"10.1145\/1341531.1341559"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Bakshy, E., Hofman, J.M., Mason, W.A., and Watts, D.J. (2011, January 9\u201312). Everyone\u2019s an Influencer: Quantifying Influence on Twitter. Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, Hong Kong.","DOI":"10.1145\/1935826.1935845"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Huang, X., Chen, D., Wang, D., and Ren, T. (2020). Identifying Influencers in Social Networks. Entropy, 22.","DOI":"10.3390\/e22040450"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"2286","DOI":"10.1109\/TPDS.2013.135","article-title":"Fine-Grained Feature-Based Social Influence Evaluation in Online Social Networks","volume":"25","author":"Wang","year":"2014","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.ijpe.2014.12.038","article-title":"Leverage RAF to find domain experts on research social network services: A big data analytics methodology with MapReduce framework","volume":"165","author":"Sun","year":"2015","journal-title":"Int. J. Prod. Econ."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3417","DOI":"10.1007\/s10115-020-01461-4","article-title":"A survey on influence maximization in a social network","volume":"62","author":"Banerjee","year":"2020","journal-title":"Knowl. Inf. Syst."},{"key":"ref_13","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_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2020.05.004","article-title":"Networks beyond pairwise interactions: Structure and dynamics","volume":"874","author":"Battiston","year":"2020","journal-title":"Phys. Rep."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Yoon, S., Song, H., Shin, K., and Yi, Y. (2020, January 20\u201324). How Much and When Do We Need Higher-Order Information in Hypergraphs? A Case Study on Hyperedge Prediction. Proceedings of the Web Conference 2020, Taipei, Taiwan.","DOI":"10.1145\/3366423.3380016"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1109\/TNSE.2018.2873759","article-title":"Social Influence Maximization in Hypergraph in Social Networks","volume":"6","author":"Zhu","year":"2019","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Antelmi, A., Cordasco, G., Spagnuolo, C., and Szufel, P. (2020). Information Diffusion in Complex Networks: A Model Based on Hypergraphs and Its Analysis. Algorithms and Models for the Web Graph, Springer International Publishing.","DOI":"10.1007\/978-3-030-48478-1_3"},{"key":"ref_18","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_19","doi-asserted-by":"crossref","first-page":"1804","DOI":"10.1007\/s00453-017-0390-5","article-title":"Discovering Small Target Sets in Social Networks: A Fast and Effective Algorithm","volume":"80","author":"Cordasco","year":"2018","journal-title":"Algorithmica"},{"key":"ref_20","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_21","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.jnca.2018.01.005","article-title":"Influence analysis in social networks: A survey","volume":"106","author":"Peng","year":"2018","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_22","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_23","doi-asserted-by":"crossref","first-page":"1420","DOI":"10.1086\/226707","article-title":"Threshold models of collective behavior","volume":"83","author":"Granovetter","year":"1978","journal-title":"Am. J. Sociol."},{"key":"ref_24","unstructured":"Schelling, T.C. (1980). Micromotives and Macrobehavior. J. Politics, 42."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1400","DOI":"10.1137\/08073617X","article-title":"On the Approximability of Influence in Social Networks","volume":"23","author":"Chen","year":"2009","journal-title":"SIAM J. Discret. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"4215","DOI":"10.3390\/e15104215","article-title":"Modeling Dynamics of Diffusion Across Heterogeneous Social Networks: News Diffusion in Social Media","volume":"15","author":"Kim","year":"2013","journal-title":"Entropy"},{"key":"ref_27","unstructured":"Li, W., Bai, Q., Zhang, M., and Nguyen, T.D. (2018, January 10\u201315). Modelling Multiple Influences Diffusion in On-Line Social Networks. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, Stockholm, Sweden."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Senevirathna, C., Gunaratne, C., Rand, W., Jayalath, C., and Garibay, I. (2021). Influence Cascades: Entropy-Based Characterization of Behavioral Influence Patterns in Social Media. Entropy, 23.","DOI":"10.3390\/e23020160"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1023\/A:1011122126881","article-title":"Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth","volume":"12","author":"Goldenberg","year":"2001","journal-title":"Mark. Lett."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1156","DOI":"10.1109\/TCSS.2019.2938575","article-title":"Group Influence Maximization Problem in Social Networks","volume":"6","author":"Zhu","year":"2019","journal-title":"IEEE Trans. Comput. Soc. Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2424","DOI":"10.1016\/j.cjph.2018.06.018","article-title":"Study on information transmission model of enterprise informal organizations based on the hypernetwork","volume":"56","author":"Ma","year":"2018","journal-title":"Chin. J. Phys."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Bretto, A. (2013). Hypergraph Theory: An Introduction, Springer International Publishing.","DOI":"10.1007\/978-3-319-00080-0"},{"key":"ref_33","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.","DOI":"10.2200\/S00527ED1V01Y201308DTM037"},{"key":"ref_34","unstructured":"Austin, R. (2021, June 18). Benson Research Data Sets. Available online: https:\/\/www.cs.cornell.edu\/~arb\/data\/."},{"key":"ref_35","unstructured":"Chouder, M.L., Rizzi, S., and Chalal, R. (2017). JSON Datasets for Exploratory OLAP, Elsevier. Mendeley Data."},{"key":"ref_36","unstructured":"Jeffrey, L. (2021, June 18). Game of Thrones Datasets and Visualizations. Available online: https:\/\/github.com\/jeffreylancaster\/game-of-thrones."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Spagnuolo, C., Cordasco, G., Szufel, P., Pralat, P., Scarano, V., Kaminski, B., and Antelmi, A. (2020). Analyzing, Exploring, and Visualizing Complex Networks via Hypergraphs using SimpleHypergraphs.jl. Internet Math.","DOI":"10.24166\/im.01.2020"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Antelmi, A., Cordasco, G., Spagnuolo, C., and Szufel, P. (2021, June 18). Social Influence Maximization in Hypergraphs\u2014Julia Package (GitHub). Available online: https:\/\/github.com\/pszufe\/LTMSim.jl.","DOI":"10.3390\/e23070796"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Antelmi, A., Cordasco, G., Spagnuolo, C., and Szufel, P. (2021). Social Influence Maximization in Hypergraphs\u2014Data Set, CERN.","DOI":"10.3390\/e23070796"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Antelmi, A., Cordasco, G., Kami\u0144ski, B., Pra\u0142at, P., Scarano, V., Spagnuolo, C., and Szufel, P. (2019). SimpleHypergraphs.jl\u2014Novel Software\nFramework for Modelling and Analysis of Hypergraphs. Algorithms and Models for theWeb Graph, Springer.","DOI":"10.1007\/978-3-030-25070-6_9"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Antelmi, A., Cordasco, G., Spagnuolo, C., and Szufel, P. (2021). Social Influence Maximization in Hypergraphs\u2014Julia Package, CERN.","DOI":"10.3390\/e23070796"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/7\/796\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:21:46Z","timestamp":1760163706000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/7\/796"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,23]]},"references-count":41,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2021,7]]}},"alternative-id":["e23070796"],"URL":"https:\/\/doi.org\/10.3390\/e23070796","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,23]]}}}