article

Hyperbolic embedding of internet graph for distance estimation and overlay construction

Authors:

Tomer TankelAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 16, Issue 1

Pages 25 - 36

https://doi.org/10.1109/TNET.2007.899021

Published: 01 February 2008 Publication History

Abstract

Estimating distances in the Internet has been studied in the recent years due to its ability to improve the performance of many applications, e.g., in the peer-to-peer realm. One scalable approach to estimate distances between nodes is to embed the nodes in some d dimensional geometric space and to use the pair distances in this space as the estimate for the real distances. Several algorithms were suggested in the past to do this in low dimensional Euclidean spaces.

It was noted in recent years that the Internet structure has a highly connected core and long stretched tendrils, and that most of the routing paths between nodes in the tendrils pass through the core. Therefore, we suggest in this work, to embed the Internet distance metric in a hyperbolic space where routes are bent toward the center. We found that if the curvature, that defines the extend of the bending, is selected in the adequate range, the accuracy of Internet distance embedding can be improved.

We demonstrate the strength of our hyperbolic embedding with two applications: selecting the closest server and building an application level multicast tree. For the latter, we present a distributed algorithm for building geometric multicast trees that achieve good trade-offs between delay (stretch) and load (stress). We also present a new efficient centralized embedding algorithm that enables the accurate embedding of short distances, something that have never been done before.

References

[1]

{1} T. S. E. Ng and H. Zhang, "Predicting Internet network distance with coordinates-based approaches," Proc. IEEE, vol. 1, pp. 170-179, Jun. 2002.

[2]

{2} H. Lim, J. C. Hou, and C. H. Choi, "Provisioning of network distance service on the Internet," IEEE/ACM Trans. Netw., vol. 13, no. 3, 2005.

[3]

{3} Tang and M. Crovella, "Virtual landmarks for the Internet," ACM Internet Measurement, Nov. 2003.

[4]

{4} Y. Shavitt and T. Tankel, "Big-Bang simulation for embedding network distances in Euclidean space," IEEE/ACM Trans. Netw., pp. 993-1006, Dec. 2004, an earlier version appeared in IEEE INFOCOM 2003.

[5]

{5} L. Subramanian, S. Agarwal, J. Rexford, and R. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, 2002, pp. 618-627.

[6]

{6} L. Tauro, C. Palmer, G. Siganos, and M. Faloutsos, "A simple conceptual model for the Internet topology," Global Internet, Nov. 2001.

[7]

{7} M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the Internet topology," in ACM SIGCOMM 1999, Boston, MA, Aug./Sep. 1999.

[8]

{8} A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, pp. 509-512, Oct. 15, 1999.

[9]

{9} R. Albert and A.-L. Barabási, "Topology of evolving networks: Local events and universality," Phys. Rev. Lett., pp. 5234-5237, Dec. 2000.

[10]

{10} J. W. Cannon, W. J. Floyd, R. Kenyon, and W. R. Parry, S. Levy, Ed., Hyperbolic Geometry. Cambridge, U.K.: Cambridge Univ. Press, 1997.

[11]

{11} W. P. Thurston, The Geometry and Topology of Three-Manifolds. Princeton, NJ: Princeton Univ. Press, 1997.

[12]

{12} J. W. P. Anderson, Hyperbolic Geometry. New York: Springer, 2001.

[13]

{13} Y. Shavitt and E. Shir, "DIMES: Let the Internet measure itself," ACM SIGCOMM Comput. Commun. Rev., vol. 35, no. 5, Oct. 2005.

[14]

{14} Q. Chen, H. Chang, R. Govindan, S. Jamin, S. J. Shenker, and W. Willinger, "The origin of power laws in Internet topologies revisited," in Proc. IEEE INFOCOM, New York, NY, Apr. 2002, pp. 608-617.

[15]

{15} P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang, "IDMaps: A global Internet host distance estimation service," IEEE/ACM Trans. Netw., Oct. 2001.

[16]

{16} P. Francis, "YOID: Extending the Internet Multicast Architecture," 2000 {Online}. Available: http://www.icir.org/yoid

[17]

{17} S. Pendarakis, S. Shi, D. Verma, and M. Waldvogel, "ALMI: An application level multicast infrastructure," in 3rd USNIX Symp. Internet Techn. Syst. (USITS'01), San Francisco, CA, Mar. 2001, pp. 49-60.

[18]

{18} S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, "A scalable content-addressable network," ACM SIGCOMM, Aug. 2001.

[19]

{19} S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, "Topology-aware overlay construction and server selection," in Proc. IEEE INFOCOM, Jun. 2002, pp. 1190-1199.

[20]

{20} Z. Xu and Z. Zhang, "Building low-maintenance expressways for p2p systems," no. HPL-2002-41, 2001.

[21]

{21} Z. Xu, C. Tang, and Z. Zhang, "Building topology-aware overlays using global soft-state," Proc. ICDCS, May 2003.

[22]

{22} S. Banerjee, B. Bhattacharjee, and C. Kommareddy, "Scalable application layer multicast," ACM SIGCOMM, Aug. 2002.

[23]

{23} S. Jain, R. Mahajan, and D. Wetherall, "A study of performance potential of dht-based overlays," in Usenix Symp. Internet Technologies (USITS), Mar. 2003.

[24]

{24} Y. Shavitt and T. Tankel, "On the curvature of the interent and its usage for overlay construction and distance estimation," in Proc. IEEE INFOCOM , Mar. 2004, pp. 374-384.

Cited By

Touahria Miliani MSadat SHaddad MSeba HAmrouche K(2024)Comparing Hyperbolic Graph Embedding models on Anomaly Detection for CybersecurityProceedings of the 19th International Conference on Availability, Reliability and Security10.1145/3664476.3670445(1-11)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1145/3664476.3670445
Yang MZhou MPan LKing ISingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)κHGCN: Tree-likeness Modeling via Continuous and Discrete Curvature LearningProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599532(2965-2977)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599532
Kobayashi SMatsugu SShiokawa HKlamma RO'Halloran SRokne J(2021)Fast indexing algorithm for efficient kNN queries on complex networksProceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1145/3487351.3489442(343-347)Online publication date: 8-Nov-2021
https://dl.acm.org/doi/10.1145/3487351.3489442
Show More Cited By

Index Terms

Hyperbolic embedding of internet graph for distance estimation and overlay construction

Recommendations

Streaming algorithms for embedding and computing edit distance in the low distance regime
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings x,y lying in the Boolean hypercube. The edit distance between x and y is defined as the minimum number of character insertion, deletion, and bit ...
An Edit Distance Between Graph Correspondences
Graph-Based Representations in Pattern Recognition
Abstract
The Hamming Distance has been largely used to calculate the dissimilarity of a pair of correspondences (also known as labellings or matchings) between two structures (i.e. sets of points, strings or graphs). Although it has the advantage of being ...
On suitability of Euclidean embedding of internet hosts
SIGMETRICS '06/Performance '06: Proceedings of the joint international conference on Measurement and modeling of computer systems

In this paper, we investigate the suitability of embedding Internet hosts into a Euclidean space given their pairwise distances (as measured by round-trip time). Using the classical scaling and matrix perturbation theories, we first establish the (sum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 16, Issue 1

February 2008

245 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2008

Published in TON Volume 16, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
410
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Touahria Miliani MSadat SHaddad MSeba HAmrouche K(2024)Comparing Hyperbolic Graph Embedding models on Anomaly Detection for CybersecurityProceedings of the 19th International Conference on Availability, Reliability and Security10.1145/3664476.3670445(1-11)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1145/3664476.3670445
Yang MZhou MPan LKing ISingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)κHGCN: Tree-likeness Modeling via Continuous and Discrete Curvature LearningProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599532(2965-2977)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599532
Kobayashi SMatsugu SShiokawa HKlamma RO'Halloran SRokne J(2021)Fast indexing algorithm for efficient kNN queries on complex networksProceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1145/3487351.3489442(343-347)Online publication date: 8-Nov-2021
https://dl.acm.org/doi/10.1145/3487351.3489442
Chalopin JChepoi VDragan FDucoffe GMohammed AVaxès Y(2021)Fast Approximation and Exact Computation of Negative Curvature Parameters of GraphsDiscrete & Computational Geometry10.1007/s00454-019-00107-965:3(856-892)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s00454-019-00107-9
Tabaghi PDokmanić IGupta RLiu YShah MRajan STang JPrakash B(2020)Hyperbolic Distance MatricesProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403224(1728-1738)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403224
Saxena CLiu TKing I(2020)A Survey of Graph Curvature and Embedding in Non-Euclidean SpacesNeural Information Processing10.1007/978-3-030-63833-7_11(127-139)Online publication date: 18-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-63833-7_11
Blasius TFriedrich TKrohmer ALaue SKrohmer ALaue SFriedrich TBlasius T(2018)Efficient Embedding of Scale-Free Graphs in the Hyperbolic PlaneIEEE/ACM Transactions on Networking10.1109/TNET.2018.281018626:2(920-933)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2810186
Chepoi VDragan FHabib MVaxès YAlrasheed H(2018)Fast Approximation of Centrality and Distances in Hyperbolic GraphsCombinatorial Optimization and Applications10.1007/978-3-030-04651-4_1(3-18)Online publication date: 15-Dec-2018
https://dl.acm.org/doi/10.1007/978-3-030-04651-4_1
Chepoi VDragan FVaxès YKlein P(2017)Core congestion is inherent in hyperbolic networksProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039835(2264-2279)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039835
Bringmann KKeusch RLengler JMaus YMolla ASchiller ESchwarzmann A(2017)Greedy Routing and the Algorithmic Small-World PhenomenonProceedings of the ACM Symposium on Principles of Distributed Computing10.1145/3087801.3087829(371-380)Online publication date: 25-Jul-2017
https://dl.acm.org/doi/10.1145/3087801.3087829
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents