TY - GEN
T1 - Fundamental effects of clustering on the euclidean embedding of Internet hosts
AU - Lee, Sanghwan
AU - Zhang, Zhi Li
AU - Sahu, Sambit
AU - Saha, Debanjan
AU - Srinivasan, Mukund
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=37249085620&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=37249085620&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-72606-7_76
DO - 10.1007/978-3-540-72606-7_76
M3 - Conference contribution
AN - SCOPUS:37249085620
SN - 9783540726050
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 890
EP - 901
BT - NETWORKING 2007 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet - 6th International IFIP-TC6 Networking Conference, Proceedings
A2 - Akyildiz, Ian F.
A2 - Sivakumar, Raghupathy
A2 - Ekici, Eylem
A2 - de Oliveira, Jaudelice Cavalcante
A2 - McNair, Janise
PB - Springer Verlag
T2 - 6th International IFIP-TC6 Networking Conference - NETWORKING 2007 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet
Y2 - 14 May 2007 through 18 May 2007
ER -