Networks and Navigation - Agenda

Working Group Navigation Home Agenda Speakers Travel Information

Networks and Navigation Working Group, August 4-6, 2008, Santa Fe NM

Joint with UCSD's Cooperative Association for Internet Data Analysis

Organizers: Aaron Clauset (SFI), Dmitri Krioukov (CAIDA), kc claffy (CAIDA) and Cris Moore (UNM & SFI)

Sunday, August 3, 2008

7:00pm Welcome dinner (Railyard)

Monday, August 4, 2008

8:30am - 9:00am Breakfast (Santa Fe Institute)

9:00am - 12:00pm Science

Aaron: Hierarchical structure of networks

Hierarchical organization -- where nodes connect together in groups, and these into groups-of-groups, etc. -- is believed to characterize the structure of many real-world networks. Here I'll briefly introduce and summarize a simple generative model of hierarchical structure, an algorithm for inferring it from real-world data, and a few quick applications of the model.

Zoltan: On realizing all simple graphs with a given degree sequence

We give a necessary and sufficient condition for a sequence of nonnegative integers to be realized as a simple graph's degree sequence such that a given (but otherwise arbitrary) set of possible connections from a node are avoided. We then use this result to present a procedure that builds all simple graphs realizing a given degree sequence.

and Zoltan continues:

Graph structure induced bottlenecks in packet-switching networks

We consider the effect of network topology on the optimality of packet routing which we define as g_c, the rate of packet insertion beyond which congestion and queue growth occurs. We show that for any network, there exists an absolute upper bound, expressed in terms of graph vertex separators, for the scaling of g_c with network size N, irrespective of the static routing protocol used. We then derive an estimate to this upper bound for scale-free networks, and introduce a static routing protocol, the ``hub avoidance protocol which, for large packet insertion rates, is superior to the shortest path routing protocol.

12:15pm - 1:00pm Lunch

1:00pm - 5:00pm Science

Aaron: How do networks become navigable?

Networks such as the World Wide Web and the human social network exhibit the property of local navigability, i.e., not only do short paths exist between pairs of nodes, but these paths can be found without resort to global information. Kleinberg's work on the generalized Watts-Strogatz "small world" model gave us one example of what kind of structure can give rise to this local navigability property, but gave no hints about whether a natural mechanism might produce it dynamically. I'll briefly summarize a model of dynamic rewiring on Kleinberg networks, based on the notion of users navigating the existing topology, that self-organizes to the optimally locally navigable structure.

Marian: Efficient navigation in complex networks

Routing information through networks is a universal phenomenon in both natural and manmade complex systems. When each node has full knowledge of the global network connectivity, finding short communication paths is merely a matter of distributed computation. However, in many real networks nodes communicate efficiently even without such global intelligence. Here we show that the peculiar structural characteristics of observable complex networks are exactly the characteristics needed to maximize their communication efficiency without global knowledge. We also describe a general mechanism that explains this connection between network structure and function. This mechanism relies on the presence of a metric space hidden behind an observable network. Our findings suggest that real networks in nature have underlying metric spaces that remain undiscovered. Their discovery would have practical applications ranging from routing in the Internet and searching social networks, to studying information flows in neural, gene regulatory networks, or signaling pathways.

6:30pm Dinner (Santa Cafe)

Tuesday, August 5, 2008

8:30am - 9:00am Breakfast (Santa Fe Institute)

9:00am - 12:00pm Science

Routing in the Internet and Navigability of Scale-Free Networks

The Internet has become an integral part of the ubiquitous information infrastructure of the modern society. But its global scale comes with a price: to route information packets from a given source to a given destination, routers maintain and constantly update an almost full view of the shortest (policy-constrained) paths in the global network topology. This maintenance involves immense computation and information processing overhead, and has recently been widely recognized as one of the biggest scalability problems in the Internet.

In this talk we focus on the question if routing (or targeted information propagation) can be efficient in the Internet and networks alike without any global knowledge of the network topology. In other words we are interested if the Internet and other complex networks are navigable -- we say that a network is navigable if some simple routing strategies based only on local information available to a node are efficient. Such local information can be nodes' coordinates in some hidden metric spaces, and then nodes can route "greedily" by forwarding information to their neighbors closest to the destination in the hidden space. We show that if these spaces are hyperbolic, then networks built upon them naturally acquire scale-free node degree distributions and strong clustering. The topology of these networks are thus surprisingly similar to the topologies of real networks, including the Internet. Moreover, their navigability properties are essentially best possible: almost all greedy routes reach their destinations and follow the shortest paths in the network.

Filipo: @@ (he didn't answer)

12:15pm - 1:00pm Lunch

1:00pm - 5:00pm Science

Fragkiskos: @@ (will ask him)

Srinivas: Evolution of the Internet AS-Level Ecosystem

We present an analytically tractable model of Internet evolution at the level of Autonomous Systems (ASs). We call our model the Multiclass Attraction (MA) model. All of its parameters are measurable based on available Internet topology data. Given the estimated values of these parameters, our analytic results accurately predict a de???nitive set of statistics characterizing the AS topology structure. These statistics are not part of model formulation. The MA model thus closes the ???measure-model-validate-predict??? loop. We develop our model in stages, adding increasing detail characterizing dynamic interaction between Internet ecosystem players. We validate each stage using recent results in Internet topology data analysis. We describe the emergence of ASs, peering links formation, bankruptcies and multihoming. Our model also explains how certain circumstances naturally lead to consolidation of providers over time, unless some exogenous force interferes.

kc: top ten things i've learned about internet infrastructure economics

Wednesday, August 6, 2008

8:30am - 9:00am Breakfast (Santa Fe Institute)

9:00am - 12:00pm Science

open questions: folks add questions to discuss here.

(1) what are the most important things to understand about the Internet as a complex system?

12:15pm - 1:00pm Lunch

1:00pm - 2:00pm Wrap up