[STOC2011] N. Schabanel - Search for optimal paths in small worlds: Dimension matters
Nicolas Schabanel
2011-06-08
Views 2
2011.06.07 - Talk at the ACM STOC conference 2011, San Jose, CA, USA
----
Optimal Path Search in Small Worlds: Dimension Matters
by Nicolas Schabanel (CNRS -- LIAFA, Université Paris Diderot -- IXXI, École Normale Supérieure de Lyon -- France)
joint work with George Giakkoupis (LIAFA, Université Paris Diderot)
----
Abstract. In this paper, we give an (asymptotically) exact and quite surprising answer to a quite old (2004) open question in the domain of models for social behavior: is it possible to search for optimal paths in a smallworld network? That is to say, is it possible to find and follow an optimal path from a source to a destination using only local views of the network? This question has clearly applications to the design of routing tables and peer-to-peer protocols. The answer we give is the following:
• if the underlying dimension of the small world network is 1, then the answer is NO: optimal paths have length O(log n) whereas the best path a local-search algorithm can compute has length Ω(log n loglog n) on expectation and we provide an algorithm matching this bound.
• if the underlying dimension of the small world network is 2 or more, then the answer is YES: a finely-tuned BFS algorithm computes paths of optimal expected length O(log n).
This is the first time such a brutal dimension-based transition of behavior is observed in this model in the small-world regime. A quite surprising consequence of our work is that peer-to-peer protocols could improve significantly their performances by using a bidimensional grid for their underlying topology rather than a ring as it is the case for most of them right now. This work is based on the seminal model of Kleinberg (2000) that we'll recall and whose history will be retraced.
----
Optimal Path Search in Small Worlds: Dimension Matters
by Nicolas Schabanel (CNRS -- LIAFA, Université Paris Diderot -- IXXI, École Normale Supérieure de Lyon -- France)
joint work with George Giakkoupis (LIAFA, Université Paris Diderot)
----
Abstract. In this paper, we give an (asymptotically) exact and quite surprising answer to a quite old (2004) open question in the domain of models for social behavior: is it possible to search for optimal paths in a smallworld network? That is to say, is it possible to find and follow an optimal path from a source to a destination using only local views of the network? This question has clearly applications to the design of routing tables and peer-to-peer protocols. The answer we give is the following:
• if the underlying dimension of the small world network is 1, then the answer is NO: optimal paths have length O(log n) whereas the best path a local-search algorithm can compute has length Ω(log n loglog n) on expectation and we provide an algorithm matching this bound.
• if the underlying dimension of the small world network is 2 or more, then the answer is YES: a finely-tuned BFS algorithm computes paths of optimal expected length O(log n).
This is the first time such a brutal dimension-based transition of behavior is observed in this model in the small-world regime. A quite surprising consequence of our work is that peer-to-peer protocols could improve significantly their performances by using a bidimensional grid for their underlying topology rather than a ring as it is the case for most of them right now. This work is based on the seminal model of Kleinberg (2000) that we'll recall and whose history will be retraced.
Report form
RELATED VIDEOS
