MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEOutils algorithmiques de détection de communautés dans les grands graphes
par Mikaila Tokoworou
| Date : | 22/03/11 | | Time : | 10:30 | | Location : | Galois Coriolis |
L'analyse et la compréhension
des réseaux sociaux occupent de plus en plus une place importante dans le
domaine industriel. En effet afin de pouvoir offrir des services innovants, mieux ciblés et adaptés aux besoins, les entreprises se penchent sur les
problématiques des réseaux sociaux. Ainsi la détection des communautés dans les graphes de ces réseaux est un sujet d'actualité aussi bien théorique que
pratique. Nous nous attaquons à l'aspect algorithmique de ce problème qui peut être vu comme un cas de clustering de graphe. Etant donné que la détection de communautés n'a d'intérêt que pour les graphes de très grande taille (graphes sociaux, graphes du web), une attention particulière est accordée à la complexité des algorithmes et la mémoire nécessaire.
Nous présentons quelques
algorithmes basés sur des méthodes combinatoires afin de pouvoir détecter les parties les plus denses du graphe, donc les communautés. Notre première méthode consiste à calculer rapidement le facteur d'arbre d'un graphe qui représente la densité maximale des ses sous graphes. Nous présentons aussi un algorithme pour maximiser la fonction de modularité (mesurant la qualité des découpages de graphe) par des méthodes spectrales de bissection. Nous présentons
finalement les autres approches de détection de communautés à savoir les
méthodes d'agglomération successive et de séparation successive.
Page des séminaires
| 
