Announcement

Recent empirical and theoretical work on complex networks has indicated that many are not only small worlds in the sense that short paths exist between most pairs of vertices, but that these paths can often be found using only local information, i.e., can be found without doing the kind of global search that is necessary for unstructured networks like uniformly random graphs.

A deeper understanding of the origin of these locally-navigable structures would (1) clarify the role (if any) that latent metric spaces play in the navigability of networks, and potentially point to novel generative mechanisms based on such spaces, (2) point us toward novel routing algorithms and search protocols for Internet-like topologies, other communication networks, and possibly social networks, (3) shed light on the potentially different behavior of passive versus active spreading on these networks, i.e., diffusion versus search, (4) identify the relationship between navigability and other network properties, e.g., community structure, degree heterogeneity, etc.

Program

The workshop started on Monday August 4th in the morning and concluded by 5 pm on Wednesday August 6th. The agenda included a short presentations from participants as well as significant time for group discussions and interactions. For more information please visit Santa Fe Institute's Networks and Navigation Working Group.

Presentation Slides

• Aaron Clauset (SFI), The Hierarchical Structure of Networks.
• Aaron Clauset (SFI), Navigating with Power Laws
• Dmitri Krioukov (CAIDA), Routing in the Internet and Navigability of Scale-Free Networks
• Fragkiskos Papadopoulos (CAIDA), Application of Hyperbolic Embedding in Overlay Network Construction.
• Fillipo Menczer (Indiana University), Navigating the Web Graph
• Srinivas Shakkottai (Texas A&M University), Demand-Aware Content Distribution

Organizing and program committee:

• Aaron Clauset (SFI)
• Dmitri Krioukov (CAIDA, UCSD)
• kc claffy (CAIDA, UCSD)
• Cris Moore (SFI and UNM)

Open Questions Emerging from the Workshop

1. Scalability of the Internet
   • can we design a routing system that can scale way beyond IPv4 / BGP / today's system? (formally, can we make the number of update messages necessary for global routability convergence grow at most polylogarithmically with network size)
   • what parameters, phenomena, etc. need to be understood before we can design such a new system?
   • what lessons can we extract from web navigation, both in terms of testing ideas on geographic/semantic/lexical routing and as an environment in which to study the evolution of (more or less hidden) metric spaces, i.e. how does the network topology co-evolve with other metric spaces, and what are the implications for efficient routing?
   • can we find a viable (technical) upgrade path from the current system to the new system? and, what technical changes cannot be done without rebooting the whole system?
   • can we design one that can coexist with a competitive market (i.e., allow providers to make money)?
   • are the same "natural monopoly" forces at play in bit-transport that govern electricity and water distribution? under what circumstances should the bit-transport layer need to be architected as a public good? (like roads, etc.) and what would this mean for operation of other layers of the network?
   • how can we make behavior that gives rise to a scalable routing architecture also incentive-compatible with economic interests of the players in the ecosystem? or, how much government oversight / regulation is necessary to make the system stable?
   • how much improvement in the scalability of routing algorithms do we get by imposing restrictions on topological/connectivity between nodes? i.e., the current system is topology-agnostic); is there a practical way, e.g., financial incentives, to implement such requirements?
2. What networks are navigable? (what networks are not?)
   • what does navigability actually mean in certain real networks, especially in the biological ones? (e.g., zoltan's protein folding was a perfect example that navigability can take somewhat unexpected forms: in his case, greedy routing became folding to the local or global minimum-energy state(s). what is navigability in transcription networks or signaling pathways?)
   • what (dynamical) mechanisms make them that way? (what about evolution (in biological sense, i.e., selection), and growth?)
   • what mechanisms keep them that way? (stability)
   • does navigability depend on an implicit/explicit metric space?
   • purely globally-structured navigation is not scalable; purely local (e.g., geographic) navigation is inefficient. how does routing efficiency depend on the degree of intermediate information? e.g., can we improve local routing a lot by including only a little global information? (routing on kleinberg graphs or hyperbolic networks is an intermediate place, because the topology implicitly contains some amount of global information)
   • what's the relationship between routing on hierarchies and routing in hyperbolic spaces?
   • what is the most general formalization of the duality between the hierarchy induced by trees or hyperbolic spaces and the hierarchy of overlapping sets?
   • are hyperbolic spaces merely a good description of current AS topology, or are they being implicitly built and maintained by microscopic (and undiscussed) mechanisms?
   • since we assume that the hidden (latent) metric spaces are induced by node similarities, then can we always define these similarities in real complex networks? perhaps in each network, there is not one but many similarity definitions: how different are the geometries induced by these different definitions, and consequently, how different are the network navigability properties with respect to these different definitions?
   • whatever real network we consider, its hidden metric space is intrinsically finite. what are the techniques to infer the main geometric properties, curvature, in particular, of the continuous spaces that these finite metric spaces come from?
3. What are the appropriate parallels / analogies with the evolution and history of other (comparable) critical infrastructure?
   • examples: airline network, telegraph, and road / rail
   • what lessons can we really pull from these stories that are relevant and useful for understanding both the past and future history of the Internet?