Forget him (or her) and keep on moving: Making mobile social networks navigable
Augustin Chaintreau
Thomson Technology Paris Laboratory
Date: Thursday, August 21, 4pm
Location: BA 7231
Abstract:
A network is navigable if a simple decentralized scheme allows efficient
routing (i.e. in a polylogarithmic number of steps). Previous works have shown
that general classes of graphs can be made navigable by adding few links
according to an appropriate distribution. However, for most of this graphs,
navigability is sensitive to small deviations from this distribution. Moreover,
it seems difficult for the nodes to manage such a link addition in a
distributed way. In spite of some efforts, and evidence of the "small-world
phenomenon" in social networks, no model currently proves the emergence of
navigability from local dynamics.
Here we prove that navigability emerges from nodes own mobility and memory.
Inspired by emerging opportunistic mobile networks using human carried devices
(a.k.a. Pocket switched networks), we model a network where nodes move (in our
case, according to a random walk in dimension d), and may opportunistically
create connections as they meet physically. Once established, these connections
are randomly maintained or forgotten, based only their current age. We prove
that this simple setting allows one to create navigable networks. We present a
few applications of these techniques to design opportunistic spatial gossip,
and discuss the upcoming challenges in relation with recent experiences on
using social software for opportunistic mobile networks.
This is a joint work with Pierre Fraigniaud and Emmanuelle Lebhar, from
CNRS-LIAFA, and Universit� Paris 7.
Host of the talk
Peter Marbach (marbach@cs.toronto.edu)