{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T15:15:49Z","timestamp":1772637349591,"version":"3.50.1"},"reference-count":61,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2023,7,4]],"date-time":"2023-07-04T00:00:00Z","timestamp":1688428800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12021001"],"award-info":[{"award-number":["12021001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11991021"],"award-info":[{"award-number":["11991021"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11991020"],"award-info":[{"award-number":["11991020"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971372"],"award-info":[{"award-number":["11971372"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12101048"],"award-info":[{"award-number":["12101048"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12171052"],"award-info":[{"award-number":["12171052"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2021YFA1000300"],"award-info":[{"award-number":["2021YFA1000300"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2021YFA1000301"],"award-info":[{"award-number":["2021YFA1000301"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012236","name":"Beijing Institute of Technology Research Fund Program for Young Scholars","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012236","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the influence maximization problem (IMP) which asks for identifying a limited number of key individuals to spread influence in a network such that the expected number of influenced individuals is maximized. The stochastic maximal covering location problem (SMCLP) formulation is a mixed integer programming formulation that effectively approximates the IMP by the Monte\u2010Carlo sampling. For IMPs with a large\u2010scale network or a large number of samplings, however, the SMCLP formulation cannot be efficiently solved by existing exact algorithms due to its large problem size. In this paper, we attempt to develop presolving methods to reduce the problem size and hence enhance the capability of employing exact algorithms in solving large\u2010scale IMPs. In particular, we propose two effective presolving methods, called strongly connected nodes aggregation (SCNA) and isomorphic nodes aggregation (INA), respectively. The SCNA enables to build a new SMCLP formulation that is potentially much more compact than the existing one, and the INA further eliminates variables and constraints in the SMCLP formulation. A theoretical analysis on two special cases of the IMP is provided to demonstrate the strength of the SCNA and INA in reducing the problem size of the SMCLP formulation. We integrate the proposed presolving methods, SCNA and INA, into the Benders decomposition algorithm, which is recognized as one of the state\u2010of\u2010the\u2010art exact algorithms for solving the IMP. We show that the proposed SCNA and INA provide the possibility to develop a much faster separation algorithm for the Benders cuts. Numerical results demonstrate that with the SCNA and INA, the Benders decomposition algorithm is much more effective in solving the IMP in terms of solution time.<\/jats:p>","DOI":"10.1002\/net.22161","type":"journal-article","created":{"date-parts":[[2023,7,4]],"date-time":"2023-07-04T13:58:22Z","timestamp":1688479102000},"page":"229-253","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient presolving methods for the influence maximization problem"],"prefix":"10.1002","volume":"82","author":[{"given":"Sheng\u2010Jie","family":"Chen","sequence":"first","affiliation":[{"name":"Academy of Mathematics and Systems Science Chinese Academy of Sciences  Beijing China"},{"name":"School of Mathematical Sciences University of Chinese Academy of Sciences  Beijing China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4147-1346","authenticated-orcid":false,"given":"Wei\u2010Kun","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics\/Beijing Key Laboratory on MCAACI Beijing Institute of Technology  Beijing China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6932-9512","authenticated-orcid":false,"given":"Yu\u2010Hong","family":"Dai","sequence":"additional","affiliation":[{"name":"Academy of Mathematics and Systems Science Chinese Academy of Sciences  Beijing China"},{"name":"School of Mathematical Sciences University of Chinese Academy of Sciences  Beijing China"}]},{"given":"Jian\u2010Hua","family":"Yuan","sequence":"additional","affiliation":[{"name":"School of Science Beijing University of Posts and Telecommunications  Beijing China"}]},{"given":"Hou\u2010Shan","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Science Beijing University of Posts and Telecommunications  Beijing China"}]}],"member":"311","published-online":{"date-parts":[[2023,7,4]]},"reference":[{"key":"e_1_2_11_2_1","unstructured":"T.Achterberg.Constraint integer programming Ph.D. thesis Technische Universit\u00e4t Berlin 2007."},{"key":"e_1_2_11_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2018.0857"},{"key":"e_1_2_11_4_1","doi-asserted-by":"publisher","DOI":"10.7763\/IJFCC.2013.V2.161"},{"key":"e_1_2_11_5_1","doi-asserted-by":"crossref","unstructured":"N.Alon I.Gamzu andM.Tennenholtz.Optimizing budget allocation among channels and influencers Proc. 21st Int. Conf. World Wide Web 2012 pp. 381\u2013388.","DOI":"10.1145\/2187836.2187888"},{"key":"e_1_2_11_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00180-7"},{"key":"e_1_2_11_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/psj.12056"},{"key":"e_1_2_11_8_1","unstructured":"R.Bornd\u00f6rfer.Aspects of set packing partitioning and covering Ph.D. thesis Technische Universit\u00e4t Berlin 1998."},{"key":"e_1_2_11_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2021.3091943"},{"key":"e_1_2_11_10_1","doi-asserted-by":"crossref","unstructured":"C.Budak D.Agrawal andA.El Abbadi.Limiting the spread of misinformation in social networks. Proc. 20th Int. Conf. World Wide Web 2011 pp. 665\u2013674.","DOI":"10.1145\/1963405.1963499"},{"key":"e_1_2_11_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20892"},{"key":"e_1_2_11_12_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00527ED1V01Y201308DTM037"},{"key":"e_1_2_11_13_1","doi-asserted-by":"crossref","unstructured":"S.\u2010J.Chen W.\u2010K.Chen Y.\u2010H.Dai J.\u2010H.Yuan andH.\u2010S.Zhang.A companion technical report of \u201cefficient presolving methods for the influence maximization problem\u201d. Tech. Rep. 2023.https:\/\/drive.google.com\/file\/d\/1vmgRBBgwp\u2010zs2rCysBQw\u2010JPcDg3YIXa9\/view?usp=sharing.","DOI":"10.1002\/net.22161"},{"key":"e_1_2_11_14_1","doi-asserted-by":"crossref","unstructured":"W.Chen Y.Wang andS.Yang.Efficient influence maximization in social networks. Proc. the 15th ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining 2009 pp. 199\u2013208.","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_11_15_1","doi-asserted-by":"crossref","unstructured":"W.Chen C.Wang andY.Wang.Scalable influence maximization for prevalent viral marketing in large\u2010scale social networks. Proc. 16th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. 2010a pp. 1029\u20131038.","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_11_16_1","doi-asserted-by":"crossref","unstructured":"W.Chen Y.Yuan andL.Zhang.Scalable influence maximization in social networks under the linear threshold model. Proc. 10th IEEE Int. Conf. Data Min. 2010b pp. 88\u201397.","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_11_17_1","doi-asserted-by":"crossref","unstructured":"S.Cheng H.Shen J.Huang G.Zhang andX.Cheng.StaticGreedy: Solving the scalability\u2010accuracy dilemma in influence maximization. Proc. 22nd ACM Int. Conf. Inform. Knowl. Manage. 2013 pp. 509\u2013518.","DOI":"10.1145\/2505515.2505541"},{"key":"e_1_2_11_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.01.015"},{"key":"e_1_2_11_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026142406234"},{"key":"e_1_2_11_20_1","unstructured":"CPLEX.2022.https:\/\/www.ibm.com\/analytics\/cplex\u2010optimizer."},{"issue":"3","key":"e_1_2_11_21_1","article-title":"Bootstrap percolation in directed and inhomogeneous random graphs","volume":"26","author":"Detering N.","year":"2019","journal-title":"Electron. J. Comb."},{"key":"e_1_2_11_22_1","doi-asserted-by":"crossref","unstructured":"P.DomingosandM.Richardson.Mining the network value of customers. Proc. 7th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. 2001 pp. 57\u201366.","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_11_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.09.012"},{"key":"e_1_2_11_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(02)00628-3"},{"key":"e_1_2_11_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1288-y"},{"key":"e_1_2_11_26_1","doi-asserted-by":"crossref","unstructured":"S.Galhotra A.Arora andS.Roy.Holistic influence maximization: Combining scalability and efficiency with opinion\u2010aware models. Proc. 2016 ACM SIGMOD Int. Conf. Manage. Data 2016 pp. 743\u2013758.","DOI":"10.1145\/2882903.2882929"},{"issue":"1","key":"e_1_2_11_27_1","first-page":"1","article-title":"A note on thresholds and connectivity in random directed graphs","volume":"3","author":"Graham A. J.","year":"2008","journal-title":"Atlantic Electron. J. Math."},{"key":"e_1_2_11_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.07.043"},{"key":"e_1_2_11_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.06.028"},{"issue":"2","key":"e_1_2_11_30_1","first-page":"289","article-title":"Least\u2010cost influence maximization on social networks","volume":"32","author":"G\u00fcnne\u00e7 D.","year":"2020","journal-title":"INFORMS J. Comput."},{"key":"e_1_2_11_31_1","unstructured":"D.Hatano T.Fukunaga andK.\u2010i.Kawarabayashi.Adaptive budget allocation for maximizing influence of advertisements. Proc. 25th Int. Joint Conf. Artif. Intell. 2016 pp. 3600\u20133608."},{"key":"e_1_2_11_32_1","doi-asserted-by":"crossref","unstructured":"X.He G.Song W.Chen andQ.Jiang.Influence blocking maximization in social networks under the competitive linear threshold model. Proc. 2012 SIAM Int. Conf. Data Min. 2012 pp. 463\u2013474.","DOI":"10.1137\/1.9781611972825.40"},{"key":"e_1_2_11_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-012-9136-9"},{"key":"e_1_2_11_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btw275"},{"key":"e_1_2_11_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.omega.2020.102264"},{"key":"e_1_2_11_36_1","unstructured":"M.Kahr M.Leitner andI.Ljubi\u0107.The impact of passive social media users in (competitive) influence maximization.http:\/\/www.optimization\u2010online.org\/DB_FILE\/2022\/01\/8777.pdf 2022."},{"key":"e_1_2_11_37_1","doi-asserted-by":"crossref","unstructured":"D.Kempe J.Kleinberg and\u00c9.Tardos.Maximizing the spread of influence through a social network. Proc. 9th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. 2003 pp. 137\u2013146.","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_11_38_1","doi-asserted-by":"crossref","unstructured":"M.KimuraandK.Saito.Tractable models for information diffusion in social networks. Proc. 10th Eur. Conf. Principle Data Min. Knowl. Discov. 2006 pp. 259\u2013271.","DOI":"10.1007\/11871637_27"},{"key":"e_1_2_11_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499363220"},{"key":"e_1_2_11_40_1","unstructured":"J.LeskovecandJ.Mcauley.Learning to discover social circles in ego networks. Proc. 26th the Annu. Conf. Neural Inform. Process. 2012 pp. 539\u2013547."},{"key":"e_1_2_11_41_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_11_42_1","doi-asserted-by":"crossref","unstructured":"J.Leskovec A.Krause C.Guestrin C.Faloutsos J.VanBriesen andN.Glance.Cost\u2010effective outbreak detection in networks. Proc. 13th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. 2007 pp. 420\u2013429.","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_11_43_1","doi-asserted-by":"crossref","unstructured":"J.Leskovec D.Huttenlocher andJ.Kleinberg.Signed networks in social media. Proc. 28th SIGCHI Conf. Human Factors Comput. Syst. 2010 pp. 1361\u20131370.","DOI":"10.1145\/1753326.1753532"},{"key":"e_1_2_11_44_1","doi-asserted-by":"publisher","DOI":"10.3390\/info8040118"},{"key":"e_1_2_11_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807843"},{"key":"e_1_2_11_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2898413"},{"key":"e_1_2_11_47_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20481"},{"key":"e_1_2_11_48_1","doi-asserted-by":"crossref","unstructured":"C.LongandR. C.\u2010W.Wong.Minimizing seed set for viral marketing. Proc. 11th IEEE Int. Conf. Data Mining. 2011 pp. 427\u2013436.","DOI":"10.1109\/ICDM.2011.99"},{"key":"e_1_2_11_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2013.130610"},{"key":"e_1_2_11_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.21015"},{"key":"e_1_2_11_51_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoo.2019.0012"},{"key":"e_1_2_11_52_1","doi-asserted-by":"crossref","unstructured":"M.RipeanuandI.Foster.Mapping the Gnutella network: Macroscopic properties of large\u2010scale peer\u2010to\u2010peer systems. Proc. 1st Int. Workshop Peer\u2010to\u2010Peer Syst. 2002 pp. 85\u201393.","DOI":"10.1007\/3-540-45748-8_8"},{"key":"e_1_2_11_53_1","doi-asserted-by":"crossref","unstructured":"B.Rozemberczki R.Davies R.Sarkar andC.Sutton.GEMSEC: Graph embedding with self clustering. Proc. 2019 IEEE\/ACM Int. Conf. Adv. Soc. Netw. Anal. Min. 2019 pp. 65\u201372.","DOI":"10.1145\/3341161.3342890"},{"key":"e_1_2_11_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(81)90008-0"},{"key":"e_1_2_11_55_1","unstructured":"D.Sheldon B.Dilkina A.Elmachtoub R.Finseth A.Sabharwal J.Conrad C. P.Gomes D.Shmoys W.Allen O.Amundsen andB.Vaughan.Maximizing the spread of cascades using network design. Proc. 26th Conf. Uncertainty Artif. Intell. 2010 pp. 517\u2013526."},{"key":"e_1_2_11_56_1","unstructured":"T.Soma N.Kakimura K.Inaba andK.\u2010i.Kawarabayashi.Optimal budget allocation: Theoretical guarantee and efficient algorithm. Proc. 31st Int. Conf. Mach. Learn. 2014 pp. 351\u2013359."},{"key":"e_1_2_11_57_1","doi-asserted-by":"crossref","unstructured":"Y.Tang X.Xiao andY.Shi.Influence maximization: Near\u2010optimal time complexity meets practical efficiency. Proc. 2014 ACM SIGMOD Int. Conf. Manage. Data 2014 pp. 75\u201386.","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_11_58_1","doi-asserted-by":"crossref","unstructured":"Y.Tang Y.Shi andX.Xiao.Influence maximization in near\u2010linear time: A martingale approach. Proc. 2015 ACM SIGMOD Int. Conf. Manage. Data 2015 pp. 1539\u20131554.","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_11_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499359828"},{"key":"e_1_2_11_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-017-9958-x"},{"key":"e_1_2_11_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1141576"},{"key":"e_1_2_11_62_1","doi-asserted-by":"crossref","unstructured":"P.Zhang W.Chen X.Sun Y.Wang andJ.Zhang.Minimizing seed set selection with probabilistic coverage guarantee in a social network. Proc. 20th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. 2014 pp. 1306\u20131315.","DOI":"10.1145\/2623330.2623684"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.22161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T12:21:54Z","timestamp":1693830114000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.22161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,4]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["10.1002\/net.22161"],"URL":"https:\/\/doi.org\/10.1002\/net.22161","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,4]]},"assertion":[{"value":"2022-05-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}