{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T07:29:05Z","timestamp":1768721345829,"version":"3.49.0"},"reference-count":43,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2022,6,1]]},"DOI":"10.1587\/transinf.2021edp7150","type":"journal-article","created":{"date-parts":[[2022,5,31]],"date-time":"2022-05-31T22:13:56Z","timestamp":1654035236000},"page":"1135-1149","source":"Crossref","is-referenced-by-count":3,"title":["Cluster Expansion Method for Critical Node Problem Based on Contraction Mechanism in Sparse Graphs"],"prefix":"10.1587","volume":"E105.D","author":[{"given":"Zheng","family":"WANG","sequence":"first","affiliation":[{"name":"School of Information and Communication Engineering, Hubei University of Economics"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"DI","sequence":"additional","affiliation":[{"name":"School of Information and Communication Engineering, Hubei University of Economics"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] S.P. Borgatti, \u201cIdentifying sets of key players in a network,\u201d IEMC '03 Proc. Managing Technologically Driven Organizations: The Human Side of Innovation and Change, pp.127-131, 2003. 10.1109\/kimas.2003.1245034","DOI":"10.1109\/KIMAS.2003.1245034"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] R. Cohen, S. Havlin, and D. ben-Avraham, \u201cEfficient Immunization Strategies for Computer Networks and Populations,\u201d Physical Review Letters, vol.91, no.24, p.247901, 2003. 10.1103\/physrevlett.91.247901","DOI":"10.1103\/PhysRevLett.91.247901"},{"key":"3","unstructured":"[3] A. Arulselvan, et al., \u201cManaging network risk via critical node identification,\u201d Risk Management in Telecommunication Networks, 2007."},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] A. Kumar, P.K. Gupta, and A. Srivastava, \u201cA review of modern technologies for tackling COVID-19 pandemic,\u201d Diabetes & Metabolic Syndrome: Clinical Research & Reviews, vol.91, no.4, pp.569-573, 2020. 10.1016\/j.dsx.2020.05.008","DOI":"10.1016\/j.dsx.2020.05.008"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] A. Arulselvan, C.W. Commander, and L. Elefteriadou, \u201cDetecting critical nodes in sparse graphs,\u201d Computers & Operations Research, vol.36, no.7, pp.2193-2200, 2008.","DOI":"10.1016\/j.cor.2008.08.016"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] M. Di Summa, A. Grosso, and M. Locatelli, \u201cComplexity of the critical node problem over trees,\u201d Computers & Operations Research, vol.38, no.12, pp.1766-1774, 2011. 10.1016\/j.cor.2011.02.016","DOI":"10.1016\/j.cor.2011.02.016"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] Y. Atay, I. Koc, I. Babaoglu, and H. Kodaz, \u201cCommunity detection from biological and social networks: A comparative analysis of metaheuristic algorithms,\u201d Applied Soft Computing, vol.50, pp.194-211, 2017. 10.1016\/j.asoc.2016.11.025","DOI":"10.1016\/j.asoc.2016.11.025"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] M. Lalou, M.A. Tahraoui, and H. Kheddouci, \u201cThe Critical Node Detection Problem in networks: A survey,\u201d Computer Science Review, vol.28, pp.92-117, 2018. 10.1016\/j.cosrev.2018.02.002","DOI":"10.1016\/j.cosrev.2018.02.002"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[12] B. Addis, M. Di Summa, and A. Grosso, \u201cIdentifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth,\u201d Discrete Appl. Math., vol.161, no.16, pp.2349-2360, 2013. 10.1016\/j.dam.2013.03.021","DOI":"10.1016\/j.dam.2013.03.021"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] M. Lalou and H. Kheddouci, \u201cA polynomial-time algorithm for finding critical nodes in bipartite permutation graphs,\u201d Optim Lett, vol.13, pp.1345-1364, 2019. 10.1007\/s11590-018-1371-6","DOI":"10.1007\/s11590-018-1371-6"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] A. Aliabdi, A. Mohades, and M. Davoodi, \u201cConstrained shortest path problems in bi-colored graphs: a label-setting approach,\u201d GeoInformatica, pp.1-19, 2019.","DOI":"10.1007\/s10707-019-00385-8"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] B. Addis, M. Di Summa, and A. Grosso, \u201cIdentifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth,\u201d Discrete Appl. Math., vol.161, no.16, pp.2349-2360, 2013. 10.1016\/j.dam.2013.03.021","DOI":"10.1016\/j.dam.2013.03.021"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] J.L. Walteros, A. Veremyev, P.M. Pardalos, and E.L. Pasiliao, \u201cDetecting critical node structures on graphs: A mathematical programming approach,\u201d Networks, vol.73, pp.48-88, 2013. 10.1002\/net.21834","DOI":"10.1002\/net.21834"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] D. Granata, G. Steeger, and S. Rebennack, \u201cNetwork interdiction via a Critical Disruption Path: Branch-and-Price algorithms,\u201d Computers & Operations Research, vol.40, no.11, pp.2689-2702, 2013. 10.1016\/j.cor.2013.04.016","DOI":"10.1016\/j.cor.2013.04.016"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] T.N. Dinh, M.T. Thai, and H.T. Nguyen, \u201cBound and exact methods for assessing link vulnerability in complex network,\u201d Journal of Combinatorial Optimization, vol.28, no.1, pp.3-24, 2014. 10.1007\/s10878-014-9742-0","DOI":"10.1007\/s10878-014-9742-0"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] C. Areas, \u201cAn exact algorithm for the two-echelon capacitated vehicle routing problem,\u201d Operations Research, vol.61, no.2, pp.298-314, 2013.","DOI":"10.1287\/opre.1120.1153"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] S.H. Yakhchali, \u201cA path enumeration approach for the analysis of critical activities in fuzzy networks,\u201d Information Sciences, vol.204, no.20, pp.23-35, 2012. 10.1016\/j.ins.2012.01.025","DOI":"10.1016\/j.ins.2012.01.025"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] B. Addis, R. Aringhieri, A. Grosso, and P. Hosteins, \u201cHybrid constructive heuristics for the critical node problem,\u201d Annals of Operations Research, vol.238, no.1-2, pp.637-649, 2016. 10.1007\/s10479-016-2110-y","DOI":"10.1007\/s10479-016-2110-y"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] M. Ventresca and D. Aleman, \u201cA Fast Greedy Algorithm for the Critical Node Detection Problem,\u201d Lecture Notes in Computer Science, pp.603-612, 2014. 10.1007\/978-3-319-12691-3_45","DOI":"10.1007\/978-3-319-12691-3_45"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] T. Ren, Z. Li, Y. Qi, Y. Zhang, S. Liu, Y. Xu, and T. Zhou, \u201cIdentifying vital nodes based on reverse greedy method,\u201d Scientific Reports, vol.10, no.1, 2020. 10.1038\/s41598-020-61722-8","DOI":"10.1038\/s41598-020-61722-8"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] D. Purevsuren and G. Cui, \u201cEfficient heuristic algorithm for identifying critical nodes in planar networks,\u201d Computers & Operations Research, vol.106, pp.143-153, 2019. 10.1016\/j.cor.2019.02.006","DOI":"10.1016\/j.cor.2019.02.006"},{"key":"22","unstructured":"[22] D. Purevsuren, et al., \u201cHybridization of GRASP with exterior path relinking for identifying critical nodes in graphs,\u201d IAENG International Journal of Computer Science, vol.44, no.2, pp.157-165, 2017."},{"key":"23","unstructured":"[23] D. Purevsuren, G. Cui, and N.N.H. Win, \u201cHeuristic algorithm for identifying critical nodes in graphs,\u201d Advances in Computer Science: an International Journal, vol.5, no.3, pp.1-4, 2016."},{"key":"24","doi-asserted-by":"crossref","unstructured":"[24] H. Jhuge and J. Zhang, \u201cTopological centrality and its e-science applications,\u201d Journal of the American Society for Information Science and Technology, vol.61, pp.1824-1841, 2010.","DOI":"10.1002\/asi.21353"},{"key":"25","unstructured":"[25] Z. Wenping, W. Zhikang, and Y. Gui, \u201cA novel algorithm for identifying critical nodes in networks based on local centrality,\u201d Journal of Computer Research and Development, vol.56, no.9, pp.1872-1880, 2019."},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] W.E. Hart, J.E. Smith, and N. Krasnogor, \u201cRecent Advances in Memetic Algorithms,\u201d Springer Berlin Heidelberg, 2005. 10.1007\/3-540-32363-5","DOI":"10.1007\/3-540-32363-5"},{"key":"27","unstructured":"[27] C. Cotta, Handbook of Memetic Algorithms, Springer Berlin Heidelberg, 2012."},{"key":"28","doi-asserted-by":"publisher","unstructured":"[28] Y.-H. Kim, Y. Yoon, and Z.W. Geem, \u201cA comparison study of harmony search and genetic algorithm for the max-cut problem,\u201d Swarm and Evolutionary Computation, vol.44, 2018. 10.1016\/j.swevo.2018.01.004","DOI":"10.1016\/j.swevo.2018.01.004"},{"key":"29","doi-asserted-by":"publisher","unstructured":"[29] P.R. De Oliveira Da Costa, S. Mauceri, P. Carroll, and F. Pallonetto, \u201cA Genetic Algorithm for a Green Vehicle Routing Problem,\u201d Electronic Notes in Discrete Mathematics, vol.64, pp.65-74, 2017. 10.1016\/j.endm.2018.01.008","DOI":"10.1016\/j.endm.2018.01.008"},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] O. Alp and E. Erkut, \u201cAn efficient genetic algorithm for the p-median problem,\u201d Annals of Operations Research, vol.122, pp.21-42, Sept. 2003.","DOI":"10.1023\/A:1026130003508"},{"key":"31","doi-asserted-by":"crossref","unstructured":"[31] C. Moon, J. Kim, and G. Choi, \u201cAn efficient genetic algorithm for the traveling salesman problem with precedence constraints,\u201d European Journal of Operational Research, vol.140, no.3, pp.606-617, 2002.","DOI":"10.1016\/S0377-2217(01)00227-2"},{"key":"32","doi-asserted-by":"publisher","unstructured":"[32] R. Aringhieri, A. Grosso, and P. Hosteins, \u201cA Genetic Algorithm for a class of Critical Node Problems,\u201d Electronic Notes in Discrete Mathematics, vol.52, pp.359-366, 2016. 10.1016\/j.endm.2016.03.047","DOI":"10.1016\/j.endm.2016.03.047"},{"key":"33","doi-asserted-by":"publisher","unstructured":"[33] R. Aringhieri, A. Grosso, P. Hosteins, and R. Scatamacchia, \u201cA general Evolutionary Framework for different classes of Critical Node Problems,\u201d Engineering Applications of Artificial Intelligence, vol.55, pp.128-145, 2016. 10.1016\/j.engappai.2016.06.010","DOI":"10.1016\/j.engappai.2016.06.010"},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] Y. Zhou, J.-K. Hao, Z.-H. Fu, Z. Wang, and X. Lai, \u201cVariable Population Memetic Search: A Case Study on the Critical Node Problem,\u201d IEEE Trans. Evol. Comput., vol.25, no.1, pp.187-200, 2021. 10.1109\/tevc.2020.3011959","DOI":"10.1109\/TEVC.2020.3011959"},{"key":"35","unstructured":"[35] Y. Zhou, H. Jin-Kao, and G. Fred, \u201cMemetic search for identifying critical nodes in sparse graphs,\u201d IEEE Trans. Cybern., pp.1-14, 2017."},{"key":"36","doi-asserted-by":"publisher","unstructured":"[36] R. Aringhieri, A. Grosso, P. Hosteins, and R. Scatamacchia, \u201cLocal search metaheuristics for the critical node problem,\u201d Networks, vol.67, no.3, pp.209-221, 2016. 10.1002\/net.21671","DOI":"10.1002\/net.21671"},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] Y. Zhou and J.-K. Hao, \u201cA fast heuristic algorithm for the critical node problem,\u201d In Proc. Genetic and Evolutionary Computation Conference Companion (GECCO '17), Association for Computing Machinery, New York, NY, USA, pp.121-122, 2017. 10.1145\/3067695.3075993","DOI":"10.1145\/3067695.3075993"},{"key":"38","doi-asserted-by":"publisher","unstructured":"[38] M. Ventresca, \u201cGlobal search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem,\u201d Computers & Operations Research, vol.39, no.11, pp.2763-2775, 2012. 10.1016\/j.cor.2012.02.008","DOI":"10.1016\/j.cor.2012.02.008"},{"key":"39","doi-asserted-by":"publisher","unstructured":"[39] R. Aringhieri, A. Grosso, P. Hosteins, and R. Scatamacchia, \u201cVNS solutions for the Critical Node Problem,\u201d Electronic Notes in Discrete Mathematics, vol.47, pp.37-44, 2015. 10.1016\/j.endm.2014.11.006","DOI":"10.1016\/j.endm.2014.11.006"},{"key":"40","doi-asserted-by":"publisher","unstructured":"[40] M. Ventresca and D. Aleman, \u201cEfficiently identifying critical nodes in large complex networks,\u201d Computational Social Networks, vol.2.1, no.6, 2015. 10.1186\/s40649-015-0010-y","DOI":"10.1186\/s40649-015-0010-y"},{"key":"41","doi-asserted-by":"crossref","unstructured":"[41] L. Chang, W. Li, and W. Zhang, \u201cComputing a near-maximum independent set in linear time by reducing-peeling,\u201d In: Proc. SIGMOD 2017, pp.1181-1196, 2017. 10.1145\/3035918.3035939","DOI":"10.1145\/3035918.3035939"},{"key":"42","doi-asserted-by":"crossref","unstructured":"[42] M. Namazi, C. Sanderson, M.A.H. Newton, M.M.A. Polash, and A. Sattar, \u201cDiversified late acceptance search,\u201d in AI 2018: Advances in Artificial Intelligence-31st Australasian Joint Conference, Wellington, New Zealand, Dec. 11-14, 2018, pp.299-311, 2018. 10.1007\/978-3-030-03991-2_29","DOI":"10.1007\/978-3-030-03991-2_29"},{"key":"43","doi-asserted-by":"crossref","unstructured":"[43] Y. Zhou, Z. Wang, and Y. Jin, \u201cLate acceptance-based heuristic algorithms for identifying critical nodes of weighted graphs,\u201d Knowledge-Based Systems, vol.211, 106562, 2021.","DOI":"10.1016\/j.knosys.2020.106562"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/6\/E105.D_2021EDP7150\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T05:48:26Z","timestamp":1727329706000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/6\/E105.D_2021EDP7150\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,1]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2021edp7150","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,1]]},"article-number":"2021EDP7150"}}