{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:06:34Z","timestamp":1760238394872,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2020,8,4]],"date-time":"2020-08-04T00:00:00Z","timestamp":1596499200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Computing shortest-path distances is a fundamental primitive in the context of graph data mining, since this kind of information is essential in a broad range of prominent applications, which include social network analysis, data routing, web search optimization, database design and route planning. Standard algorithms for shortest paths (e.g., Dijkstra\u2019s) do not scale well with the graph size, as they take more than a second or huge memory overheads to answer a single query on the distance for large-scale graph datasets. Hence, they are not suited to mine distances from big graphs, which are becoming the norm in most modern application contexts. Therefore, to achieve faster query answering, smarter and more scalable methods have been designed, the most effective of them based on precomputing and querying a compact representation of the transitive closure of the input graph, called the 2-hop-cover labeling. To use such approaches in realistic time-evolving scenarios, when the managed graph undergoes topological modifications over time, specific dynamic algorithms, carefully updating the labeling as the graph evolves, have been introduced. In fact, recomputing from scratch the 2-hop-cover structure every time the graph changes is not an option, as it induces unsustainable time overheads. While the state-of-the-art dynamic algorithm to update a 2-hop-cover labeling against incremental modifications (insertions of arcs\/vertices, arc weights decreases) offers very fast update times, the only known solution for decremental modifications (deletions of arcs\/vertices, arc weights increases) is still far from being considered practical, as it requires up to tens of seconds of processing per update in several prominent classes of real-world inputs, as experimentation shows. In this paper, we introduce a new dynamic algorithm to update 2-hop-cover labelings against decremental changes. We prove its correctness, formally analyze its worst-case performance, and assess its effectiveness through an experimental evaluation employing both real-world and synthetic inputs. Our results show that it improves, by up to several orders of magnitude, upon average update times of the only existing decremental algorithm, thus representing a step forward towards real-time distance mining in general, massive time-evolving graphs.<\/jats:p>","DOI":"10.3390\/a13080191","type":"journal-article","created":{"date-parts":[[2020,8,5]],"date-time":"2020-08-05T06:02:21Z","timestamp":1596607341000},"page":"191","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7833-9520","authenticated-orcid":false,"given":"Mattia","family":"D\u2019Emidio","sequence":"first","affiliation":[{"name":"Department of Information Engineering, Computer Science and Mathematics, University of L\u2019Aquila, Via Vetoio, I-67100 L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Vieira, M.V., Fonseca, B.M., Damazio, R., Golgher, P.B., Reis, D.C., and Ribeiro-Neto, B.A. (2007, January 6\u201310). Efficient search ranking in social networks. Proceedings of the 16th ACM Conference on Conference on Information and Knowledge Management (CIKM 2007), Lisbon, Portugal.","DOI":"10.1145\/1321440.1321520"},{"key":"ref_2","first-page":"24","article-title":"Hierarchical Hub Labelings for Shortest Paths","volume":"Volume 7501","author":"Abraham","year":"2012","journal-title":"European Symposium on Algorithms"},{"key":"ref_3","first-page":"321","article-title":"Robust Distance Queries on Massive Networks","volume":"Volume 8737","author":"Delling","year":"2014","journal-title":"Proceedings of the 22st European Symposium on Algorithms (ESA 2004)"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.jda.2017.09.001","article-title":"Engineering Graph-Based Models for Dynamic Timetable Information Systems","volume":"46\u201347","author":"Cionini","year":"2017","journal-title":"J. Discret. Algorithms"},{"key":"ref_5","first-page":"21","article-title":"Distance-Based Community Search","volume":"Volume 11376","author":"Catania","year":"2019","journal-title":"Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00778-017-0468-3","article-title":"Reachability Querying: An Independent Permutation Labeling Approach","volume":"27","author":"Wei","year":"2018","journal-title":"VLDB J."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., and Yoshida, Y. (2013, January 22\u201327). Fast exact shortest-path distance queries on large networks by pruned landmark labeling. Proceedings of the International Conference on Management of Data (SIGMOD 2013), New York, NY, USA.","DOI":"10.1145\/2463676.2465315"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., and Yoshida, Y. (2014, January 7\u201311). Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. Proceedings of the 23rd Int. World Wide Web Conference (WWW 2014), Seoul, Korea.","DOI":"10.1145\/2566486.2568007"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Cheng, J., and Yu, J.X. (2009, January 23\u201326). On-line exact shortest distance query processing. Proceedings of the 12th International Conference on Extending Database Technology (EDBT 2009), Saint-Petersburg, Russia.","DOI":"10.1145\/1516360.1516417"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Jiang, M., Fu, A.W.C., and Wong, R.C.W. (June, January 31). Exact Top-k Nearest Keyword Search in Large Networks. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD 2015), Melbourne, Australia.","DOI":"10.1145\/2723372.2749447"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.tcs.2015.02.033","article-title":"Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games","volume":"586","author":"Borassi","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","first-page":"145","article-title":"Subgoal graphs for fast optimal pathfinding","volume":"2","author":"Uras","year":"2015","journal-title":"Game AI Pro"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s10878-018-00374-x","article-title":"Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem","volume":"38","author":"Forlizzi","year":"2019","journal-title":"J. Comb. Optim."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1002\/net.21542","article-title":"Fully dynamic update of arc-flags","volume":"63","author":"Frigioni","year":"2014","journal-title":"Networks"},{"key":"ref_15","first-page":"135","article-title":"Fully Dynamic Maintenance of Arc-Flags in Road Networks","volume":"Volume 7276","author":"Frigioni","year":"2012","journal-title":"Proceedings of the 11th International Symposium on Experimental Algorithms (SEA 2012)"},{"key":"ref_16","first-page":"51","article-title":"Batch Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study","volume":"Volume 5526","author":"Bauer","year":"2009","journal-title":"Proceedings of the 8th International Symposium on Experimental Algorithms (SEA 2009)"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","article-title":"Route Planning in Transportation Networks","volume":"Volume 9220","author":"Bast","year":"2016","journal-title":"Algorithm Engineering"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1338","DOI":"10.1137\/S0097539702403098","article-title":"Reachability and Distance Queries via 2-Hop Labels","volume":"32","author":"Cohen","year":"2003","journal-title":"SIAM J. Comput."},{"key":"ref_19","first-page":"457","article-title":"IS-Label: An Independent-set Based Labeling Scheme for Point-to-point Distance Querying","volume":"6","author":"Fu","year":"2013","journal-title":"Proc. VLDB 2013"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Jin, R., Ruan, N., Xiang, Y., and Lee, V.E. (2012, January 20\u201324). A highway-centric labeling approach for answering distance queries on large sparse graphs. Proceedings of the International Conference on Management of Data (SIGMOD 2012), Scottsdale, AZ, USA.","DOI":"10.1145\/2213836.2213887"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bampis, E. (2015). Public Transit Labeling. Experimental Algorithms, Springer International Publishing.","DOI":"10.1007\/978-3-319-20086-6"},{"key":"ref_22","unstructured":"Qin, Y., Sheng, Q.Z., and Zhang, W.E. (2015, January 23\u201327). SIEF: Efficiently Answering Distance Queries for Failure Prone Graphs. Proceedings of the 18th Int. Conference on Extending Database Technology (EDBT 2015), Brussels, Belgium."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Wei, F. (2010, January 6\u201311). TEDI: Efficient Shortest Path Query Answering on Graphs. Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2010), Indianapolis, IN, USA.","DOI":"10.1145\/1807167.1807181"},{"key":"ref_24","first-page":"376","article-title":"Customizable route planning","volume":"Volume 6630","author":"Delling","year":"2011","journal-title":"Proceedings of the 10th Symposium on Experimental Algorithms (SEA 2011), Kolimpari, Chania"},{"key":"ref_25","first-page":"103","article-title":"Dynamic Public Transit Labeling","volume":"Volume 11619","author":"Misra","year":"2019","journal-title":"Proceedings of the Computational Science and Its Applications (ICCSA 2019), 19th International Conference"},{"key":"ref_26","first-page":"1.6:1","article-title":"Fully Dynamic 2-Hop Cover Labeling","volume":"24","author":"Frigioni","year":"2019","journal-title":"J. Exp. Algorithmics"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-3-319-44543-4_9","article-title":"Distance Queries in Large-Scale Fully Dynamic Complex Networks","volume":"Volume 9843","author":"Frigioni","year":"2016","journal-title":"Proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)"},{"key":"ref_28","unstructured":"Weller, M. (arXiv, 2014). Optimal Hub Labeling is NP-complete, arXiv."},{"key":"ref_29","unstructured":"Cicerone, S., D\u2019Emidio, M., and Frigioni, D. (2018, January 18\u201320). On Mining Distances in Large-Scale Dynamic Graphs. Proceedings of the 19th Italian Conference on Theoretical Computer Science, Urbino, Italy."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Bergamini, E., and Meyerhenke, H. (2015). Fully-dynamic Approximation of Betweenness Centrality. Algorithms-ESA, Springer.","DOI":"10.1007\/978-3-662-48350-3_14"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Hayashi, T., Akiba, T., and Kawarabayashi, K. (2016, January 24\u201328). Fully Dynamic Shortest-Path Distance Query Acceleration on Massive Networks. Proceedings of the 25th ACM International on Conference on Information and Knowledge Management (CIKM 2016), Indianapolis, IN, USA.","DOI":"10.1145\/2983323.2983731"},{"key":"ref_32","first-page":"283","article-title":"Experimental Evaluation of Dynamic Shortest Path Tree Algorithms on Homogeneous Batches","volume":"Volume 8504","author":"Frigioni","year":"2014","journal-title":"Proceedings of the 13th International Symposium on Experimental Algorithms (SEA 2014)"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., and Nanongkai, D. (2018). Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. J. ACM, 65.","DOI":"10.1145\/3218657"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., and Khanna, S. (2019, January 26). A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, USA.","DOI":"10.1145\/3313276.3316320"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1017\/nws.2016.20","article-title":"NetworKit: A tool suite for large-scale complex network analysis","volume":"4","author":"Staudt","year":"2016","journal-title":"Netw. Sci."},{"key":"ref_36","first-page":"259","article-title":"Hub Labels: Theory and Practice","volume":"Volume 8504","author":"Delling","year":"2014","journal-title":"Proceedings of the 13th Symposium on Experimental Algorithms (SEA 2014)"},{"key":"ref_37","unstructured":"Leskovec, J., and Krevl, A. (2020, February 11). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Rossi, R.A., and Ahmed, N.K. (2015, January 25\u201330). The Network Data Repository with Interactive Graph Analytics and Visualization. Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), Austin, TX, USA.","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"ref_39","unstructured":"Kunegis, J. (2020, February 11). KONECT: The Koblenz Network Collection. Available online: http:\/\/konect.uni-koblenz.de\/."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (2001). Random Graphs, Cambridge University Press.","DOI":"10.1017\/CBO9780511814068"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","article-title":"Statistical mechanics of complex network","volume":"74","author":"Albert","year":"2002","journal-title":"Rev. Mod. Phys."},{"key":"ref_42","first-page":"1.5:1.1","article-title":"Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates: New Algorithms and Experiments","volume":"20","author":"Frigioni","year":"2015","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1109\/TPDS.2017.2763951","article-title":"Parallel Algorithm for Incremental Betweenness Centrality on Large Graphs","volume":"29","author":"Jamour","year":"2018","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/191\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:54:22Z","timestamp":1760176462000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,4]]},"references-count":43,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2020,8]]}},"alternative-id":["a13080191"],"URL":"https:\/\/doi.org\/10.3390\/a13080191","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,8,4]]}}}