Quelques propriétés de grands graphes aléatoires (clairsemés)
L'intérêt récent pour ces modèles vient en particulier du fait qu'ils possèdent certaines des propriétés très communément observées dans les réseaux complexes :(1) dès qu'ils sont suffisamment connectés, on observe l'émergence d'une unique composante "géante" regroupant une proportion positive des noeuds. (2) la distance entre deux noeuds typiques de la composante géante reste très petite comparativement au nombre de noeuds : c'est l'effet "petit monde". (3) dès que le graphe est assez grand, la distribution des degrés de ses noeuds ne dépend que très peu de la taille du graphe. (4) cette distribution est souvent une loi puissance. Après avoir introduit le modèle, puis effectué des préliminaires importants sur les processus de branchement, et enfin expliqué les définitions mathématiques des propriétés (1)-(4), on donnera l'idée de la preuve des trois premières pour le graphe d'Erdös-Rényi. La quatrième propriété n'est en revanche pas satisfaite par ce modèle, on donnera donc quelques exemples de généralisations, ou d'autres modèles qui peuvent la satisfaire.
