Approche de détection de communautés chevauchantes dans les réseaux bipartis

Abstract

La perception actuelle de la notion de réseau a permis de réaliser des progrès significatifs pour la compréhension des systèmes complexes. L'une des caractéristiques les plus pertinentes des réseaux représentant des systèmes réels est l’existence de zones plus densément connectées que d’autres. Ces zones sont habituellement appelées communautés. De nombreux algorithmes ont été conçus pour découvrir les structures des communautés dans des réseaux. Ces algorithmes sont pour la plupart dédiés pour détecter des communautés disjointes. Très peu d’entre eux sont destinés à découvrir des communautés chevauchantes, particulièrement les réseaux bipartis, n’ont presque pas été explorés pour la détection de ce type de communautés. Dans cette thèse, nous présentons une approche qui consiste à former des communautés chevauchantes mixtes significatives dans des réseaux bipartis. Cette approche est fondée sur une double optimisation de la modularité réseau. À ce titre, nous proposons deux algorithmes. Le premier est un algorithme évolutionnaire dédié à une optimisation globale de la modularité de Newman sur le graphe-arête. Le second algorithme est appliqué sur la décomposition de noeuds résultant du processus évolutionnaire. Ce deuxième algorithme est destiné à optimiser localement la modularité de Mancoridis en prenant en considération l’aspect sémantique. La prise en compte de la sémantique contribue à détecter des communautés cohérentes et significatives. Notre approche ne nécessite aucune connaissance préalable du nombre de communautés recherchées dans le réseau. Nous validons notre approche sur deux ensembles de données : un groupe de réseaux synthétiques et un réseau du monde réel.