Scribd
Importer
14 vues3 pages

Introduction aux graphes et applications

Ce document présente un cours structuré sur les graphes, abordant des concepts fondamentaux, des théories avancées, des algorithmes classiques, et des applications modernes. Il inclut également des sections sur les réseaux de neurones graphiques et les bases de données orientées graphes, ainsi que des études de cas et projets pratiques. Chaque section est accompagnée d'objectifs d'apprentissage et de travaux dirigés pour renforcer les compétences des étudiants.

Transféré par

yangui rania
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
14 vues3 pages

Introduction aux graphes et applications

Ce document présente un cours structuré sur les graphes, abordant des concepts fondamentaux, des théories avancées, des algorithmes classiques, et des applications modernes. Il inclut également des sections sur les réseaux de neurones graphiques et les bases de données orientées graphes, ainsi que des études de cas et projets pratiques. Chaque section est accompagnée d'objectifs d'apprentissage et de travaux dirigés pour renforcer les compétences des étudiants.

Transféré par

yangui rania
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

1.

Introduction aux graphes


Objectifs :

 Poser les bases conceptuelles des graphes.


 Utilisations.

Contenu :

 Définitions : sommets, arêtes, graphes orientés / non orientés / pondérés / bipartis /


multigraphes.
 Représentations (matrice d’adjacence, listes d’adjacence, dictionnaires).
 Parcours : BFS, DFS.
 Applications simples : réseau social, chemin dans un labyrinthe.

TD :

 Construire différents graphes et leurs représentations.


 Exercices de parcours BFS/DFS manuels.

2. Théorie avancée des graphes


Objectifs :

 Approfondir les propriétés théoriques.


 Préparer le terrain pour les algorithmes avancés.

Contenu :

 Connexité et composantes fortement connexes.


 Graphes eulériens (théorème d’Euler), graphes hamiltoniens.
 Coloration de graphes et nombre chromatique.
 Arbres : propriétés, codage de Prüfer.

TD :

 Vérification d’un graphe eulérien/hamiltonien.


 Exercices de coloration de graphes.

3. Algorithmes fondamentaux sur les graphes


Objectifs :

 Étudier les grands algorithmes classiques.


 Comprendre leurs applications et complexités.
Contenu :

 Chemins : Dijkstra, Bellman-Ford, Floyd-Warshall.


 Arbres couvrants : Prim, Kruskal.
 Flots : Ford-Fulkerson, Edmonds-Karp.

TD/TP :

 Implémentation en Python avec NetworkX.


 Étude d’un graphe de transport (calcul shortest path, min spanning tree).

4. Applications modernes des graphes


Objectifs :

 Montrer l’importance des graphes dans les réseaux complexes (ex : SM).
 Étudier des mesures et détection de communautés.

Contenu :

 Réseaux complexes (loi de puissance, petit monde).


 Centralité : degré, proximité, intermédiarité, vecteur propre.
 Détection de communautés : Girvan-Newman, Louvain.
 Applications : réseaux sociaux, biologie, web.

TD/TP :

 Analyse d’un dataset réseau social avec NetworkX.


 Identification de communautés et nœuds influents.

5. Graph Neural Networks


Objectifs :

 Introduire les modèles d’apprentissage profond appliqués aux graphes.

Contenu :

 Représentation de graphes pour le machine learning.


 Idée de convolution sur graphe.
 GCN (Graph Convolutional Networks).
 Applications : classification de nœuds, prédiction de liens, réseaux moléculaires.

TP :

 Exemple avec PyTorch Geometric ou DGL (classification de nœuds sur Cora dataset).

6. Bases de données orientées graphes et Neo4j


Objectifs :

 Découvrir les graph databases.


 Apprendre Cypher et explorer Neo4j.

Contenu :

 Modèle Neo4j : nœuds, relations, propriétés.


 Cypher : CREATE, MATCH, RETURN, WHERE, shortestPath().
 Neo4j Graph Data Science (centralité, communautés).
 Applications : recommandation, analyse de fraude, réseaux sociaux.

TP :

 Installation Neo4j Desktop ou AuraDB.


 Chargement d’un dataset (IMDB, Game of Thrones, réseau social).
 Requêtes Cypher (requêtes simples puis avancées).
 Analyse de communautés avec GDS.

7. Études de cas et projets


Objectifs :

 Synthétiser les acquis.


 Appliquer la théorie à un mini-projet de recherche.

Contenu :

 Étude de datasets réels :


o Réseaux sociaux (Twitter, Facebook).
o Réseaux de transport/logistique.
o Réseaux biologiques (protéines, gènes).

Projet final :

 Analyse de graphe réel avec Python/Neo4j.

Vous aimerez peut-être aussi