Abstract FR:

Dans de nombreux contextes, des ensembles d'entités en relation peuvent être modélisés par des graphes, dans lesquels les entités individuelles sont représentées par des sommets et les relations entre ces entités par des liens. Ces graphes, que nous appellerons "graphes de terrain", peuvent être rencontrés dans le monde réel dans différents domaines tels que les sciences sociales, l'informatique, la biologie, le transport, la linguistique, etc. La plupart des graphes de terrain sont composés de sous-graphes denses faiblement inter-connectés appelés "communautés" et de nombreux algorithmes ont été proposés afin d'identifier cette structure communautaire automatiquement. Nous nous sommes intéressés dans cette thèse aux problèmes des algorithmes de détéction de communautés, notamment leur non-déterminisme et l'instabilité qui en découle. Nous avons présenté une méthodologie qui tire parti de ce non- déterminisme afin d'améliorer les résultats obtenus avec les techniques actuelles de détection de communautés. Nous avons proposé une approche basée sur le concept de communautés fortes ou "coeurs de communautés" et nous avons montré l'amélioration apportée par notre approche en l'appliquant à des graphes réels et artificiels. Nous avons aussi étudié la structure des coeurs des graphes aléatoires et nous avons montré qu'à la différence des algorithmes classiques de détection de communautés qui peuvent trouver des partitions en communautés dans des graphes n'ayant pourtant aucune structure communautaire intrinsèque, notre approche indique clairement l'absence de structure communautaire dans les graphes aléatoires et permet en ce sens de distinguer les graphes aléatoires des graphes réels. Nous avons étudié également l'évolution des coeurs dans des réseaux dynamiques via une dynamique simulée simple et contrôlable ainsi qu'une dynamique réelle. Nous avons montré que les coeurs sont beaucoup plus stables que les communautés obtenues par les techniques actuelles de détection de communautés et que notre approche peut donc pallier les défauts des méthodes stabilisées qui ont été proposées récemment.