Linked !Linked !

La nouvelle science des réseauxAlain BouquetPCC - CDF

Alain Bouquet Linked ! 2

Graphes et réseauxGraphes et réseaux

Nœuds et liensUn réseau est formé de nœuds

connectés par des liensCes liens peuvent être

• Orientés ou non• Pondérés ou non

Les mathématiciens parlent de graphes

Euler et les ponts de Königsberg

Graphes réguliers– Nœuds et liens connus– Nombre de liens par nœud fixé– Cristallographie et percolation

Alain Bouquet Linked ! 3

Mais est-ce bien réaliste ?

Réseaux aléatoiresRéseaux aléatoires

Erdös & Rényi (1959)Réseaux aléatoires où

• Chaque nœud est connecté aléatoirement à un autre nœud

• selon une distribution de Poisson

Un tout petit monde• N nœuds ayant k liens en moyenne• En d sauts on rejoint kd nœuds • Diamètre D du réseau = Log N / Log

k

Cinq degrés de séparation• N = 10 milliards, k =100 D = 5• Tout homme est -en moyenne- relié

par 4 intermédiaires à n’importe quel autre homme

Les communautés• Granovetter (1973)• Watts & Strogatz (1998)

Beaucoup de liens « courts » avec quelques liens « à longue portée » redonnent les résultats du modèle purement aléatoire

Alain Bouquet Linked ! 4

La réalitéLa réalité

Enquête sur les réseaux réels

Le nombre de liens par nœud ne suit pratiquement jamais une loi de Poisson, mais une loi de puissance

P(k) ~k- avec ~ 2 ou 3

La plupart des nœuds sont

très faiblement connectés Quelques uns sont très

fortement connectésLa valeur moyenne ne signifie

rien

Alain Bouquet Linked ! 5

Les plaques tournantesLes plaques tournantes

Quelques nœuds assurent l’essentiel de la connectivité

Ce sont les plaques tournantes du réseau, par qui sont reliés la majorité des nœuds

Etes-vous une plaque tournante ?

Alain Bouquet Linked ! 6

Le modèle sans échelleLe modèle sans échelle

D’où vient cette structure ? (Barabasi et al. 1999)

Les riches s’enrichissent

Réseau dynamique : il se construit nœud par nœud

Attachement préférentiel : un nœud se connecte de préférence à un nœud riche

Alain Bouquet Linked ! 7

L’effet GoogleL’effet Google

Ouvriers de la 11e heure– Dans le modèle précédent, les

premiers nœuds possèdent un avantage que les suivants ne rattrappent jamais.

– Il existe cependant des cas où un tard venu s ’impose sur un « marché » déjà bien occupé :

• Nouveau prédateur dans un écosystème

• Boeing face à Douglas et Lockheed, puis Airbus face à Boeing

• Google face à AltaVista• Linux face à Windows ?

Aptitude– Cela s’incorpore facilement

en introduisant une « aptitude » d ’un nouveau lien, modulant la probabilité des autres à s’y connecter

Raffinements– On peut aussi modéliser le

« vieillissement » d’un nœud en modulant son aptitude à nouer de nouvelles connexions

Alain Bouquet Linked ! 8

Réduire un monopole ?

L’effet MicrosoftL’effet Microsoft

Bose-Einstein– En 2001 Barabasi et al.

Remarquent que les équations du modèle sont identiques à celles d ’un gaz de bosons, où

• Liens <-> bosons• Aptitudes des nœuds <-

> niveaux d’énergie

– Placés dans des circonstances favorables, la quasi-totalité des bosons se « condensent » dans l’état d ’énergie minimale

Condensation de Bose– Dans le vocabulaire des

réseaux, cela signifie que la quasi-totalité des liens se rattache au même nœud

– Dans un réseau économique, cela s ’appelle un monopole.

Existe-t-il des monopoles ?

Alain Bouquet Linked ! 9

Domaine quasi-inexploré

Réseaux orientésRéseaux orientés

Exemples très courants– Relations économiques– Chaînes alimentaires– Réactions biologiques– Hiérarchies– Citations– Internet bien sûr...

4 domaines

Alain Bouquet Linked ! 10

Stratégies de défense ?

Résilience et fragilitéRésilience et fragilité

Insensibilité aux pannes aléatoires– La majorité des pannes

frappe -statistiquement- des nœuds peu connectés, et elles ont des effets mineurs

Risque de pannes en cascade– Par contre une panne qui

frappe une plaque tournante dévie le trafic vers d ’autres, qui peuvent ne pas résister à la surcharge et lâcher à leur tour

Fragilité face aux attaques coordonnées sur les plaques tournantes– Le risque majeur est une

attaque simultanée des plaques tournantes

– Le réseau se fragmente alors en îlots déconnectés les uns des autres

– Exemple : attaque coordonnée en octobre 2002 sur 7 des 13 DNS d ’Internet

Alain Bouquet Linked ! 11

EconomieEconomie

Organisation traditionnelle, pyramidale des entreprises

Réseau de clients et de fournisseurs

Réseau orienté pondéré

Organisation en réseau : « outsourcing », « joint ventures »

•Avantages : résilience, souplesse, liberté…

•Inconvénients :fragilités aux pannes en cascade, vulnérabilité des plaques tournantes, plus difficile à contrôler...

Alain Bouquet Linked ! 12

C’est fini !C’est fini !

Je vous remercie

de votre attention