{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T17:12:50Z","timestamp":1763053970748,"version":"3.45.0"},"reference-count":62,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T00:00:00Z","timestamp":1762992000000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,11,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Influence Maximization (IM) is a pivotal concept in social network analysis, involving the identification of influential nodes within a network to maximize the number of influenced nodes, and has a wide variety of applications that range from viral marketing and information dissemination to public health campaigns. IM can be modeled as a combinatorial optimization problem with a black-box objective function, where the goal is to select $ B $ seed nodes that maximize the expected influence spread. Direct search methods, which do not require gradient information, are well-suited for such problems. Unlike gradient-based approaches, direct search algorithms, in fact, only evaluate the objective function at a suitably chosen set of trial points around the current solution to guide the search process. However, these methods often suffer from scalability issues due to the high cost of function evaluations, especially when applied to combinatorial problems like IM. This work, therefore, proposes the Network-aware Direct Search (NaDS) method, an innovative direct search approach that integrates the network structure into its neighborhood formulation and is used to tackle a mixed-integer programming formulation of the IM problem, the so-called General Information Propagation model. We tested our method on large-scale networks, comparing it to existing state-of-the-art approaches for the IM problem, including direct search methods and various greedy techniques and heuristics. The results of the experiments empirically confirm the assumptions underlying NaDS, demonstrating that exploiting the graph structure of the IM problem in the algorithmic framework can significantly improve its computational efficiency in the considered context.<\/jats:p>","DOI":"10.1093\/comnet\/cnaf042","type":"journal-article","created":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T17:08:34Z","timestamp":1763053714000},"source":"Crossref","is-referenced-by-count":0,"title":["An efficient network-aware direct search method for influence maximization"],"prefix":"10.1093","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-1501-390X","authenticated-orcid":false,"given":"Matteo","family":"Bergamaschi","sequence":"first","affiliation":[{"name":"University of Padua Department of Mathematics \u201cTullio Levi-Civita\u201d, , Via Trieste, 63 , Padova, 35121,","place":["Italy"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2653-8533","authenticated-orcid":false,"given":"Sara","family":"Venturini","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology Senseable City Laboratory, , 77 Massachusetts Avenue , Cambridge, MA, 02139,","place":["United States"]}]},{"given":"Francesco","family":"Tudisco","sequence":"additional","affiliation":[{"name":"The University of Edinburgh School of Mathematics, , Edinburgh, EH93FD,","place":["United Kingdom"]}]},{"given":"Francesco","family":"Rinaldi","sequence":"additional","affiliation":[{"name":"University of Padua Department of Mathematics \u201cTullio Levi-Civita\u201d, , Via Trieste, 63 , Padova, 35121,","place":["Italy"]}]}],"member":"286","published-online":{"date-parts":[[2025,11,13]]},"reference":[{"key":"2025111312082917100_cnaf042-B1","first-page":"519","author":"Bakshy","year":"2012"},{"key":"2025111312082917100_cnaf042-B2","doi-asserted-by":"crossref","first-page":"1194","DOI":"10.1126\/science.1185231","article-title":"The spread of behavior in an online social network experiment","volume":"329","author":"Centola","year":"2010","journal-title":"Science"},{"key":"2025111312082917100_cnaf042-B3","doi-asserted-by":"crossref","first-page":"15095","DOI":"10.1038\/s41598-019-51209-6","article-title":"Systematic comparison between methods for the detection of influential spreaders in complex networks","volume":"9","author":"Erkol","year":"2019","journal-title":"Sci Rep"},{"key":"2025111312082917100_cnaf042-B4","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/j.physa.2006.07.017","article-title":"Theory of rumour spreading in complex social networks","volume":"374","author":"Nekovee","year":"2007","journal-title":"Phys A Stat Mech Appl"},{"key":"2025111312082917100_cnaf042-B5","first-page":"57","author":"Domingos","year":"2001"},{"key":"2025111312082917100_cnaf042-B6","first-page":"420","author":"Leskovec","year":"2007"},{"key":"2025111312082917100_cnaf042-B7","first-page":"665","author":"Budak","year":"2011"},{"key":"2025111312082917100_cnaf042-B8","first-page":"463","author":"He","year":"2012"},{"key":"2025111312082917100_cnaf042-B9","first-page":"671","article-title":"Exploring social influence for recommendation: a generative model approach","author":"Ye","year":"2012"},{"key":"2025111312082917100_cnaf042-B10","first-page":"137","author":"Kempe","year":"2003"},{"key":"2025111312082917100_cnaf042-B11","first-page":"35","author":"Shakarian","year":"2015"},{"key":"2025111312082917100_cnaf042-B12","doi-asserted-by":"crossref","first-page":"034316","DOI":"10.1103\/PhysRevE.106.034316","article-title":"Unifying information propagation models on networks and influence maximization","volume":"106","author":"Tian","year":"2022","journal-title":"Phys Rev E"},{"key":"2025111312082917100_cnaf042-B13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-68913-5","volume-title":"Derivative-Free and Blackbox Optimization","author":"Audet","year":"2017"},{"key":"2025111312082917100_cnaf042-B14","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718768","volume-title":"Introduction to Derivative-Free Optimization","author":"Conn","year":"2009"},{"key":"2025111312082917100_cnaf042-B15","author":"Dzahini","year":"2024"},{"key":"2025111312082917100_cnaf042-B16","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1017\/S0962492919000060","article-title":"Derivative-free optimization methods","volume":"28","author":"Larson","year":"2019","journal-title":"Acta Numer"},{"key":"2025111312082917100_cnaf042-B17","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1038\/s41467-018-07761-2","article-title":"Influence of fake news in Twitter during the 2016 US presidential election","volume":"10","author":"Bovet","year":"2019","journal-title":"Nat Commun"},{"key":"2025111312082917100_cnaf042-B18","first-page":"1029","author":"Chen","year":"2010"},{"key":"2025111312082917100_cnaf042-B19","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"},{"key":"2025111312082917100_cnaf042-B20","doi-asserted-by":"crossref","first-page":"2176","DOI":"10.1137\/080714452","article-title":"Submodularity of influence in social networks: from local to global","volume":"39","author":"Mossel","year":"2010","journal-title":"SIAM J Comput"},{"key":"2025111312082917100_cnaf042-B21","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1103\/RevModPhys.87.925","article-title":"Epidemic processes in complex networks","volume":"87","author":"Pastor-Satorras","year":"2015","journal-title":"Rev Mod Phys"},{"key":"2025111312082917100_cnaf042-B22","first-page":"651","author":"Arora","year":"2017"},{"key":"2025111312082917100_cnaf042-B23","volume-title":"Information and Influence Propagation in Social Networks","author":"Chen","year":"2022"},{"key":"2025111312082917100_cnaf042-B24","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":"Sigmod Rec"},{"key":"2025111312082917100_cnaf042-B25","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":"2025111312082917100_cnaf042-B26","first-page":"177","author":"Sun","year":"2011"},{"key":"2025111312082917100_cnaf042-B27","first-page":"1345","author":"Tejaswi","year":"2016"},{"key":"2025111312082917100_cnaf042-B28","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1201\/b17231-3","article-title":"Recent advances in information diffusion and influence maximization in complex social networks","volume":"37","author":"Zhang","year":"2014","journal-title":"Opportunistic Mobile Soc Netw"},{"key":"2025111312082917100_cnaf042-B29","first-page":"700","article-title":"A contribution to the mathematical theory of epidemics","volume":"115","author":"Kermack","year":"1927","journal-title":"Proc R Soc Lond Ser A Contain Papers Math Phys Charact"},{"key":"2025111312082917100_cnaf042-B30","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1093\/biomet\/60.3.581","article-title":"A model for spatial conflict","volume":"60","author":"Clifford","year":"1973","journal-title":"Biometrika"},{"key":"2025111312082917100_cnaf042-B31","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":"2025111312082917100_cnaf042-B32","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":"2025111312082917100_cnaf042-B33","volume-title":"Micromotives and Macrobehavior","author":"Schelling","year":"2006"},{"key":"2025111312082917100_cnaf042-B34","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1609\/aaai.v26i1.8204","article-title":"Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process","volume":"26","author":"Chen","year":"2021","journal-title":"AAAI"},{"key":"2025111312082917100_cnaf042-B35","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.knosys.2014.02.013","article-title":"CT-IC: continuously activated and time-restricted independent cascade model for viral marketing","volume":"62","author":"Kim","year":"2014","journal-title":"Knowl Based Syst"},{"key":"2025111312082917100_cnaf042-B36","first-page":"439","author":"Liu","year":"2012"},{"key":"2025111312082917100_cnaf042-B37","first-page":"561","author":"Gomez-Rodriguez","year":"2011"},{"key":"2025111312082917100_cnaf042-B38","first-page":"346","article-title":"Dynadiffuse: a dynamic diffusion model for continuous time constrained influence maximization","volume":"29","author":"Xie","year":"2015","journal-title":"Proc AAAI Conf Artif Intell"},{"key":"2025111312082917100_cnaf042-B39","first-page":"199","author":"Chen","year":"2009"},{"key":"2025111312082917100_cnaf042-B40","first-page":"918","author":"Jung","year":"2012"},{"key":"2025111312082917100_cnaf042-B41","first-page":"259","author":"Kimura","year":"2006"},{"key":"2025111312082917100_cnaf042-B42","first-page":"171","author":"Liu","year":"2014"},{"key":"2025111312082917100_cnaf042-B43","first-page":"946","author":"Borgs","year":"2014"},{"key":"2025111312082917100_cnaf042-B44","first-page":"509","author":"Cheng","year":"2013"},{"key":"2025111312082917100_cnaf042-B45","first-page":"629","author":"Cohen","year":"2014"},{"key":"2025111312082917100_cnaf042-B46","first-page":"138","article-title":"Fast and accurate influence maximization on large networks with pruned Monte\u2013Carlo simulations","author":"Ohsaka","year":"2014","journal-title":"Proc AAAI Conf Artif Intell"},{"key":"2025111312082917100_cnaf042-B47","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1038\/nphys1746","article-title":"Identification of influential spreaders in complex networks","volume":"6","author":"Kitsak","year":"2010","journal-title":"Nat Phys"},{"key":"2025111312082917100_cnaf042-B48","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1038\/nature14604","article-title":"Influence maximization in complex networks through optimal percolation","volume":"524","author":"Morone","year":"2015","journal-title":"Nature"},{"key":"2025111312082917100_cnaf042-B49","doi-asserted-by":"crossref","first-page":"054306","DOI":"10.1103\/PhysRevE.107.054306","article-title":"Influence maximization: divide and conquer","volume":"107","author":"Patwardhan","year":"2023","journal-title":"Phys Rev E"},{"key":"2025111312082917100_cnaf042-B50","doi-asserted-by":"crossref","first-page":"cnz029","DOI":"10.1093\/comnet\/cnz029","article-title":"Influencer identification in dynamical complex systems","volume":"8","author":"Pei","year":"2020","journal-title":"J Complex Netw"},{"key":"2025111312082917100_cnaf042-B51","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF02289026","article-title":"A new status index derived from sociometric analysis","volume":"18","author":"Katz","year":"1953","journal-title":"Psychometrika"},{"key":"2025111312082917100_cnaf042-B52","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1217299.1217301","article-title":"Graph evolution: densification and shrinking diameters","volume":"1","author":"Leskovec","year":"2007","journal-title":"ACM Trans Knowl Discov Data"},{"key":"2025111312082917100_cnaf042-B53","first-page":"1325","author":"Rozemberczki","year":"2020"},{"key":"2025111312082917100_cnaf042-B54","author":"Leskovec","year":"2008"},{"key":"2025111312082917100_cnaf042-B55","first-page":"217","author":"Klimt","year":"2004"},{"key":"2025111312082917100_cnaf042-B56","first-page":"539","author":"McAuley","year":"2012"},{"key":"2025111312082917100_cnaf042-B57","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1103\/PhysRevE.78.046110","article-title":"Benchmark graphs for testing community detection algorithms","volume":"78","author":"Lancichinetti","year":"2008","journal-title":"Phys Rev E"},{"key":"2025111312082917100_cnaf042-B58","first-page":"11","author":"Hagberg","year":"2008"},{"key":"2025111312082917100_cnaf042-B59","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/s41586-020-2649-2","article-title":"Others Array programming with NumPy","volume":"585","author":"Harris","year":"2020","journal-title":"Nature"},{"key":"2025111312082917100_cnaf042-B60","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1038\/s41592-019-0686-2","article-title":"1.0: fundamental algorithms for scientific computing in Python","volume":"17","author":"Virtanen","year":"2020","journal-title":"Nat Methods"},{"key":"2025111312082917100_cnaf042-B61","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/MCSE.2007.55","article-title":"Matplotlib: a 2D Graphics Environment","volume":"9","author":"Hunter","year":"2007","journal-title":"Comput Sci Eng"},{"key":"2025111312082917100_cnaf042-B62","author":"Leskovec","year":"2014"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/13\/6\/cnaf042\/65284922\/cnaf042.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/13\/6\/cnaf042\/65284922\/cnaf042.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T17:08:40Z","timestamp":1763053720000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnaf042\/8322444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,4]]},"references-count":62,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,11,4]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnaf042","relation":{},"ISSN":["2051-1329"],"issn-type":[{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,12]]},"published":{"date-parts":[[2025,11,4]]},"article-number":"cnaf042"}}