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.

Zoltan: 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 optimal 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

Dima: 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: Navigating the Web graph

I will outline some results concerning content, link, and semantic topologies on the Web and their topical locality, ie the likelihood that two nodes close in one space are also close in another. I will then discuss some implications of locality for modeling Web growth, and especially for navigation of the Web graph. Analysis of empirical data suggests that the Web is a friendly place, in that it possesses characteristics that facilitate search. If time allows and people are interested, we can conclude with an overview of two applications of these idea: intelligent Web crawlers and peer networks for distributed collaborative Web search.

12:15pm - 1:00pm Lunch

1:00pm - 5:00pm Science

Fragkiskos: Application of Hyperbolic Embedding in Overlay Network Construction

We first present a network model that grows in a hyperbolic metric space. We show that the resultinggraph instances maintain a power-law degree distribution and strong clustering, and that greedy routing on them performs extremely well. Then, we discuss how a real Peer-to-Peer (P2P) structured overlay network can be built by exploiting this model. Compared to existing architectures this network has many important benefits, such as minimal information exchange among nodes for its maintenance and for successfully locating content. The tradeoff is the need for powerful peers that can act as the high-degree nodes.

Srinivas: Demand-aware Content Distribution

The main source of Internet traffic today is easily duplicable and location-independent content. However all pieces of content are not equally popular, and more popular content could be considered as more valuable. In this talk we primarily focus on one aspect -- utilizing demand awareness in the interest of efficient resource usage. We first develop ideas of how demand is realized in networks, with particular attention to the Bass model for diffusion of innovation in fully connected graphs. We use this model to compare a hybrid of a peer-to-peer and a centralized client-server approach against each method acting alone. We show how awareness of demand can be used to attain a given average delay target with lowest possible utilization of the central server by using the hybrid scheme. We conclude the talk with with a brief perspective on other aspects of utilizing such awareness, such as for efficient caching in CDNs.

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?

(2) how navigable is the Internet? if we removed BGP and OSPF, could a "local" strategy work?

(3) [your question here]

12:15pm - 1:00pm Lunch

1:00pm - 2:00pm Wrap up