Thomas Pontoizeau

J'ai soutenu ma thèse le 4 juin 2018 à l'Université Paris-Dauphine au laboratoire du LAMSADE sous la supervision du professeur Cristina Bazgan.

Cette thèse étudie la détection de communautés dans le contexte 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 représentent les relations entre les membres. En particulier, j'étudie trois différentes définitions de communauté. D'abord, une structure en communautés peut être définie par une partition des sommets telle que tout sommet a une plus grande proportion de voisins dans sa partie que dans toute autre partie. Ensuite, une communauté peut être vue comme un sous graphe tel que tout couple de sommets sont à distance 2 dans ce sous graphe. Enfin, dans le contexte des sites de rencontre, je propose d'étudier une définition de communauté potentielle dans le sens où les membres de la communauté ne se connaissent pas, mais sont liés par des connaissances communes. Pour ces trois définitions, j'étudie la complexité computationnelle et l'approximation de problèmes liés à l'existence ou la recherche de telles communautés dans les graphes.

Mots-clés: Optimisation combinatoire, Complexité, Approximation, Algorithmique, Graphes.

Mon CV est disponible ici.

Les slides de ma soutenance sont disponibles ici.

Ma thèse est disponible ici.

Contact

Email

Address