{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:46:32Z","timestamp":1757313992779,"version":"3.41.2"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T00:00:00Z","timestamp":1672358400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,12,30]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce L-hydra (landmarked hyperbolic distance recovery and approximation), a method for embedding network- or distance-based data into hyperbolic space, which requires only the distance measurements to a few \u2018landmark nodes\u2019. This landmark heuristic makes L-hydra applicable to large-scale graphs and improves upon previously introduced methods. As a mathematical justification, we show that a point configuration in $d$-dimensional hyperbolic space can be perfectly recovered (up to isometry) from distance measurements to just $d+1$ landmarks. We also show that L-hydra solves a two-stage strain-minimization problem, similar to our previous (unlandmarked) method \u2018hydra\u2019. Testing on real network data, we show that L-hydra is an order of magnitude faster than the existing hyperbolic embedding methods and scales linearly in the number of nodes. While the embedding error of L-hydra is higher than the error of the existing methods, we introduce an extension, L-hydra+, which outperforms the existing methods in both runtime and embedding quality.<\/jats:p>","DOI":"10.1093\/comnet\/cnad002","type":"journal-article","created":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T22:02:37Z","timestamp":1675202557000},"source":"Crossref","is-referenced-by-count":1,"title":["Strain-minimizing hyperbolic network embeddings with landmarks"],"prefix":"10.1093","volume":"11","author":[{"given":"Martin","family":"Keller-Ressel","sequence":"first","affiliation":[{"name":"Institute of Mathematical Stochastics , TU Dresden, 01062 Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephanie","family":"Nargang","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Stochastics , TU Dresden, 01062 Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,1,31]]},"reference":[{"key":"2023013112495663300_B1","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1038\/nature11459","article-title":"Popularity versus similarity in growing networks","volume":"489","author":"Papadopoulos,","year":"2012","journal-title":"Nature"},{"key":"2023013112495663300_B2","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1109\/TNET.2013.2294052","article-title":"Network mapping by replaying hyperbolic growth","volume":"23","author":"Papadopoulos,","year":"2015","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"2023013112495663300_B3","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.is.2003.10.002","article-title":"H-MDS: a new approach for interactive visualization with multidimensional scaling in the hyperbolic space","volume":"29","author":"Walter,","year":"2004","journal-title":"Inf. Syst."},{"key":"2023013112495663300_B4","doi-asserted-by":"crossref","first-page":"1615","DOI":"10.1038\/s41467-017-01825-5","article-title":"Machine learning meets complex networks via coalescent embedding in the hyperbolic space","volume":"8","author":"Muscoloni,","year":"2017","journal-title":"Nat. Commun."},{"key":"2023013112495663300_B5","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1038\/nphys1130","article-title":"Navigability of complex networks","volume":"5","author":"Boguna,","year":"2009","journal-title":"Nat. Phys."},{"key":"2023013112495663300_B6","doi-asserted-by":"crossref","first-page":"1902","DOI":"10.1109\/INFCOM.2007.221","article-title":"Geographic routing using hyperbolic space","author":"Kleinberg,","year":"2007","journal-title":"INFOCOM 2007 26th IEEE International Conference on Computer Communications"},{"key":"2023013112495663300_B7","article-title":"An improved hyperbolic embedding algorithm","author":"Chowdhary,","year":"2017","journal-title":"J. Complex Netw."},{"article-title":"Fast and scalable analysis of massive social graphs","year":"2011","author":"Zhao,","key":"2023013112495663300_B8"},{"key":"2023013112495663300_B9","doi-asserted-by":"crossref","first-page":"044315","DOI":"10.1103\/PhysRevE.104.044315","article-title":"Systematic comparison of graph embedding methods in practical tasks","volume":"104","author":"Zhang,","year":"2021","journal-title":"Phys. Rev. E"},{"key":"2023013112495663300_B10","article-title":"Hydra: a method for strain-minimizing hyperbolic embedding of network- and distance-based data","volume":"8","author":"Keller-Ressel,","year":"2020","journal-title":"J. Complex Netw."},{"key":"2023013112495663300_B11","article-title":"Sparse multidimensional scaling using landmark points","author":"De Silva,","year":"2004","journal-title":"Technical Report"},{"key":"2023013112495663300_B12","first-page":"59","article-title":"Hyperbolic geometry","author":"Cannon,","year":"1997","journal-title":"Flavors of Geometry"},{"key":"2023013112495663300_B13","volume":"149","author":"Ratcliffe,","year":"2006","journal-title":"Foundations of Hyperbolic Manifolds"},{"journal-title":"Modern Multidimensional Scaling: Theory and Applications","year":"2005","author":"Borg,","key":"2023013112495663300_B14"},{"key":"2023013112495663300_B15","doi-asserted-by":"crossref","first-page":"1728","DOI":"10.1145\/3394486.3403224","article-title":"Hyperbolic distance matrices","author":"Tabaghi,","year":"2020","journal-title":"Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining"},{"key":"2023013112495663300_B16","first-page":"5:1","article-title":"From graph theory to network science: the natural emergence of hyperbolicity","author":"Friedrich,","year":"2019","journal-title":"Symposium Theoretical Aspects of Computer Science (STACS)"},{"key":"2023013112495663300_B17","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: shortest path","volume":"5","author":"Floyd,","year":"1962","journal-title":"Commun. ACM"},{"article-title":"Neural embeddings of graphs in hyperbolic space","year":"2017","author":"Chamberlain,","key":"2023013112495663300_B18"},{"key":"2023013112495663300_B19","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1145\/279232.279236","article-title":"Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization","volume":"23","author":"Zhu,","year":"1997","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"2023013112495663300_B20","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717907","author":"Laub,","year":"2004","journal-title":"Matrix Analysis For Scientists And Engineers"},{"key":"2023013112495663300_B21","doi-asserted-by":"crossref","DOI":"10.1201\/9781420010572","author":"Hogben,","year":"2006","journal-title":"Handbook of Linear Algebra"},{"key":"2023013112495663300_B22","doi-asserted-by":"crossref","DOI":"10.1145\/2350190.2350193","article-title":"Defining and evaluating network communities based on ground-truth","author":"Yang,","year":"2012","journal-title":"Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics"},{"key":"2023013112495663300_B23","first-page":"1","article-title":"Snap: A general-purpose network analysis and graph-mining library","volume":"8.1","author":"Leskovec,","year":"2016","journal-title":"ACM Transactions on Intelligent Systems and Technology (TIST)"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/11\/1\/cnad002\/48999578\/cnad002.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/11\/1\/cnad002\/48999578\/cnad002.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,4]],"date-time":"2023-12-04T20:56:41Z","timestamp":1701723401000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnad002\/7016783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,30]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12,30]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnad002","relation":{},"ISSN":["2051-1329"],"issn-type":[{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2023,2,1]]},"published":{"date-parts":[[2022,12,30]]},"article-number":"cnad002"}}