View
103
Download
0
Category
Preview:
Citation preview
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
Recommended