User Tools

Site Tools


chicoutimi_2016:modele_graphes_aleatoires

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

chicoutimi_2016:modele_graphes_aleatoires [2016/05/12 23:53] (current)
melancon created
Line 1: Line 1:
 +====== Visual Analytics Course ======
  
 +Instructor: [[http://​www.labri.fr/​perso/​melancon|Guy Melançon]] (email: ''​Guy dot Melancon at labri dot fr''​)
 +
 +{{:​uqac.jpg?​nolink&​100 |}}
 +
 +===== Chicoutimi Summer 2016 roadmap / May 3, 3pm course =====
 +
 +  * [[chicoutimi_2016:​session_by_session_cutdown|Back to the course start page]]
 +
 +==== Modèles de graphes aléatoires ====
 +
 +Des modèles de graphes aléatoires sont décrits ici en lien avec la présentation des [[chicoutimi_2016:​mesures_sur_les_graphes|mesures sur les graphes]].
 +
 +=== Modèle de Erdos - Renyi ===
 +
 +C'est le modèle de référence peut-être le plus connu, et le seul à avoir existé jusqu'​à récemment. Il a été très étudié par les mathématicien [[https://​en.wikipedia.org/​wiki/​Paul_Erd%C5%91s|Paul Erdős]] et [[https://​en.wikipedia.org/​wiki/​Alfr%C3%A9d_R%C3%A9nyi|Alfréd Rényi]].
 +
 +Le modèle $G(n, p)$ de Erdős et Rényi est le plus connu (il en existe un autre qui lui est similaire). Ce modèle permet de construire un graphe en faisant une succession de tirage aléatoire de Bernouilli, un tirage pour chaque paire de sommets $i, j \in \{1, 2, \ldots, n\}$ avec probabilité $p \in [0, 1]$ de succès. Ce modèle produit donc un graphe sur $n$ sommets contenant un nombre d'​arêtes proches de ${n \choose 2} \cdot p$.
 +
 +La distribution des degrés d'un tel graphe s'​approche d'une distribution de Poisson.
 +
 +{{ :​chicoutimi_2016:​erdos_renyi.jpeg?​nolink&​600 |Graphe aléatoire Erdős-Rényi sur 500 sommets et comptant 1000 sommets. A gauche, la fréquence empirique des degrés du graphe.}}
 +
 +La distance moyenne dans ce graphe est d'un peu plus de 4. En général, la distance moyenne dans un graphe aléatoire de Erdős-Rényi,​ la distance moyenne entre les sommets est petite (par rapport au nombre de sommets) et proche de $\log_e(N)/​\log_e(\bar k)$ où $\bar k$ désigne le degré moyen du graphe.
 +
 +=== Modèle de Wang et al. (2007) ===
 +
 +Ce modèle, de {{:​chicoutimi_2016:​wang_2007.pdf|Wang et al. présenté dans un article de 2007}}, imite la structure des graphes petit monde: distance moyenne petite et coefficient de clustering plus élevé (qu'un graphe aléatoire Erod-Rényi de même taille et de même densité d'​arêtes).
 +
 +{{ :​chicoutimi_2016:​wang.jpeg?​nolink&​600 |}}
 +
 +La distribution du degré dan ces graphes suit typiquement une loi de puissance $y \sim c x^\gamma$, et le coefficient de clustering moyen est élevé. Il faut comparer avec l'​image associé au graphe aléatoire du paragraphe précédent. Note: on utilise une échelle logarithmique sur les ordonnées de la distribution des degrés du graphe de Wang. On utilise une échelle logarithmique pour les ordonnées des distributions du coefficient de clustering pour les deux graphes.
 +
 +Le coefficient de clustering moyen du graphe de Erdos-Renyi avoisine les 0.03 alors qu'il est voisin de 0.75 pour le graphe généré selon le modèle de Wang.
 +
 +La distance moyenne entre les sommets du graphe Erdos-Renyi est de 8.43 alors qu'​elle est de 8.60 pour le graphe de Wang.
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/modele_graphes_aleatoires.txt · Last modified: 2016/05/12 23:53 by melancon