Communautés et anonymisation dans les graphes
10/12/2021 à 14h42
M. Pierre CAZALS présente ses travaux en soutenance le 10/12/2021 à 14h42
À l'adresse suivante : Place du Maréchal de Lattre de Tassigny 75016 Paris - Salle A701
En vue de l'obtention du diplôme : Doctorat enInformatique
La soutenance est publique
Titre des travaux
Communautés et anonymisation dans les graphes
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
Mme Cristina BAZGAN
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| Mme Cristina BAZGAN | Professeur des universités | UNIVERSITE PARIS DAUPHINE - PSL | Directrice de thèse |
| M. Eric ANGEL | Professeur des universités | Université d'Évry Val d'Essonne | Rapporteur |
| M. Cédric BENTZ | Maître de conférences | Conservatoire National des Arts et Métiers | Rapporteur |
| Mme Nadia BRAUNER | Professeur des universités | Université Grenoble Alpes | Examinatrice |
| M. Florent FOUCAUD | Maître de conférences | IUT Clermont Auvergne | Examinateur |
Résumé
Dans cette thèse nous étudions la complexité algorithmique de problèmes d'optimisation lié à l'étude des réseaux sociaux. Un réseau social peut être modélisé par un graphe dans lequel les sommets représentent les membres et les arêtes leurs relations. Nous nous intéressons à deux problématiques différentes, l'anonymisation du graphe et la détection de communautés. L'anonymisation de graphes a déjà été étudiée et de nombreuses formalisations du concept ont été proposées sont forme de propriétés. Pour les satisfaire il faut souvent transformer le graphe initial. On sera alors attentif à fournir des algorithmes qui minimisent son altération lors du processus d'anonymisation. Dans cette thèse nous mesurons l'altération subie par le nombre de transformations élémentaires effectuées sur le graphe. Nous proposons d'étudier la minimisation du nombre de rotations d'arêtes nécessaires sur un graphe afin qu'il respecte une propriété d'anonymisation donnée dans différents cas de figure. Des travaux empiriques ont déjà été publié et nous nous sommes attaché à les poursuivre sur l'angle de de la complexité et de l'approximation. L'utilisation de ce nouvel opérateur a permis des résultats théorique négatifs ainsi que positifs plus encourageant qu'avec les précédents. Une communauté est un groupe social partageant un espace, des biens ou des intérêts communs. Cela se reflète sur le graphe par des fortes connexions entre ses individus. Il existe de nombreuses manière de caractériser les communautés et nous nous sommes concentrés sur les définitions basées sur l'optimisation d'une fonction de densité. Plus précisément nous étudions un problème de partition en sous-graphes denses où l'on cherche à maximiser une fonction de densité globale. Nous poursuivons les premiers travaux entrepris sur ce sujet et proposons des résultats plus approfondis. Pour ces deux problèmes nous avons étudié différentes classes dont des classes de graphes peu dense, relativement similaire aux réseaux sociaux.