CAIDA Home
 Current Research | Historical Research  
 www.caida.org > research : topology : : hiddenmetricspaces
    visit     contact     search:
CAIDA: Cooperative Association for Internet Data Analysis
Hidden Metric Spaces

-----summary of contents-----
We find that the maximally navigable networks in this hidden framework have structure remarkably similar to the structure of many complex networks observed in reality. This finding suggests that real networks may be maximally navigable with respect to hidden metric spaces that underlie them but remain unknown. Their discovery will have profound implications for network science theory and practice, including routing and searching in social or communication networks such as the Internet.
-----end summary of contents-----

In this work, we identify a general mechanism that explains routing conductivity, or navigability of real networks based on the concept of similarity between nodes. Specifically, intrinsic charactristics of nodes defne a measure of similarity betwen them, which we abstract as a hidden distance. Taken together, hidden distances define a hidden metric space for a given network. Our recent work shows that these spaces explaini the observed structural peculiarities of several real networks, in particular social and technological ones. here we show that this undying metric structure can be used as a guide for the routing process, leading to efficient communication without global information in arbitrary large networks. Our analysis reveals that, remarkably, real networks satisfy the topological conditions that maximize their navigability within this framework. Therefore, hidden metric spaces offer explanations of two open problems in complex networks science: the communication efficiency networks so often exhibit, and their unique structural characteristics. Our results hold enormous consequences for network science and engineering, opening the possibility, for example, to design efficient routing algorithms in technological networks such as the Internet or peer to peer networks.


Cooperative Association for Internet Data Analysis (CAIDA)
  Last Modified: Mon Feb-25-2008 13:5:27 PDT
  Maintained by: Alex Ma
  Page URL: http://www.caida.org/research/topology/hiddenmetricspaces/index.xml