1

D-NETDynamic Networks Research Project Team Proposal V1.0

E. Fleury, ENS Lyon / INRIA

February 2009

2

Challenges & Objectives

3

“Réseaux complexes dynamiques”Grands ensembles d’entités en relation, en réseau, qui jouent un rôle clé

• Réseaux technologiques: informatiques / transport

• Réseaux de citation / sociologique

• Réseaux biologiques / épidémiologique

Graphes étudiés issus • de contextes sémantiques particuliers,

• d’expériences et de données in situ

• relations avec le monde réel / réalité concrète.

Objets de natures très diverses mais avec des propriétés communes non triviales

• Science des réseaux complexes

Dynamique de ces objets de terrainRéseau métabolique

Réseau Internet

4

Objectifs scientifiques

Fondation pour une « science des réseaux dynamiques »

Pour laquelle : • Un « très » grand nombre d’entités interagissant

• Auto organisation

• Petit monde

• Hétérogénéité et loi sans échelle

• Dynamique importante

sont des caractéristiques intrinsèques importantes.

Expected

P(k) ~ k-

Found

5

Préoccupations scientifiques communes

• Comment obtenir de l’information pertinente sur les réseaux dynamiques ?

• Comment les décrire ?

• Quelles sont leurs

– Propriétés communes ?

– Leurs spécificités ?

– Leurs dynamiques ?

• Comment

– les modéliser ?

– Les manipuler ?

• Comment concevoir des protocoles et une algorithmique appropriée à ces réseaux ?

6Quatre angles d’attaque scientifiques

Mesure• observer, échantillonner, estimer des réseaux d’entités très complexes

• vision partielle et biaisée de l’objet réel

Analyse• décrire la structure, ses propriétés principales, ses caractéristiques

• notions statistiques et/ou structurelles

• pertinence et robustesse vis-à-vis de la mesure ?

Modélisation• modèle de la dynamique des réseaux et/ou sur les réseaux

• graphes artificiels, représentatifs des propriétés choisies

Algorithmique• Évaluation / optimisation d’algorithmes distribués

7

Application Domains

8

Health / Epidemiology Mastering hOSpital Antimicrobial Resistance

Better understand the dynamic of AMRB transmission• the real-time analysis of the relative contribution of exposure to

antibiotics;• the intrinsic characteristics of epidemic clones that contribute to

inter-individual transmission;• the identification of factors contributing to the transmission of strains

between individuals in the hospital population and community.

Document interactions between• medical and nursing staff• patients to patients• patient to medical staff

Document contact frequencies• monitor the dynamic (inter & intra contact)• characterize the interaction network

9MOSAR’s experiment

http://perso.ens-lyon.fr/eric.fleury/Upload/Mosar/MosarEng080120.wmv

600 people / every 30sec / 6 months 311 Millions snapshots

10

Health / Sociometry TUBEXPO

Study of the Health Care Workers (HCWs) exposure to tuberculosis in their work environment

• Bias of audit / conversations (HCW souvenirs);

• Bias of the measure itself

Document interactions between• medical / nursing staff to patients

Document contact frequencies• monitor the dynamic (inter & intra contact)

• characterize the interaction network

Hospital Hygiene• Impact of isolation procedure on watch frequency

• Impact on the time of received treatment

• Movement during surgery (surgeon / anaesthetist)

À éviter: une mauvaise rencontre avec Mycobacterium tuberculosis (source: NY State Departement of Health)

11TUBEXPO’s experiment

12

Dynamique des populations IXXI DISPOP

Dynamique spatial des populations

• Animal• Analyse multi modal

Outil de mesure • Des interactions sociales• Méthodologie pour l’analyse

Recherche pluri disciplinaires• DEPE (Département

Ecologie, Physiologie et Ethologie) de l'IPHC (Institut Pluridisciplinaire Hubert Curien)

13Wireless Sensor Networks

Application / Measure oriented

Classical theme• Exploit large # of devices• In-network and collaborative processing for longevity

New researches• Optimize system as a whole• Exploit multiple modalities, multiple scales, and mobility• Interactivity• Calibration, self test, validation

Great Experimental Tool• Measure close to the physical phenomena

WIDE/CNRS

IP MOSARIP WASP

ANR SensLABADT SensTOOLS

RECAP

14

ENS / LIP environmentAddressing Interdisciplinary Issues

•

Spin off new themes• Static & dynamic analyse of interaction network

• Metrology of wireless Network

• Overlay & Scheduling

Foster collaborations• P. Abry, P. Borgnat, P. Goncalves

July 2007

15

The Dream Team

16Team Composition

Project Head• Eric FLEURY, Professor, ENS Lyon

Permanent Researchers• Guillaume CHELIUS, CR1, INRIA

Non Permanent Researchers• Céline ROBARDET, délégation INRIA

Engineers• Loïc Lemaître, ADT SensTOOLS

• ANR SensLAB

Administrative Assistant• TBD

PhD Students• Elyes BEN HAMIDA, MENRT

• Andreaa CHIS, WASP

• Qinna WANG, MENRT

17

Scientific Foundations

18

Three Complementary Scientific Directions— short/long term challenges —

Données réelles massives et dynamiques

Analyse et modélisation

Algorithmique

L’objectif général que l’on se donne est de maximiser l’information (qualitativement & quantitativement) que l’on peut retirer d’un système de mesure distribué, collaboratif, adaptatif et intelligent au travers de la conception, de la mise en œuvre d’architectures de mesure, du déploiement et du développement d’applications distribuées.

19

Données réelles massives et dynamiques

Exploiter des grands jeux de données réelles et de qualité sur des réseaux dynamiques

Les objets considérés varient suivant les disciplines, mais les problématiques sont souvent les mêmes :

Comment obtenir de l’information pertinente sur ces réseaux ? Comment les décrire ?

Conception et optimisation d’applications distribuées / de mesure. Qualité des données observées dans le monde réel Comportement globale de l’application de mesure Relations existantes entre le résultat et les biais du processus distribué de la

mesure

20Analyze & modelsFrom "primitive" to "analyzable" data: Observables

different time and space resolutions. local quantities

number of contacts of each individual pair-wise contact times and durations

global measures the fluctuations of the average connectivity.

« analyzable data » whose relevance and meaningfulness for the analysis of network dynamic and network diffusion phenomena will need to be assessed.

Granularity and resolution. Time-series approach, « condensing » network dynamics description at various granularity

levels, both in time and space understanding of the evolution of the network from a set of isolated contacts (when

analyzed with low resolution) to a globally interconnected ensemble of individuals (at large analysis scale).

selecting the adequate level of granularity / the multi-modality of the data, with potentially different time resolutions

wavelet decompositions and multiresolution analyses: go beyond the intermittency models

21Analyze & models (cont)Dependencies, correlations and causality

Does a given property observed on different components of the data result from a same and single network mechanism controlling the ensemble or rather stem from different and independent causes?

Do correlations observed on one instance of information (e.g., topological) command correlations for other modalities?

Can directionality in correlations (causality) be inferred amongst the different components of multivariate data? can be envisioned with different time and space resolutions.

22Analyze & models (cont)Toward a dynamic graph model and theory

the basic notions for manipulating dynamic graphs (as graph theory does for static graphs),

the notions and indicators to describe its dynamics meaningfully (as complex networks theory does for static complex networks).

Dynamic communities build a network which encodes temporal modifications carefully investigate the space/time complexity of such approach

Tools for dynamic graph visualization

23

D-NET in the World Wide Research Scene

24Positioning at INRIADT3 Réseaux, systèmes et services, calcul distribué

Com B: Networks and Telecoms• GANG: Networks, Graphs and Algorithms. Study of the structure and algorithmic

characteristics of large networks such as Internet, wireless networks (ad hoc) and peer-to-peer networks. 

Com A: Distributed systems and software architecture• ASAP: foundations of large scale dynamic distributed systems. Complementary expertise.

Formal & informal collaborations.

• POPS: focused on operating systems scalability, less focused on autonomic networking or cross layer approach.

• CEPAGE: conception d’algorithmes et de structures de données et à leur déploiement sur des plates-formes dynamiques à grande échelle. (Distribution de contenu, tâches, réseaux virtuels)

Cog C: Multimedia data: interpretation and man-machine interaction• GRAVITE: visualisation interactive, fouille et à l’analyse de données massives.

• AVIZ: méthodes d’analyse et de visualisation de grandes quantités de données (réseaux sociaux)

25

European & International positioning

France• LIP6, M. Latapy

• CREA / RNSC

Europe• Louvain (Blondel)

• Cx-Net • Institute for Scientific Interchange

Foundation

World• Sante Fe Institute

• Barabasi LAB

• Indiana University School of Informatics (A. Vespignani)

• Center for the Study of Complex Systems, University of Michigan (M. E. J. Newman)

• Cornell University (J. Kleinberg)

• Tokyo University (Live-E)

26

Grant & Activities

27

Grants

National• CNRS RECAP

• ANR SensLAB

• ADT SensTOOLS

• AFFSET TUBEXPO

Industrial• ALU

European• FP6 IST, IP, WASP

• FP6 LSH, IP, MOSAR

28

Dissemination

29

Conference committees

Networking• VTC 2009, ICC 2008/09,

NETWORKING 2009, COMSWARE 2007/08/09, PIMRC 2008, Networking 2009

Autonomic Computing• PERCOM 2009, EuroPar 2008

Sensor Networks• WSN 2008, Intersens 2006,

MSN 2006-07, REALMAN, T2PWSN 2007

Distributed / Theoretical computing• AlgoSensor, DIALM-POMC, FAWN,

SpaSWiN, Adhoc-Now 08, DCOSS 08,

Performance Evaluation• PE-WASUN, SIMUTools,

PM2HW2N

Complex Networks• Dynamics on and of complex

networks 2009

30

31

lettre en date du 18/07/2008 de la direction du CITI à l’attention de : Alain Viari, Eric Fleury, François Sillion, Frédéric Desprez

« […] impératif que la gouvernance des projets INRIA dont l’activité est centrée sur le CITI soit portée par un membre interne au laboratoire et non par un membre extérieur »

32

Individual trajectories among social groups (cont)

• Individual 19, enters group 13 (time step 1215)

• Goes to group 9

• Before going to group 10

19 13

9

19 10

19

33

34