{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T13:51:42Z","timestamp":1770040302022,"version":"3.49.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities of China","doi-asserted-by":"crossref","award":["2020XD-A01-1"],"award-info":[{"award-number":["2020XD-A01-1"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["71871233 and 92046026"],"award-info":[{"award-number":["71871233 and 92046026"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Beijing Natural Science Foundation","award":["1202020"],"award-info":[{"award-number":["1202020"]}]},{"name":"Beijing Natural Science Foundation","award":["1202020 and 9182015"],"award-info":[{"award-number":["1202020 and 9182015"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            Vulnerability assessment\u2014a critical issue for networks\u2014attempts to foresee unexpected destructive events or hostile attacks in the whole system. In this article, we consider a new Markov global connectivity metric\u2014Kemeny constant, and take its derivative called\n            <jats:italic>Markov criticality<\/jats:italic>\n            to identify critical links.\n            <jats:italic>Markov criticality<\/jats:italic>\n            allows us to find links that are most influential on the derivative of Kemeny constant. Thus, we can utilize it to identity a critical link (\n            <jats:italic>i<\/jats:italic>\n            ,\n            <jats:italic>j<\/jats:italic>\n            ) from node\n            <jats:italic>i<\/jats:italic>\n            to node\n            <jats:italic>j<\/jats:italic>\n            , such that removing it leads to a minimization of networks\u2019 global connectivity, i.e., the Kemeny constant. Furthermore, we also define a novel vulnerability index to measure the average speed by which we can disconnect a specified ratio of links with network decomposition. Our method is of high efficiency, which can be easily employed to calculate the Markov criticality in real-life networks. Comprehensive experiments on several synthetic and real-life networks have demonstrated our method\u2019s better performance by comparing it with state-of-the-art baseline approaches.\n          <\/jats:p>","DOI":"10.1145\/3464390","type":"journal-article","created":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T21:25:55Z","timestamp":1626902755000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Measuring the Network Vulnerability Based on Markov Criticality"],"prefix":"10.1145","volume":"16","author":[{"given":"Hui-Jia","family":"Li","sequence":"first","affiliation":[{"name":"School of Science, Beijing University of Posts and Telecommunications, Beijing, China"}]},{"given":"Lin","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Genetics, University of Cambridge, Cambridge, United Kingdom"}]},{"given":"Zhan","family":"Bu","sequence":"additional","affiliation":[{"name":"Jiangsu Provincial Key Laboratory of E-Business, Nanjing University of Finance and Economics, Nanjing, China"}]},{"given":"Jie","family":"Cao","sequence":"additional","affiliation":[{"name":"Jiangsu Provincial Key Laboratory of E-Business, Nanjing University of Finance and Economics, Nanjing, China"}]},{"given":"Yong","family":"Shi","sequence":"additional","affiliation":[{"name":"Fictitious Economics and Data Technology Research Centre, Chinese Academy of Sciences, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2021,7,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms10168"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2017.2772880"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2019.2908269"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSII.2020.2973668"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2019.2960605"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2018.04.028"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978345"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.plrev.2017.11.003"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ab8e5e"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2215882"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"R. Albert H. Jeong and A. Barabasi. 2000. Error and attack tolerance of complex networks. Nature 406 6794 (2000) 378\u2013382.  R. Albert H. Jeong and A. Barabasi. 2000. Error and attack tolerance of complex networks. Nature 406 6794 (2000) 378\u2013382.","DOI":"10.1038\/35019019"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.025103"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/00018730601170527"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2007.09.004"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2170849"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1813"},{"key":"e_1_2_1_18_1","unstructured":"J. G. Kemeny and J. L. Snell. 1976. Finite Markov chains: With a new appendix. Generalization of a Fundamental Matrix. Springer New York.  J. G. Kemeny and J. L. Snell. 1976. Finite Markov chains: With a new appendix. Generalization of a Fundamental Matrix. Springer New York."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.11.005"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJSN.2007.012823"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.08.016"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.02.016"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1031050"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2010.07.016"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1038\/43601"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393 6684 (1998) 440.  D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393 6684 (1998) 440.","DOI":"10.1038\/30918"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"A.-L. Barabasi and R. Albert. 1999. Emergence of scaling in random networks. Science 286 5439 (1999) 509\u2013512.  A.-L. Barabasi and R. Albert. 1999. Emergence of scaling in random networks. Science 286 5439 (1999) 509\u2013512.","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(89)90048-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2010\/10\/P10011"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the National Academy of Sciences.","author":"Girvan M.","year":"2002","unstructured":"M. Girvan and M. E. Newman . 2002. Community structure in social and biological networks . In Proceedings of the National Academy of Sciences. ( 2002 ), 7821\u20137826. M. Girvan and M. E. Newman. 2002. Community structure in social and biological networks. In Proceedings of the National Academy of Sciences. (2002), 7821\u20137826."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42911-3_35"},{"key":"e_1_2_1_34_1","volume-title":"October, 2016.","unstructured":"Chicago network dataset\u2014KONECT , October, 2016. Chicago network dataset\u2014KONECT, October, 2016."},{"key":"e_1_2_1_35_1","first-page":"329","article-title":"Random networks with sublinear preferential attachment: The giant component","volume":"41","author":"S.","year":"2013","unstructured":"S. Dereichet al. 2013 . Random networks with sublinear preferential attachment: The giant component . The Annals of Probability 41 , 1 (2013), 329 \u2013 384 . S. Dereichet al.2013. Random networks with sublinear preferential attachment: The giant component. The Annals of Probability 41, 1 (2013), 329\u2013384.","journal-title":"The Annals of Probability"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3464390","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3464390","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:10Z","timestamp":1750191430000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3464390"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3464390"],"URL":"https:\/\/doi.org\/10.1145\/3464390","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}