Analyse statistique de graphes
Préambule
1
Introduction aux graphes
1.1
Exemples de graphes
1.2
Définitions
1.3
Visualisation
1.4
TP – Package
igraph
Package
igraph
Créer un graphe à la main
Matrice d’adjacence
Propiétés de base d’un graphe
Visualisation de graphes
Embellir ses figures avec
igraph
Exercice 1
2
Exploration des graphes et statistique descriptive
2.1
Densité
2.2
Voisinage et degré
2.3
Distance et diamètre
2.4
Connexité
2.5
Motifs
2.6
Clustering, transitivité
2.7
Centralité de sommets
2.8
TP – Exploration des données
Propiétés de base d’un graphe
Les degrés avec
igraph
Autres indicateurs
Exercice 2.
3
Modèles de graphes aléatoires – Partie 1
3.1
Modèle d’Erdös-Rényi
3.1.1
Définition
3.1.2
Simulation de grands graphes
3.1.3
Distribution des degrés
3.1.4
Mauvais ajustement aux réseaux réels
3.2
TP – Modèle
\(G(n,p)\)
Modèle
\(G(n,p)\)
ou modèle de Erdös-Rényi
Exercice 1
Exercice 2
3.3
Graphes
scale free
3.3.1
Loi de puissance des degrés
3.3.2
Suite de degrés réalisable
3.3.3
Simulation de graphe avec degrés donnés
3.3.4
Modèle à degrés fixés
3.3.5
Modèle à degrés aléatoires
3.4
TP – Modèle de loi de puissance des degrés
Exercice 1
Exercice 2
4
Spectral clustering
4.1
Matrices laplaciennes de graphe
4.1.1
Laplacien non normalisé
4.1.2
Laplacien normalisé
4.1.3
Laplacien
\(L_{\text{abs}}\)
4.2
Algorithmes de spectral clustering
4.2.1
Heuristique
4.2.2
Rappel:
\(k\)
-means
4.2.3
Trois algorithmes
4.2.4
Choix du nombre de clusters
4.2.5
Exemples jouets
4.3
TP - Implémentation du spectral clustering
Debugging dans RStudio
Exercice 1
Exercice 2
Exercice 3
4.4
Perturbation de matrices
4.4.1
Théorie de perturbation
4.4.2
Perturbation de graphe
4.4.3
Commentaires
4.5
Clustering de données vectorielles
4.5.1
Graphes de similarité
4.5.2
Commentaires pratiques
4.6
TP - Graphes de similarités
5
Alternatives pour la détection de communautés
5.1
Graph cuts
5.2
Modularité et intermédiarité
5.2.1
Intermédiarité d’arête
5.2.2
Modularité pour le choix du nombre de clusters
5.3
TP – Modularité
Choix du nombre de clusters
Algorithme de Louvain
Exercice
6
Modèles de graphes aléatoires – Partie 2
6.1
Modèles exponentiels de graphes aléatoires
6.2
Attachement préférentiel
6.3
Modèle à positions latentes
6.3.1
Version classifiante du modèle
6.3.2
Choix de la dimension de l’espace latent
7
Modèle à variables latentes classique
7.1
Définition
7.2
Vraisemblance
7.3
Algorithme EM
7.4
Modèles graphiques
7.4.1
Modèle graphique dirigé
7.4.2
Modèle graphique non dirigé
7.4.3
Graphe moral
8
Modèle à blocs stochastiques
8.1
Définition
8.2
Vraisemblance
8.3
Approximation variationnelle
8.4
Algorithme VEM
8.5
Sélection de modèle
8.6
TP – SBM
Exercice 1. Simulation d’un SBM
Package
sbm
Exercice 2
References
Published with bookdown
Analyse statistique de graphes
Chapitre 6
Modèles de graphes aléatoires – Partie 2
On présente ici trois modèles de graphes aléatoires.