Social network analysis over dynamic graphs and application to urban mobile ad hoc networks

Wireless mobile ad hoc networks (MANET) are composed of mobile communicating devices that self-organize to ubiquitously exchange information over the air. Envisioned applications for such networks cover disaster relief situations, battlefield deployment and more generally any use-case that makes the deployment of wired or infrastructure-based networks too costly or simply unsuitable. Lately, new applications for MANETs are developing in the urban environment, namely mobile social networks and vehicular ad hoc networks. Despite this large spectrum of possible applications and the large number of wireless-capable devices available today, mobile ad hoc networks remain confidential. One important reason is the lack of reliability of wireless communications, especially on long path.
In this thesis, we propose to cope with this problem by creating virtual structures that will group together limited set of users that are densely and reliably connected in order to favor the dynamic and robust exchange of information. Our proposal uses the concept of community, that first appeared in social network analysis. After reviewing the main concepts taken from this branch of graph theory and justifying the application by underlining the specificities of MANETs in the urban context, we formally present our contribution, based on epidemic propagation of community labels. Then we exhibit its applications on concrete communication systems and how it can benefit more generally to improve the management of wireless ad hoc networks topology.