{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T07:01:14Z","timestamp":1763535674221,"version":"build-2065373602"},"reference-count":16,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,2,6]],"date-time":"2020-02-06T00:00:00Z","timestamp":1580947200000},"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>Proposed algorithms for calculating the shortest paths such as Dijikstra and Flowd-Warshall\u2019s algorithms are limited to small networks due to computational complexity and cost. We propose an efficient and a more accurate approximation algorithm that is applicable to large scale networks. Our algorithm iteratively constructs levels of hierarchical networks by a node condensing procedure to construct hierarchical graphs until threshold. The shortest paths between nodes in the original network are approximated by considering their corresponding shortest paths in the highest hierarchy. Experiments on real life data show that our algorithm records high efficiency and accuracy compared with other algorithms.<\/jats:p>","DOI":"10.3390\/a13020036","type":"journal-article","created":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T03:13:27Z","timestamp":1581045207000},"page":"36","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Approximation Algorithm for Shortest Path in Large Social Networks"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4011-3803","authenticated-orcid":false,"given":"Dennis Nii Ayeh","family":"Mensah","sequence":"first","affiliation":[{"name":"Big Data Research Center, University of Electronic Science and Technology of China, Chengdu 610051, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9557-7739","authenticated-orcid":false,"given":"Hui","family":"Gao","sequence":"additional","affiliation":[{"name":"Big Data Research Center, University of Electronic Science and Technology of China, Chengdu 610051, China"}]},{"given":"Liang Wei","family":"Yang","sequence":"additional","affiliation":[{"name":"Big Data Research Center, University of Electronic Science and Technology of China, Chengdu 610051, China"}]}],"member":"1968","published-online":{"date-parts":[[2020,2,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Stolfo, S.J., Hershkop, S., Wang, K., Nimeskern, O., and Hu, C.W. (2003, January 2\u20133). Behavior profiling of email. Proceedings of the 1st NSF\/NIJ Conference on Intelligence and Security Informatics, Tucson, AZ, USA.","DOI":"10.1007\/3-540-44853-5_6"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"036112","DOI":"10.1103\/PhysRevE.82.036112","article-title":"Epidemic spreading in evolving networks","volume":"82","author":"Schwarzkopf","year":"2020","journal-title":"Phys. Rev. E"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1980","DOI":"10.3724\/SP.J.1001.2008.01980","article-title":"Networked data mining based on social network visualizations","volume":"19","author":"Yang","year":"2008","journal-title":"J. Software"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1795","DOI":"10.3724\/SP.J.1016.2008.01795","article-title":"Mining key members of crime networks based on personality trait simulation email analysis system","volume":"31","author":"Qiao","year":"2008","journal-title":"Chin. J. Comput."},{"key":"ref_5","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":"1978","journal-title":"Soc. Network"},{"key":"ref_6","unstructured":"Chow, E. (2005, January 9\u201313). A graph search heuristic for shortest distance paths. Proceedings of the Twentieth National Conference on Artificial Intelligence, Pittsburgh, PA, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Rattigan, M., Maier, M.J., and Jensen, D. (2006, January 22\u201323). Using structure indices for efficient approximation of network properties. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA.","DOI":"10.1145\/1150402.1150443"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2279","DOI":"10.3724\/SP.J.1001.2011.03924","article-title":"Shortest Path Approximate Algorithm for Complex Network Analysis","volume":"22","author":"Tang","year":"2011","journal-title":"J. Softw."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Tretyakov, K., Armas-Cervantes, A., Garc\u00eda-Ba\u00f1uelos, L., Vilo, J., and Dumas, M. (2011, January 24\u201328). Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs. Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM \u201911), Glasgow, UK.","DOI":"10.1145\/2063576.2063834"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Maleki, S., Nguyen, D., Lenharth, A., Garzar\u00e1n, M., Padua, D., and Pingali, K. (2016, January 1\u20133). DSMR: A Parallel Algorithm for Single-Source Shortest Path Problem. Proceedings of the 2016 International Conference on Supercomputing (ICS \u201916), Istanbul, Turkey.","DOI":"10.1145\/2925426.2926287"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A Formal Basis for the Heuristic Determination of Minimum Cost Paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_12","unstructured":"McGeoch, C.C. (2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. International Workshop on Experimental and Efficient Algorithms, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1445","DOI":"10.1016\/j.parco.2003.05.004","article-title":"Parallel implementation of geometric shortest path algorithms","volume":"29","author":"Lanthier","year":"2003","journal-title":"Parallel Comput."},{"key":"ref_14","unstructured":"Klimmt, B., and Yang, Y. (2004, January 30\u201331). Introducing the Enron corpus. Proceedings of the First Conference on Email and Anti-Spam, Mountain View, CA, USA."},{"key":"ref_15","unstructured":"Fahmy, S., and Park, K. (2001). Internet topology: Connectivity of IP graphs. Scalability and Traffic Control in IP Networks, SPIE."},{"key":"ref_16","unstructured":"Ley, M., and Reuther, P. (2006, January 17\u201320). Maintaining an Online Bibliographical Database: The Problem of Data Quality. Proceedings of the Extraction et Gestion des Connaissances 2006 (EGC 2006), Lille, France."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/36\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:55:17Z","timestamp":1760172917000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,6]]},"references-count":16,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["a13020036"],"URL":"https:\/\/doi.org\/10.3390\/a13020036","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,2,6]]}}}