{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T03:32:16Z","timestamp":1752982336233,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"13","license":[{"start":{"date-parts":[[2022,4,15]],"date-time":"2022-04-15T00:00:00Z","timestamp":1649980800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,15]],"date-time":"2022-04-15T00:00:00Z","timestamp":1649980800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100009567","name":"Budapesti Muszaki \u00e9s Gazdas\u00e1gtudom\u00e1nyi Egyetem","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100009567","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009567","name":"Budapest University of Technology and Economics","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009567","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Complex system theory is increasingly applied to develop control protocols for distributed computational and networking resources. The paper deals with the important subproblem of finding complex connected structures having excellent navigability properties using limited computational resources. Recently, the two-dimensional hyperbolic space turned out to be an efficient geometry for generative models of complex networks. The networks generated using the hyperbolic metric space share their basic structural properties (like small diameter or scale-free degree distribution) with several real networks. In the paper, a new model is proposed for generating navigation trees for complex networks embedded in the two-dimensional hyperbolic plane. The generative model is not based on known hyperbolic network models: the trees are not inferred from the existing links of any network; they are generated from scratch instead and based purely on the hyperbolic coordinates of nodes. We show that these hyperbolic trees have scale-free degree distributions and are present to a large extent both in synthetic hyperbolic complex networks and real ones (Internet autonomous system topology, US flight network) embedded in the hyperbolic plane. As the main result, we show that routing on the generated hyperbolic trees is optimal in terms of total memory usage of forwarding tables.<\/jats:p>","DOI":"10.1007\/s11227-022-04485-5","type":"journal-article","created":{"date-parts":[[2022,4,15]],"date-time":"2022-04-15T10:04:41Z","timestamp":1650017081000},"page":"15250-15268","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Hyperbolic trees for efficient routing computation"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6779-1711","authenticated-orcid":false,"given":"Zal\u00e1n","family":"Heszberger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,15]]},"reference":[{"key":"4485_CR1","unstructured":"Charalambos S, Marios L, Pavlos A, Christos L, Andreas P (2020) Complex systems: a communication networks perspective towards 6g. IEEE Access, pp 1\u20131, 05"},{"key":"4485_CR2","unstructured":"Umar FQM, Xingfu W, Ammar H, Asad K, Adeel A, Teju WF (2020) Torp: load balanced reliable opportunistic routing for asynchronous wireless sensor networks. In: 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pp 1384\u20131389"},{"key":"4485_CR3","unstructured":"Andre B, Claffy KC (2001) Analysis of routeviews bgp data: policy atoms"},{"key":"4485_CR4","unstructured":"Attila K, Andr\u00e1s G, Zal\u00e1n H, J\u00f3zsef B, R\u00e9tv\u00e1ri G (2020) Tight bounds and optimal address spaces. IEEE\/ACM Transactions on Networking, on the Memory Requirement of Hop-by-Hop Routing"},{"key":"4485_CR5","doi-asserted-by":"publisher","first-page":"7651","DOI":"10.1038\/ncomms8651","volume":"6","author":"A Guly\u00e1s","year":"2015","unstructured":"Guly\u00e1s A, B\u00edr\u00f3 JJ, K\u0151r\u00f6si A, R\u00e9tv\u00e1ri G, Krioukov D (2015) Navigable networks as nash equilibria of navigation games. Nat Commun 6:7651","journal-title":"Nat Commun"},{"issue":"6","key":"4485_CR6","doi-asserted-by":"publisher","first-page":"1832","DOI":"10.1109\/TNET.2014.2342155","volume":"23","author":"J Tapolcai","year":"2014","unstructured":"Tapolcai J, B\u00edr\u00f3 J, Babarczi P, Guly\u00e1s A, Heszberger Z, Trossen D (2014) Optimal false-positive-free bloom filter design for scalable multicast forwarding. IEEE\/ACM Trans Netw 23(6):1832\u20131845","journal-title":"IEEE\/ACM Trans Netw"},{"key":"4485_CR7","doi-asserted-by":"crossref","unstructured":"Luca G, Konstantinos P, Ueli P (2012) Random hyperbolic graphs: degree sequence and clustering. In: International Colloquium on Automata, Languages, and Programming, pp 573\u2013585. Springer","DOI":"10.1007\/978-3-642-31585-5_51"},{"issue":"6798","key":"4485_CR8","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1038\/35022643","volume":"406","author":"JM Kleinberg","year":"2000","unstructured":"Kleinberg JM (2000) Navigation in a small world. Nature 406(6798):845\u2013845","journal-title":"Nature"},{"issue":"5571","key":"4485_CR9","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1126\/science.1070120","volume":"296","author":"DJ Watts","year":"2002","unstructured":"Watts DJ, Dodds PS, Newman MEJ (2002) Identity and search in social networks. Science 296(5571):1302","journal-title":"Science"},{"key":"4485_CR10","unstructured":"Guoqi L, Lei D, Gaoxi X, Pei T, Changyun W, Wuhua H, Jing P, Luping S, Eugene SH (2018) Enabling controlling complex networks with local topological information"},{"key":"4485_CR11","doi-asserted-by":"crossref","unstructured":"Kleinberg R (2007) Geographic routing using hyperbolic space. In: Proc of INFOCOM","DOI":"10.1109\/INFCOM.2007.221"},{"issue":"3","key":"4485_CR12","doi-asserted-by":"publisher","first-page":"036106","DOI":"10.1103\/PhysRevE.82.036106","volume":"82","author":"D Krioukov","year":"2010","unstructured":"Krioukov D et al (2010) Hyperbolic geometry of complex networks. Phys Rev E 82(3):036106","journal-title":"Phys Rev E"},{"key":"4485_CR13","unstructured":"Moritz VL, Mustafa SO, S\u00f6ren L, Henning M (2016) Generating Massive Complex Networks with Hyperbolic Geometry Faster in Practice. In: 2016 IEEE High Performance Extreme Computing Conference (HPEC), pp 1\u20136"},{"key":"4485_CR14","unstructured":"M\u00e1rton C, Andr\u00e1s G, Attila K, Bal\u00e1zs S, Gergely B (2012) Poincar\u00e9: A Hyperbolic Data Center Architecture. In: 32nd International Conference on Distributed Computing Systems Workshops (ICDCSW), pp 8\u201316, 06"},{"issue":"8","key":"4485_CR15","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1093\/bioinformatics\/btn079","volume":"24","author":"DJ Higham","year":"2008","unstructured":"Higham DJ, Ra\u0161ajski M, Pr\u017eulj N (2008) Fitting a geometric graph to a protein\u2013protein interaction network. Bioinformatics 24(8):1093\u20131099","journal-title":"Bioinformatics"},{"key":"4485_CR16","unstructured":"Vince L, Ashlesh G, Beichuan Z, Lixia Z, Rodrigo A, Dmitri K, Lan W (2016) An experimental investigation of hyperbolic routing with a smart forwarding plane in ndn. In: 2016 IEEE\/ACM 24th International Symposium on Quality of Service (IWQoS), pp 1\u201310"},{"key":"4485_CR17","unstructured":"Wei P, Tuomas V, Abdelrahman M, Henglin S, Guoying Z (2021) Hyperbolic deep neural networks: a survey. arXiv preprint arXiv:2101.04562"},{"issue":"7417","key":"4485_CR18","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1038\/nature11459","volume":"489","author":"F Papadopoulos","year":"2012","unstructured":"Papadopoulos F, Kitsak M, Serrano M, Bogun\u00e1 M, Krioukov D (2012) Popularity versus similarity in growing networks. Nature 489(7417):537\u2013540","journal-title":"Nature"},{"issue":"1","key":"4485_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-017-01825-5","volume":"8","author":"A Muscoloni","year":"2017","unstructured":"Muscoloni A, Thomas JM, Ciucci S, Bianconi G, Cannistraci CV (2017) Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nat Commun 8(1):1\u201319","journal-title":"Nat Commun"},{"key":"4485_CR20","unstructured":"Bolyai J (1987) APPENDIX - The Theory of Space (with Introduction, Comments and Addenda by F. Karteszi). North-Holland"},{"key":"4485_CR21","volume-title":"Hyperbolic geometry","author":"JW Anderson","year":"2006","unstructured":"Anderson JW (2006) Hyperbolic geometry. Springer, New York"},{"key":"4485_CR22","volume-title":"Handbook of Mathematical Functions","author":"M Abramovitz","year":"1965","unstructured":"Abramovitz M, Stegun I (1965) Handbook of Mathematical Functions. Courier Dover Publication, New York"},{"key":"4485_CR23","doi-asserted-by":"crossref","unstructured":"Papadopoulos F, Krioukov D, Bogua M, Vahdat A (2010) Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In: Proc. of IEEE Infocom, pp 1\u20139. IEEE","DOI":"10.1109\/INFCOM.2010.5462131"},{"issue":"1","key":"4485_CR24","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1038\/nphys1130","volume":"5","author":"M Boguna","year":"2009","unstructured":"Boguna M, Krioukov D, Claffy KC (2009) Navigability of complex networks. Nat Phys 5(1):74\u201380","journal-title":"Nat Phys"},{"issue":"3","key":"4485_CR25","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/3138808.3138811","volume":"47","author":"I Voitalov","year":"2017","unstructured":"Voitalov I, Aldecoa R, Wang L, Krioukov D (2017) Geohyperbolic routing and addressing schemes. ACM SIGCOMM Comput Commun Rev 47(3):11\u201318","journal-title":"ACM SIGCOMM Comput Commun Rev"},{"issue":"6","key":"4485_CR26","first-page":"1","volume":"1","author":"M Boguna","year":"2010","unstructured":"Boguna M, Papadopoulos F, Krioukov D (2010) Sustaining the internet with hyperbolic mapping. Nat Commun 1(6):1\u20138","journal-title":"Nat Commun"},{"issue":"33","key":"4485_CR27","doi-asserted-by":"publisher","first-page":"13316","DOI":"10.1073\/pnas.1300832110","volume":"110","author":"B Corominas-Murtra","year":"2013","unstructured":"Corominas-Murtra B, Go\u00f1i J, Sol\u00e9 RV, Rodr\u00edguez-Caso C (2013) On the origins of hierarchy in complex networks. Proc Natl Acad Sci 110(33):13316\u201313321","journal-title":"Proc Natl Acad Sci"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04485-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-022-04485-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04485-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,8]],"date-time":"2022-08-08T15:13:01Z","timestamp":1659971581000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-022-04485-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,15]]},"references-count":27,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["4485"],"URL":"https:\/\/doi.org\/10.1007\/s11227-022-04485-5","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2022,4,15]]},"assertion":[{"value":"24 March 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}