Fundamental effects of clustering on the euclidean embedding of Internet hosts

Sanghwan Lee, Zhi Li Zhang, Sambit Sahu, Debanjan Saha, Mukund Srinivasan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

The network distance estimation schemes based on Euclidean embedding have been shown to provide reasonably good overall accuracy. While some recent studies have revealed that triangle inequality violations (TIVs) inherent in network distances among Internet hosts fundamentally limit their accuracy, these Euclidean embedding methods are nonetheless appealing and useful for many applications due to their simplicity and scalability. In this paper, we investigate why the Euclidean embedding shows reasonable accuracy despite the prevalence of TIVs, focusing in particular on the effect of clustering among Internet hosts. Through mathematical analysis and experiments, we demonstrate that clustering of Internet hosts reduces the effective dimension of the distances, hence lowdimension Euclidean embedding suffices to produce reasonable accuracy. Our findings also provide us with good guidelines as to how to select landmarks to improve the accuracy, and explains why random selection of a large number of landmarks improves the accuracy.

Original languageEnglish (US)
Title of host publicationNETWORKING 2007 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet - 6th International IFIP-TC6 Networking Conference, Proceedings
EditorsIan F. Akyildiz, Raghupathy Sivakumar, Eylem Ekici, Jaudelice Cavalcante de Oliveira, Janise McNair
PublisherSpringer Verlag
Pages890-901
Number of pages12
ISBN (Print)9783540726050
DOIs
StatePublished - 2007
Event6th International IFIP-TC6 Networking Conference - NETWORKING 2007 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet - Atlanta, GA, United States
Duration: May 14 2007May 18 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4479 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th International IFIP-TC6 Networking Conference - NETWORKING 2007 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet
CountryUnited States
CityAtlanta, GA
Period5/14/075/18/07

Fingerprint Dive into the research topics of 'Fundamental effects of clustering on the euclidean embedding of Internet hosts'. Together they form a unique fingerprint.

Cite this