Forget him (or her) and keep on moving: Making mobile social networks navigable

Speaker: Augustin Chaintreau, Thomson, Paris
Host: Prof. Ramesh GovindanAbstract:
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-Universite Paris Diderot and CMM-Universidad de Chile)

Location: Kaprielian Hall (KAP) - 163

Audiences: Everyone Is Invited

Contact: CS Colloquia