Time Elsewhere

Friday, June 4

10:00-11:00 S1: Invited speaker: Renaud Lambiotte
11:00-12:00 S2: Monitoring & Protocols
14:00-15:30 S3: Models & Tools

Friday, June 4 10:00 - 11:00

S1: Invited speaker: Renaud Lambiotte

Multi-scale Modularity in Complex Networks
Renaud Lambiotte (University of Namur, Belgium)

We focus on the detection of communities in multi-scale networks, namely networks made of different levels of organization and in which modules exist at different scales. It is first shown that methods based on modularity are not appropriate to uncover modules in empirical networks, mainly because modularity optimization has an intrinsic bias towards partitions having a characteristic number of modules which might not be compatible with the modular organization of the system. We argue for the use of more flexible quality functions incorporating a resolution parameter that allows us to reveal the natural scales of the system. Different types of multi-resolution quality functions are described and unified by looking at the partitioning problem from a dynamical viewpoint. Finally, significant values of the resolution parameter are selected by using complementary measures of robustness of the uncovered partitions. The methods are illustrated on a benchmark and an empirical network.

Friday, June 4 11:00 - 12:00

S2: Monitoring & Protocols

Optimal Monotone Forwarding Policies in Delay Tolerant Mobile Ad Hoc Networks with Multiple Classes of Nodes
Francesco De Pellegrini (University of Avignon, France); Eitan Altman (INRIA, France); Tamer Başar (University of Illinois at Urbana-Champaign, USA)

In this paper we describe a framework for the optimal control of delay tolerant mobile ad hoc networks where multiple classes of nodes exist. We specialize the description of the energy-delay tradeoffs as an optimization problem based on a fluid approximation. We then adopt two product forms to model message diffusion and show that extremal controls are of bang-bang type. Using the general framework we analyze some specific cases of interest for applications.

Detecting Events in the Dynamics of Ego-centered Measurements of the Internet Topology
Assia Hamzaoui (UPMC & LIP6, France); Matthieu Latapy (LIP6 - CNRS and UPMC, France); Clémence Magnien (CNRS, France)

Detecting events such as major routing changes, in the dynamics of internet topology is an important but challenging task. We explore here a 'top-down' approach based on a notion of statistically meaningful events. It consists in identifying statistics which exhibit a homogeneous distribution with outliers, which correspond to events. We apply this approach to 'ego-centerd' measurements of the internet topology (views obtained from a single monitor) and show that it succeeds in detecting meaningful events. Finally, we give some hints for the interpretation of such events in terms of network events.

Friday, June 4 14:00 - 15:30

S3: Models & Tools

K-Shell Decomposition for Dynamic Complex Networks
Daniele Miorandi (U-Hopper, Italy); Francesco De Pellegrini (University of Avignon, France)

K-shell graph decomposition methods have been recently proposed as a technique for understanding the most influential spreader in a complex network. Such techniques apply to static networks, whereby topology does not change over time. In this paper we address the extension of such a framework to dynamic networks, which can be characterized by a pattern of contacts among nodes in the network. We proposed two methods and we compare them by using synthetic contact traces.

Static community detection algorithms for evolving networks
Thomas Aynaud (LIP6, France); Jean-Loup Guillaume (Université de la Rochelle, France)

Complex networks can often be divided in dense sub-networks called communities. We study, using a partition edit distance, how three community detection algorithms transform their outputs if the input network is sligthly modified. The instabilities appear to be important and we propose a modification of one algorithm to stabilize it and to allow the tracking of the communities in a dynamic network. This modification has one parameter which is a tradeoff between stability and quality. The resulting algorithm appears to be very effective. We finnaly use it on a dynamic network of blogs.