{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T04:27:56Z","timestamp":1777696076948,"version":"3.51.4"},"reference-count":43,"publisher":"SAGE Publications","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IDA"],"published-print":{"date-parts":[[2021,9,15]]},"abstract":"<jats:p>We challenge the problem of efficiently identifying critical links that substantially degrade network performance if they do not function under a realistic situation where each link is probabilistically disconnected, e.g., unexpected traffic accident in a road network and unexpected server down in a communication network. To solve this problem, we utilize the bridge detection technique in graph theory and efficiently identify critical links in case the node reachability is taken as the performance measure.To be more precise, we define a set of target nodes and a new measure associated with it, Target-oriented latent link Criticalness Centrality (TCC), which is defined as the marginal loss of the expected number of nodes in the network that can reach, or equivalently can be reached from, one of the target nodes, and compute TCC for each link by use of detected bridges. We apply the proposed method to two real-world networks, one from social network and the other from spatial network, and empirically show that the proposed method has a good scalability with respect to the network size and the links our method identified possess unique properties. They are substantially more critical than those obtained by the others, and no known measures can replace the TCC measure.<\/jats:p>","DOI":"10.3233\/ida-205539","type":"journal-article","created":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T12:04:17Z","timestamp":1631880257000},"page":"1323-1343","source":"Crossref","is-referenced-by-count":2,"title":["Efficient computation of target-oriented link criticalness centrality in uncertain graphs"],"prefix":"10.1177","volume":"25","author":[{"given":"Kazumi","family":"Saito","sequence":"first","affiliation":[{"name":"Faculty of Science, Kanagawa University, Kanagawa, Japan"},{"name":"Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takayasu","family":"Fushimi","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tokyo University of Technology, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kouzou","family":"Ohara","sequence":"additional","affiliation":[{"name":"College of Science and Engineering, Aoyama Gakuin University, Kanagawa, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masahiro","family":"Kimura","sequence":"additional","affiliation":[{"name":"Faculty of Advanced Science and Technology, Ryukoku University, Shiga, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Motoda","sequence":"additional","affiliation":[{"name":"Institute of Scientific and Industrial Research, Osaka University, Osaka, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"issue":"7","key":"10.3233\/IDA-205539_ref1","doi-asserted-by":"crossref","first-page":"8786","DOI":"10.3390\/s130708786","article-title":"Breadth-first search-based single-phase algorithms for bridge detection in wireless sensor networks","volume":"13","author":"Akram","year":"2013","journal-title":"Sensors"},{"issue":"1","key":"10.3233\/IDA-205539_ref2","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1109\/TNSE.2018.2884235","article-title":"Centrality measures for graphons: Accounting for uncertainty in networks","volume":"7","author":"Avella-Medina","year":"2020","journal-title":"IEEE Transactions on Network Science and Engineering"},{"key":"10.3233\/IDA-205539_ref3","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","article-title":"The anatomy of a large-scale hypertextual web search engine","volume":"30","author":"Brin","year":"1998","journal-title":"Computer Networks and ISDN Systems"},{"key":"10.3233\/IDA-205539_ref4","doi-asserted-by":"crossref","unstructured":"V. Chaoji, S. Ranu, R. Rastogi and R. Bhatt, Recommendations to boost content spread in social networks, In Proceedings of the 21th International Conference on World Wide Web (WWW \u201912), 2012, pp. 529\u201353.","DOI":"10.1145\/2187836.2187908"},{"issue":"4","key":"10.3233\/IDA-205539_ref5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2200\/S00527ED1V01Y201308DTM037","article-title":"Information and influence propagation in social networks","volume":"5","author":"Chen","year":"2013","journal-title":"Synthesis Lectures on Data Management"},{"key":"10.3233\/IDA-205539_ref6","doi-asserted-by":"crossref","unstructured":"P. Crescenzi, G. D\u2019angelo, L. Severini and Y. Velaj, Greedily improving our own closeness centrality in a network, ACM Transactions on Knowledge Discovery from Data 11(1) (2016).","DOI":"10.1145\/2953882"},{"issue":"3","key":"10.3233\/IDA-205539_ref7","doi-asserted-by":"crossref","first-page":"036125","DOI":"10.1103\/PhysRevE.73.036125","article-title":"Centrality measures in spatial networks of urban streets","volume":"73","author":"Crucitti","year":"2006","journal-title":"Physical Review E"},{"key":"10.3233\/IDA-205539_ref8","unstructured":"K. Diao, R. Farmani, G. Fu and D. Butler, Toward scalable cut vertex and link detection with applications in wireless ad hoc networks, Int. J. Optim. Civil Eng. 5(3) (2015)."},{"key":"10.3233\/IDA-205539_ref9","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1017\/CBO9780511811395.004","article-title":"Extending centrality","author":"Everett","year":"2005","journal-title":"Models and methods in social network analysis"},{"key":"10.3233\/IDA-205539_ref10","first-page":"1","article-title":"Comparing network-centric and power flow models for the optimal allocation of link capacities in a cascade-resilient power transmission network","volume":"99","author":"Fang","year":"2014","journal-title":"IEEE Systems Journal"},{"key":"10.3233\/IDA-205539_ref11","doi-asserted-by":"crossref","unstructured":"T.L. Frantz, M. Cataldo and K.M. Carley, Robustness of centrality measures under uncertainty: Examining the role of network topology, Computational Mathematical Organization Theory 15(303) (2009).","DOI":"10.1007\/s10588-009-9063-5"},{"key":"10.3233\/IDA-205539_ref12","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0378-8733(78)90021-7","article-title":"Centrality in social networks: Conceptual clarification","volume":"1","author":"Freeman","year":"1979","journal-title":"Social Networks"},{"issue":"864","key":"10.3233\/IDA-205539_ref13","first-page":"1","article-title":"Robust classification of salient links in complex networks","volume":"3","author":"Grady","year":"2012","journal-title":"Nature Communications"},{"key":"10.3233\/IDA-205539_ref14","doi-asserted-by":"crossref","unstructured":"V. Kassiano, A. Gounaris, A.N. Papadopoulos and K. Tsichlas, Mining uncertain graphs: An overview, In Proceedings of the International Workshop on Algorithmic Aspects of Cloud Computing (ALGOCLOUD 2016), 2017, pp. 87\u2013116.","DOI":"10.1007\/978-3-319-57045-7_6"},{"key":"10.3233\/IDA-205539_ref15","doi-asserted-by":"crossref","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","article-title":"Maximizing the spread of influence through a social network","volume":"11","author":"Kempe","year":"2015","journal-title":"Theory of Computation"},{"key":"10.3233\/IDA-205539_ref16","doi-asserted-by":"crossref","unstructured":"A. Khan, Y. Ye and C.L., On Uncertain Graphs, Morgan & Claypool, 2018.","DOI":"10.1007\/978-3-031-01860-2"},{"key":"10.3233\/IDA-205539_ref17","doi-asserted-by":"crossref","first-page":"9:1","DOI":"10.1145\/1514888.1514892","article-title":"Blocking links to minimize contamination spread in a social network","volume":"3","author":"Kimura","year":"2009","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"10.3233\/IDA-205539_ref18","doi-asserted-by":"crossref","unstructured":"B. Klimt and Y. Yang, The enron corpus: A new dataset for email classification research, In Proceedings of the 2004 European Conference on Machine Learning (ECML\u201904), 2004, pp. 217\u2013226.","DOI":"10.1007\/978-3-540-30115-8_22"},{"key":"10.3233\/IDA-205539_ref19","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/978-3-540-31955-9_3","article-title":"Centrality indices","author":"Kosch\u00fctzki","year":"2005","journal-title":"Network Analysis: Methodological Foundations"},{"key":"10.3233\/IDA-205539_ref20","doi-asserted-by":"crossref","unstructured":"D. Li, Z. Xu, S. Li, X. Sun, A. Gupta and K. Sycara, Link recommendation for promoting information diffusion in social network d, In Proceedings of the 22nd International Conference on World Wide Web (WWW \u201913), 2013, pp. 185\u2013186.","DOI":"10.1145\/2487788.2487881"},{"key":"10.3233\/IDA-205539_ref21","doi-asserted-by":"crossref","unstructured":"L. Liu, R. Jin, C. Aggarwal and Y. Shen, Reliable clustering on uncertain graphs, In Proceedings of the 2012 IEEE 12th International Conference on Data Mining (ICDM 2012), 2012, pp. 459\u2013468.","DOI":"10.1109\/ICDM.2012.11"},{"key":"10.3233\/IDA-205539_ref22","doi-asserted-by":"crossref","unstructured":"K. Ohara, K. Saito, M. Kimura and H. Motoda, Accelerating computation of distance based centrality measures for spatial networks, In Proceedings of the 19th International Conference on Discovery Science (DS\u201916), LNCS 9956, 2016, pp. 376\u2013391.","DOI":"10.1007\/978-3-319-46307-0_24"},{"key":"10.3233\/IDA-205539_ref23","doi-asserted-by":"crossref","unstructured":"K. Ohara, K. Saito, M. Kimura and H. Motoda, Maximizing network performance based on group centrality by creating most effective k-links, In Proceedings of the 4th IEEE International Conference on Data Science and Advanced Analytics (DSAA\u201917), 2017, pp. 561\u2013570.","DOI":"10.1109\/DSAA.2017.44"},{"key":"10.3233\/IDA-205539_ref24","doi-asserted-by":"crossref","unstructured":"K. Ohara, K. Saito, M. Kimura and H. Motoda, Critical node identification based on articulation point detection for network with uncertain connectivity, In Proceedings of the Sixth International Symposium on Computing and Networking (CANDAR 2018), 2018, pp. 146\u2013152.","DOI":"10.1109\/CANDAR.2018.00027"},{"issue":"2","key":"10.3233\/IDA-205539_ref25","doi-asserted-by":"crossref","first-page":"201","DOI":"10.15803\/ijnc.9.2_201","article-title":"Critical node identification based on articulation point detection for uncertain network","volume":"9","author":"Ohara","year":"2019","journal-title":"International Journal of Networking and Computing"},{"key":"10.3233\/IDA-205539_ref26","doi-asserted-by":"crossref","unstructured":"E.L. Oliveira, L.S. Portugal and W.P. Junior, Determining critical links in a road network: vulnerability and congestion indicators, Procedia \u2013 Social and Behavioral Sciences 162 (2014), 158\u2013167.","DOI":"10.1016\/j.sbspro.2014.12.196"},{"issue":"3","key":"10.3233\/IDA-205539_ref27","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.socnet.2010.03.006","article-title":"Node centrality in weighted networks: Generalizing degree and shortest paths","volume":"32","author":"Opsahl","year":"2010","journal-title":"Social Networks"},{"key":"10.3233\/IDA-205539_ref28","doi-asserted-by":"crossref","unstructured":"M. Papagelis, Refining social graph connectivity via shortcut edge addition, ACM Transactions on Knowledge Discovery from Data 10(2) (2015).","DOI":"10.1145\/2757281"},{"key":"10.3233\/IDA-205539_ref29","doi-asserted-by":"crossref","unstructured":"N. Parotsidis, E. Pitoura and P. Tsaparas, Selecting shortcuts for a smaller world, In Proceedings of the 2015 SIAM International Conference on Data Mining (SDM 2015), 2015, pp. 28\u201336.","DOI":"10.1137\/1.9781611974010.4"},{"key":"10.3233\/IDA-205539_ref30","doi-asserted-by":"crossref","unstructured":"N. Parotsidis, E. Pitoura and P. Tsaparas, Centrality-aware link recommendations, In Proceedings of of the Ninth ACM International Conference on Web Search and Data Mining (WSDM \u201916), 2016, pp. 503\u2013512.","DOI":"10.1145\/2835776.2835818"},{"key":"10.3233\/IDA-205539_ref31","unstructured":"J.J. Pfeiffer, III. and J. Neville, Methods to determine node centrality and clustering in graphs with uncertain structure, In: Proceedings of the Fifth International Conference on Weblogs and Social Media, L.A. Adamic, R. Baeza-Yates and S. Counts, editors, The AAAI Press, 2011."},{"issue":"1","key":"10.3233\/IDA-205539_ref32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pone.0053095","article-title":"Percolation centrality: Quantifying graph-theoretic impact of nodes during percolation in networks","volume":"8","author":"Piraveenan","year":"2013","journal-title":"PLoS ONE"},{"key":"10.3233\/IDA-205539_ref33","doi-asserted-by":"crossref","unstructured":"M. Potamias, F. Bonchi, A. Gionis and G. Kollios, K-nearest neighbors in uncertain graphs, In Proceedings of the VLDB Endowment (PVLDB), volume\u00a03, 2010, pp. 997\u20131008.","DOI":"10.14778\/1920841.1920967"},{"key":"10.3233\/IDA-205539_ref34","doi-asserted-by":"crossref","unstructured":"K. Saito, M. Kimura, K. Ohara and H. Motoda, Detecting critical links in complex network to maintain information flow\/reachability, In Proceedings of the 14th Pacific Rim International Conference on Artificial Intelligence (PRICAI2016), 2016, pp. 419\u2013432.","DOI":"10.1007\/978-3-319-42911-3_35"},{"key":"10.3233\/IDA-205539_ref35","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1016\/j.ins.2015.03.034","article-title":"Super mediator \u2013 a new centrality measure of node importance for information diffusion over social network","volume":"329","author":"Saito","year":"2016","journal-title":"Information Sciences"},{"key":"10.3233\/IDA-205539_ref36","doi-asserted-by":"crossref","unstructured":"K. Saito, M. Kimura, K. Ohara and H. Motoda, An accurate and efficient method to detect critical links to maintain information flow in network, In Proceedings of the 23th International Symposium on Methodologies for Intelligent Systems (ISMIS2017), 2017, pp. 116\u2013126.","DOI":"10.1007\/978-3-319-60438-1_12"},{"key":"10.3233\/IDA-205539_ref37","doi-asserted-by":"crossref","unstructured":"K. Saito, K. Ohara, M. Kimura and H. Motoda, Critical link identification based on bridge detection for network with uncertain connectivity, In Proceedings of The 24th International Symposium on Methodologies of Intelligent Systems (ISMIS2018), LNAI 11177, 2018, pp. 89\u201399.","DOI":"10.1007\/978-3-030-01851-1_9"},{"issue":"3","key":"10.3233\/IDA-205539_ref38","doi-asserted-by":"crossref","first-page":"26:1","DOI":"10.1145\/3022668","article-title":"Graph manipulations for fast centrality computation","volume":"11","author":"Sariy\u00fcce","year":"2017","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"issue":"3","key":"10.3233\/IDA-205539_ref39","doi-asserted-by":"crossref","first-page":"963","DOI":"10.1109\/TNET.2012.2215882","article-title":"On the discovery of critical links and nodes for assessing network vulnerability","volume":"21","author":"Shen","year":"2013","journal-title":"IEEE\/ACM Transaction on Networking"},{"key":"10.3233\/IDA-205539_ref40","doi-asserted-by":"crossref","unstructured":"I. Stojmenovic, D. Simplot-Ryl, A. Nayak and Y. Velaj, Toward scalable cut vertex and link detection with applications in wireless ad hoc networks, IEEE Network 25(1) (2011).","DOI":"10.1109\/MNET.2011.5687952"},{"key":"10.3233\/IDA-205539_ref41","doi-asserted-by":"crossref","unstructured":"R.E. Tarjan, A note on finding the bridges of a graph, Information Processing Letters 2(6) (1974), 160\u2013161.","DOI":"10.1016\/0020-0190(74)90003-9"},{"key":"10.3233\/IDA-205539_ref42","doi-asserted-by":"crossref","unstructured":"H. Tong, B.A. Prakash, T. Eliassi-Rad, M. Faloutsos and C. Faloutsos, Gelling, and melting, large graphs by edge manipulation, In Proceedings of the 21st ACM international conference on Information and knowledge management (CIKM \u201912), 2012, pp. 245\u2013254.","DOI":"10.1145\/2396761.2396795"},{"key":"10.3233\/IDA-205539_ref43","doi-asserted-by":"crossref","first-page":"61259","DOI":"10.1109\/ACCESS.2019.2915974","article-title":"An efficient approximation of betweenness centrality for uncertain graphs","volume":"7","author":"Wang","year":"2019","journal-title":"IEEE Access"}],"container-title":["Intelligent Data Analysis"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/IDA-205539","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:19:12Z","timestamp":1777454352000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/IDA-205539"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,15]]},"references-count":43,"journal-issue":{"issue":"5"},"URL":"https:\/\/doi.org\/10.3233\/ida-205539","relation":{},"ISSN":["1088-467X","1571-4128"],"issn-type":[{"value":"1088-467X","type":"print"},{"value":"1571-4128","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,15]]}}}