Networks and Navigation - Agenda: Difference between revisions
From Santa Fe Institute Events Wiki
No edit summary |
|||
| Line 19: | Line 19: | ||
:: 9:00am - 12:00pm '''Science''' | :: 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''' | :: 12:15pm - 1:00pm '''Lunch''' | ||
:: 1:00pm - 5:00pm '''Science''' | :: 1:00pm - 5:00pm '''Science''' | ||
Aaron: How do networks become navigable? | |||
Abstract: 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) | :: 6:30pm '''Dinner''' (Santa Cafe) | ||
Revision as of 05:25, 24 July 2008
| Working Group Navigation |
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?
Abstract: 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
- 12:15pm - 1:00pm Lunch
- 1:00pm - 5:00pm Science
Wednesday, August 6, 2008
- 8:30am - 9:00am Breakfast (Santa Fe Institute)
- 9:00am - 12:00pm Science
- 12:15pm - 1:00pm Lunch
- 1:00pm - 2:00pm Wrap up