Upload
dokhuong
View
212
Download
0
Embed Size (px)
Citation preview
Reseaux SociauxMaster 1 informatique RIF IFI - Systemes Artificiels Complexes
Sebastien [email protected]
www.i3s.unice.fr/∼verel
Universite Nice Sophia AntipolisLaboratoire I3S
Equipe DOLPHIN - INRIA Lille Nord Europe
26 octobre 2012
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Plan
1 Reseaux aleatoire
2 Propagation d’informationModele SI
3 Reseaux petit monde
4 Reseaux sans echelle caracteristique
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Commencons par un peu de litterature... in English bitte
”I read somewhere that everybody on this planet is separated byonly six other people. Six degrees of separation between us and
everyone else on this planet. The President of the United States, agondolier in Venice, just fill in the names. I find it A) extremely
comforting that we’re so close, and B) like Chinese water torturethat we’re so close because you have to find the right six people tomake the right connection... I am bound to everyone on this planet
by a trail of six people.”John Guare, 1990
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
L’univers des reseaux
Reseaux
Relation binaire :relation directe entre 2 entitees
Graphe :
Ensemble de Noeuds ou sommetEnsemble d’Arcs (oriente) ou aretes (non-oriente)
Reseau : graphe + echange d’informationsmessages entre personnes, paquets entre machines,agent chimique entre genes, voiture entre villes, etc.
⇒ un de ces universaux capables de modeliser de nombreusessituations existantes
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Reseau social
Graphite, Diamant :pas d’echange d’information
→ ”juste” graphe, statique,regulier.
Relations amicales :Reseau, raison d’exister est
l’echange d’information
structure moins repetitive, sansregularite, tres imbriqueeArrive / depart d’individus
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Reseau social
Reseau social
Reseau dont les relations ou les entitessont issue d’activites sociales
Relations sociales :systeme complexe
Relations inter-individuelles simples⇒ emergence de proprietescollectives(partage information, resistancevirale, etc.)
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Reseaux
Reseaux (graphes)
modelisent la structure de nombreux systemes complexes(social, biologique, informatique, etc.)
Grandes questions :
Structure des grands reseaux
Evolution de cette structure
Phenomene de diffusion d’information dans ces reseaux
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Definitions basiques
Graphe, reseau
Un graphe oriente G est un coupleG = (V ,E ) ou :
V est l’ensemble des noeuds
E est l’arc des arcs E ⊂ V 2.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Definitions basiques
Degre sortant
deg+(v) est le nombre de noeuds w enrelation depuis v : (v ,w) ∈ E .
Degre entrant
deg−(v) est le nombre de noeuds w enrelation vers v : (w , v) ∈ E .
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Chemin et composante connexe
Chemin
Un chemin P(v ,w) est une suite denoeuds (v0, v1, . . . , vk) ou :
v0 = v et vk = w
∀i ∈ [|0, k − 1|], (vi , vi+1) ∈ E
S’il n’y qu’un seul groupe, tous lesetudiants sont relies par un chemin,le graphe G est dit connexe
Un sous-graphe connexe est unecomposante connexe, i.e. ungroupe d’etudiants
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Graphe aleatoire
Random graph : the easiest model for any network
Simple underlying asumptionbut more realistic than regular graph
First family of network studied (≈ 1950)
exact results possible
Basic idea :
Edges are added at random between a fixed number n ofvertices
Many models were developped, but the most important
the Erdos-Renyi random graphthe Gilbert random graph
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Graphe aleatoire Erdos-Renyi
Definition
Gn,m ensemble des graphes a n noeuds et m arcs.Probabilite uniforme de tirer un graphe dans cet ensemble.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Graphe aleatoire de Gilbert
Definition
Gn,p est un graphe a n noeuds danslequel un arc (v ,w) existe avec uneprobabilite p.
Easy to construct iteratively
Relation between random graph models
if m ≡ p.n the two models Gn,m andGn,p are almost interchangeable.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Graphe aleatoire de Gilbert
Definition
Gn,p est un graphe a n noeuds danslequel un arc (v ,w) existe avec uneprobabilite p.
Easy to construct iteratively
Relation between random graph models
if m ≡ p.n the two models Gn,m andGn,p are almost interchangeable.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Simulation en Netlogo
to setupset-default-shape turtles "circle"reset-ticks
end
to gomake-node
end
to make-nodecreate-turtles 1 [setxy random-pxcor random-pycorcreate-links-with other turtles
with [ random-float 1.0 < p ]]
end
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Simulation en Netlogo
to setupset-default-shape turtles "circle"reset-ticks
end
to gomake-node
end
to make-nodecreate-turtles 1 [setxy random-pxcor random-pycorcreate-links-with other turtles
with [ random-float 1.0 < p ]]
end
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Simulation en Netlogo
to setupset-default-shape turtles "circle"reset-ticks
end
to gomake-node
end
to make-nodecreate-turtles 1 [setxy random-pxcor random-pycorcreate-links-with other turtles
with [ random-float 1.0 < p ]]
end
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Distribution des degres
nature de la distribution des degres
”En gros une bosse autour de la moyenne”
Plus precisement :
Distribution binomial de parametre (n − 1, p)
Probabilite d’avoir k relations :(n−1
k
)pk(1− p)n−k ,
Moyenne : p(n − 1)
Tout le monde a a peu pres le meme nombre de relation proche dela moyenne....
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Formation du reseau
Reseau non-regulier
D’abord nombreux noeuds isoles
Puis peu de noeuds isoles, unecomposante connexe majoritaire
A partir d’une certaine valeur seuilde p, une seule composante
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Resultat sur les composantes connexes
Nombre et taille des groupes
Lorsque p < 1n ,
grande probabilite que les composantes connexes du grapheaient une taille de l’ordre de log(n).
Lorsque 1n < p,
il existe presque surement une composante connexedominante dont la taille est une fraction de n,et les autres composantes ont des tailles encore une fois trespetite de l’ordre de log(n).
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Resultat sur les composantes connexes
Seuil critique : changement de connexite rapide
Soit ε > 0 :
Si p > (1 + ε) log(n)n
alors le graphe est connexe presque surement.
Si p < (1− ε) log(n)n
alors le graphe n’est pas connexe presque surement.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Modele de propagation de maladieModele a compartiments
Principe
Les individus peuvent etre dans differents etats : descompartiments
Des regles definissent les changements d’etats
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Modele SI
Un individus peut etre dans l’etat :
S : Susceptible d’etre infecteI : Infecte
Un individus devient infecte au contact d’un individus infecteselon le taux β
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Parlons un peu de percolation...
Masque a gaz : constitue granulesde carbone poreux. Reseaualeatoire de petits tunnelsinterconnectes.
Pores larges : gaz passe a traversPores trop petits : plus detraverse
Cafe : serrage plus au moins fortdu filtre. Agglomerat de finesparticules (milieu aleatoireinhomogene)Densite a laquelle l’eau ne passeplus
→ Seuil de percolation
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Exemples
Archipel au contient : baissedu niveau de l’eau
Reseau de communication :n stations reliees avec uneprobabilite p
Melange de 2 poudres :proportion p de poudreconductrice, 1− p denon-conductrice
→ Seuil critique de percolation
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Definition
1954, Broadbent
utilisation des methodes de Monte-Carlo pour analyser lapenetration d’un fluide dans un labyrinthe de passage ouver ouferme
Terminologie (en reference au cafe) 1957 : S.R.BROADBENT et J.M. HAMMERSLEY :Modele dual de la diffusion
Processus de propagation aleatoire d’un fluide a travers un milieu
Diffusion Percolation
Mouvement du fluide aleatoire deterministe
Structure du milieu deterministe aleatoire
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Dualite diffusion/percolation
Diffusion
milieu deterministe,deplacement aleatoire
Percolation
milieu aleatoire,deplacement deterministe
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Communication de l’information
probleme de transmission
milieu etendu
distribution reguliere d’un grand nombre de ”sites”
susceptibles de relayer localement une information
communication entre sites : liens d’efficacite aleatoire
Selon la proportion de liaisons actives :
possibilite ou non de transmission information a longuedistance
pc seuil de percolation
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Modele SI dans un reseau aleatoire
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Transition de phase
Avant log(n)/n :peu de noeuds infectes
Apres log(n)/n :quasiment tous les noeudsinfectes
Nombreuses consequences
Transmission de maladiesinfectieuses
Propagation d’informationdans un reseau type”twitter”
etc.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Clustering Coefficient, coefficient d’agglomeration
Introduit par Watts and Strogatz en 1998 (des physiciens !)
Rapport entre le nombre de triangles de connaissance et lenombre maximum de triangles possibles (k(k − 1)/2)
Donne une bonne indication de la cohesion locale entre lesindividus.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Clustering Coefficient, formal definition
Clustering Coefficient
cc(v) = e(N(v))deg+(v)(deg+(v)−1) where N(v) is the nodes in the
neighborhood of v and e(N(v)) is the number of edges in theneighborhood.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Modele SI
Clustering Coefficient : exemples
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
The small world problem, Milgram
Question : What is the distance betweenpeople in the social network ?
Experiment of 1967 :
send a letter to 60 people randomlyselected from Omaha (Nebraska)
explain the study to people
Ask them to send the letter to a person inBoston (Massachusetts) with only thename, the profession and the city. (1933 - 1984)
http://maps.google.fr/maps?f=d&source=s d&saddr=Omaha,+Nebraska&daddr=Sharon,+Massachusetts&hl=fr&geocode=&mra=ls&sll=47.15984,2.988281&sspn=15.664847,39.375&ie=UTF8&ll=42.182965,-83.56269&spn=34.027051,78.75&z=4
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
The small world problem, Milgram
Some letters goes to the right person !
When it arrives, only 6 persons between source and destination
The diameter of the social network is small
−→ six degrees of separation
As usual in science, there is some critisms :
The effect of motivation increase the rate of succes :Is the social network changed with money ?
The sociology of people has some effects on the succes rate :The social network have some small network,but it is not sure all the social network is small.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Small Word phenomenon back to physicians
from the experiment ofMilgram, no convincingnetwork model generating anetwork with high ClusteringCoefficient or average shortpath length
Watts and Strogatts startedthree king of real networks
small world network : neithergrid-like network neither fullrandom network
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Examples
actor collaboration graph (Tjaden, 1997) :2 actors are connected by an undirected edge if they haveacted in at least one film
The power grid of the United States (Phadke and Thorp,1988) :
Neural network of the nematode C. elegans (White et al.1992) :
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Examples
Diameter and Clustering Coefficient of the 3 real networkscompared to random graph
D D random CC CC random
actor collaboration 3.65 2.99 0.79 0.00027power grid 18.7 12.4 0.08 0.005Neural network 2.65 2.25 0.28 0.05
Small World Network
A small world network is a network with a dense local structureand a diameter comparable to a random graph with the samenumbers of nodes and edges.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
From random to order networksWatts-Strogatz models
Small world Network
Neither :
Grid-like networks : regularity and locality, but a high averagepath length and diameter ;
Random graph : clustering coefficient of p
Watts and Strogatz proposed a mixture of both
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
From random to order networksWatts-Strogatz models
Generative Watts-Strogatz model :
Build a ring of n vertices and connect each vertex with its kclockwie neighbors on the ring
Draw a random number between 0 and 1 for each edge
Rewire each edge with probability p :
if the edge’s random nimber is smaller than p : keep the sourcevertex of the edge fixed, and choose a new target vertexuniformly at random from all other vertices.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
From random to order networksWatts-Strogatz models
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
From random to order networksWatts-Strogatz models
For p = 0, network is totaly regular.
CC is approaching 3/4 for large kdiameter in O(n)
For p = 1, network is regular random network
CC is approaching p for large kdiameter in O(log n)
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Watts-Strogatz models
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Disease Spreading in Structured populations
A lot of works from 1980 and 1990 study the deseasespreading :
topology grid, ring, starsometime different of relation between individuals
Conclusion : spatial structured can affect the speading
BUT None of this work : treat the global dynamical propertiesof the system as a function of the network structure
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Disease Spreading in Structured populations
A lot of works from 1980 and 1990 study the deseasespreading :
topology grid, ring, starsometime different of relation between individuals
Conclusion : spatial structured can affect the speading
BUT None of this work : treat the global dynamical propertiesof the system as a function of the network structure
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Disease Spreading in Structured populations
A lot of works from 1980 and 1990 study the deseasespreading :
topology grid, ring, starsometime different of relation between individuals
Conclusion : spatial structured can affect the speading
BUT None of this work : treat the global dynamical propertiesof the system as a function of the network structure
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Disease Spreading in Structured populationsSIR model (D. Watts)
3 possible states for eachelement :
susceptible : could beinfected
infected : is infected
removed : wasinfected
At each time step t :
every infected element can infecteach one of is neighbbors with theprobability p
a newly infected elements remainsinfected during 1 time step andbecomes removed prematly fromthe population
A time t = 0, a single element isinfected
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Disease Spreading in Structured populationsMeasure
The disease will have run its course and died out,Fraction Fs of the population is uninfected
The whole population will have been infected (Fs = 0),in some characteristic time T
Is Fs and T can be understood in terms of path length orclustering coeffcient ?
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Disease Spreading in Structured populationsMeasure
The disease will have run its course and died out,Fraction Fs of the population is uninfected
The whole population will have been infected (Fs = 0),in some characteristic time T
Is Fs and T can be understood in terms of path length orclustering coeffcient ?
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Disease Spreading in Structured populationsResults
p ≤ 1/(k − 1) : for alltopologies, disease infectsonly a negligibe fraction ofthe population
1/(k − 1) < p : differenttopologies yield different Fs ,it’s depends on th CC
p ≥ 0.5, for all topologies,all population infected
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Constrction d’un reseau petit-monde
n noeuds repartis spacialement
Chaque noeud est relie aux k plus proches voisins
Chaque noeud etabli q lien longue distance
Probabilite d’etablir une relation ’longue distance’ entre ai etaj : 1/d(ai , aj)
r .parametre r : tendance a se parler loin
Quelles sont les proprietes de ce reseau ?
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Exemple de reseau
100 nœuds, k = 3, q = 1 etr = 2.0 :
Coefficient d’agglomeration 0.35,distance moyenne 4.18.
Principe de formation du reseau :
En bleu : les liens courtedistance avec les k plusproches etudiants
En vert : les liens longuedistance
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Reseaux petit monde
Coefficient d’agglomeration : Distance moyenne :
Observations :
Forte agglomeration, Courte distance
⇒ Reseau petit monde
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Exercice
Exercice
Ajouter le modele SIR au reseau petit monde et dessiner la memecourbe que Watts-Strogatts
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Communication et utilisation des proprietes du reseau
Kleinberg, nagivabilite (2000)
Comment communiquer un message dans un tel reseau (cf. S.Milgram) ?
Comment trouver une ressource dans un tel reseau ?
Principe glouton :
Transmettre le message au plus proche du but !
La distance physique entre etudiants peut etre remplacee par une’distance’ abstraite a un but
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Communication et utilisation des proprietes du reseau
Kleinberg, nagivabilite (2000)
Comment communiquer un message dans un tel reseau (cf. S.Milgram) ?
Comment trouver une ressource dans un tel reseau ?
Principe glouton :
Transmettre le message au plus proche du but !
La distance physique entre etudiants peut etre remplacee par une’distance’ abstraite a un but
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Exercice
Exercice
Etudier le taux de transmission pour n = 500, k = 3 et q = 1.
Dessiner en jaune les optima locaux de la transmission
Proposer une heuristique ameliorant le principe glouton.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Quelques ecart a la realite dans certains cas
Les deux types de reseaux, les noeuds ont des degres similaires :
Pour le reseau aleatoire,distribution binomiale autour de la moyenne
Pour les reseaux petit monde,distribution normale autour du degre k
Pourtant, dans beaucoup de reseaux sociaux ce n’est pas le cas...
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Carte du trafic sur l’internet
Il existe des noeuds avec un tres grand degre : les hubs
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Definition
Reseau sans echelle caracteristique
La distribution des degres suit une loi de puissance :Le nombre de noeuds de degre k est proportionel a kα
A toutes les echelles d’observation, on ”voit” le meme reseau
Beaucoup de noeuds peu connecte
Un tres petit nombre de noued fortement connecte
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Exemples
Traffic (nombre de passager, lignes) des aearoport
Collaborations scientifique
Proximite semantique des mots
Les partenaires sexuels pour les humains
Les interaction de reseau de proteines
Question
Quels modeles de formation pour ces reseaux ?
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Un principe de formation : attachement preferentiel
Attachement preferentiel
Pour tout etudiant u,
∀v ∈ V , Pr({u, v} ∈ E ) =deg(v)∑
w∈V deg(w)
Les riches deviennent plus riches
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Exemple de formation
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Comparaison des distributions des degres
Reseau de troisieme annee (scale free)
Reseau de premiere annee (aleatoire Erdos-Renyi)
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Distance moyenne
Attachementavec et sans preference
Les distances sont pluscourtes avec attachementpreferentiels
Les hubs jouent le role deraccourcis
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Infection / Communication
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Exercice
Exercice
Simuler le modele SIR
Simuler des ”pannes” de transmission : certains noeudsaleatoires sont initialement dans l’etat R
Simuler des attaques : certains noeuds hub sont initialementdans l’etat R
Comparer le taux d’infection de ces simulations
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Robustesse aux pannes et attaques
Reseau aleatoire :
Sensible aux pannesaleatoires
Tres robuste aux attaquesciblees
Reseau scale free :
Tres robuste aux pannesaleatoires
Tres sensible aux attaquesciblees
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Conclusions
Differents modes de formation (regles locales)
Attachement uniforme : Reseaux aleatoires
Creation de lien courte et longue distance : Reseaux petitmonde
Attachement preferentiel : reseaux sans echelle caracteristiques
Trois proprietes principales
Distance moyenne (et diametre)
Coefficient d’agglomeration
Distribution des degres
Selon la structure, differentes proprietes globales... a exploiter
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Decomposition en communautes
Sous-graphes
Sous-ensemble de noeuds avec les arcs correspondantsSous-graphes particuliers :
Arbres, cliques (sous-graphe complet)
Communaute
Pas de definition admise par tous.Informellement, ensemble de noeuds fortement connectes entre eux
Beaucoup d’interet a detecter les communautes des (grands)reseaux
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Exemple de communautes
Reseau d’optima locaux d’un probleme d’optimisation combinatoire
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Bibliography
D. J. Watts and S. H. Strogatz, Collective dynamics of’small-world’ networks, Nature 393 (1998), 440–442.
D. J. Watts, Networks, Dynamics, and the Small-WorldPhenomenon, American Journal of Sociology 105 2, (1998),493–527.
A-L. Barabasi and R. Albert, Emergence of scaling in randomnetworks, Science 286 (1999), 509–512.
D. J. Watts, The ”new” science of networks, Annual Review ofSociology 30 (2004), 243–270.
Sebastien Verel Metaheuristiques
Reseaux aleatoirePropagation d’information
Reseaux petit mondeReseaux sans echelle caracteristique
Bibliography
Katharina Anna Lehmann, Michael Kaufmann.Random Graphs, Small-Worlds and Scale-Free Networks.Peer-to-Peer Systems and Applications (2005) 57-76
F. Vazquez, V.M. Eguiluz, and M. San Miguel.Generic Absorbing Transition in Coevolution DynamicsIn Phys. Rev. Lett. 100, 108702 (2008)
J. Kleinberg,”Navigation in a small world.”Nature 406 (2000)
Sebastien Verel Metaheuristiques