Réseaux complexes

Qu’est-ce qu’un réseau ?

Points/sites reliés par des liens

individus

ordinateurspages webaéroportsmolécules....

relations sociales (ex:collaborations scientifiques)câbleshyperliensconnexions aériennesréactions chimiques....

AutoorganisationEvolution dynamique

Etude des réseaux complexes

•Etude phénoménologique:

dégager des caractéristiques générales

•Modélisation:

comprendre les mécanismes

•Conséquences: comprendre l’importance des différentes caractéristiques

pour différents phénomènes, par exemple la propagation

d’épidémies, la fragilité en face de pannes ou d’attaques...

Réseaux sociaux:l’expérience de Milgram

Milgram, Psych Today 2, 60 (1967)

Dodds et al., Science 301, 827 (2003)

“Six degrés de séparation”: “petit-monde”

L’Internet: un autre “petit-monde”

Histogramme des distancesentre deux sites:

distances typiques très petitespar rapport à la taille d’Internet

Autres exemples: WWW, réseaux de transports, etc...

Une autre caractéristique répandue: “Clustering”

1

2

3

n

Plus grande probabilité d’être connectés

Clustering: Mes amis se connaissent très probablement entre eux (exemple typique: réseaux sociaux)

Effet quantifié parle coefficient de clustering,entre 0 et 1

Modèle le plus simple de réseaux:Erdös-Renyi (1960)

-N points, liés avec probabilité p:

-Modifications du modèle pour introduire le clustering

Réseau -statique, -homogène: nombre de voisins similaire pour tous

Réseau du transport aérien

Une vision d’Internet

Homogène vs. Hétérogène

Réseau homogène

nombre de voisins similaire pour tous Réseau hétérogène:

grandes variations du nombre de voisins

Principales caractéristiques des réseaux complexes

•Nombreux éléments en interaction•Evolution dynamique•Auto-organisation

•Nombreux éléments en interaction•Evolution dynamique•Auto-organisation

Architecture non-trivialePropriétés émergentes

Phénomènes coopératifs

petit-mondeclusteringhétérogénéité

Internet,World-Wide-Web,Réseaux sociauxetc...

Modélisation des réseaux complexes

Processus microscopiques des composants

Propriétés statistiques et dynamiquesau niveau macroscopique

Physique

Statistique

La modélisation commence par la compréhensiondes mécanismes de base de la formation du réseau

La topologie complexe est générée dans les modèles,et non mise à la main de façon ad-hoc

Meilleure compréhension de l’interaction entredynamique, trafic, etc...

Changement de point de vue

Exemple de mécanisme:L’attachement préférentiel

1)Les réseaux croissent par l’addition de nouveaux sites

Exemples:

WWW : addition de nouvelles pages webs Internet : nouveaux ordinateurs, serveurs

2) Les nouveaux sites se connectent plutôt vers des sites ayant déjà de

nombreux voisinsExemples:WWW : liens vers des pages webs connuesInternet : liens vers des fournisseurs d’accès bien connectés

1) + 2) => réseau très hétérogène

Graphe aléatoire vs

Attachement préférentiel

Autres niveaux de complexité

• intensités des liens

• réseaux dynamiques

(ex: peer-to-peer)

• réseaux dirigés (ex: WWW)

Exemple d’applications:

épidémiologie

Modèles de propagation d’épidémies

Description schématique des individus et de leur état:

Les individus peuvent se trouver dans certains états: Sain/Susceptible * Infecté * Immunisé/Remis

-Propagation par contact

S I II

p

-Guérison/immunisation

I R

Modèles de propagation d’épidémies

Réseau de contacts:•Individus=sites•Liens=possibilité de propagation

Réseau dont la topologiejoue un rôle important

Virus sur ordinateurs Topologie d’Internet

Computer worms Topologie du réseaud’ email

Importance de la topologiedu réseau de contacts

Epidémiologie Topologie du réseaude transports/déplacements

Importance de la topologiedu réseau de contacts

p0 pc

L’épidémie se propage

L’épidémiemeurt

p0pc=0 (ou très petit)

L’épidémie se propage

Graphes homogènes Graphes hétérogènes

S I II

p

Un autre exemple de modèlede propagation d’une épidémie

Ville A Ville Ba

b

c

d

Un autre exemple;propagation d’une épidémie

Ville A Ville B

=>Importance du réseau de transport !

ab

c

d

Une épidémie ancienne

Dec. 1347

Dec. 1347June 1348

Dec. 1348

June 1349

Dec. 1349

June 1350

Dec. 1350

Dec. 1347

Dec. 1350

Peste NoirePeste Noire14ème siècle14ème siècle

Nov. 2002

Mar. 2003

Une épidémie récente

SARSSARS

Etudes possibles

caractérisation du réseau de transport(essentiellement: transport aérien) modèle simple d’épidémie reproduire a posteriori le déroulement de l’épidémiepour valider le modèle

étude, dans le cadre du modèle, de l’influencedes différents niveaux de complexité étude de la prédictabilité étude de mesures d’endiguement

Conclusion

Domaine interdisciplinaire:

informatique, biologie, épidémiologie, sciences sociales...

-Importance études empiriques

-Modélisation

-Conséquences sur processus divers

PhysiqueStatistique

(exemples: épidémies; fragilité des réseaux; ...)

RobustnessComplex systems maintain their basic functions even under errors and failures (cell mutations; Internet router breakdowns)

node failure

fc

0 1Fraction of removed nodes, f

1

SS: fraction of giant

component

Case of Scale-free NetworksCase of Scale-free Networks

s

fc 1

Random failure fc =1 ( 3)

Attack =progressive failure of the most

connected nodes fc <1

Internet mapsInternet maps

R. Albert, H. Jeong, A.L. Barabasi, Nature 406 378 (2000)

Failures vs. attacks

1

S

0 1ffc

Attacks

3 : fc=1

(R. Cohen et al PRL, 2000)

Failures

Topological error tolerance