EdMot : Une Approche d'Amélioration des Arêtes pour la Détection de Communautés Sensibles aux Motifs

La détection de communautés dans les réseaux est un sujet de recherche actuel en analyse de réseaux. Bien qu’un grand nombre de méthodes aient été proposées pour la détection de communautés, la plupart ne prennent en compte que la structure d’ordre inférieur du réseau, au niveau des nœuds et des arêtes individuels. Par conséquent, elles échouent à capturer les caractéristiques d’ordre supérieur au niveau de motifs de sous-graphes denses de petite taille, tels que les motifs. Récemment, certaines méthodes d’ordre supérieur ont été développées, mais elles se concentrent généralement sur des hypergraphes basés sur des motifs, supposés être des graphes connexes. Or, cette hypothèse ne peut pas être garantie dans certains réseaux du monde réel. En particulier, l’hypergraphe peut devenir fragmenté, c’est-à-dire qu’il peut contenir un grand nombre de composantes connexes ainsi que des nœuds isolés, même si le réseau d’origine est lui-même connexe. Ainsi, les méthodes d’ordre supérieur existantes souffrent fortement de ce problème de fragmentation, car dans ces approches, les nœuds non connectés dans l’hypergraphe ne peuvent pas être regroupés ensemble, même s’ils appartiennent à la même communauté. Pour résoudre ce problème de fragmentation, nous proposons une méthode appelée EdMot (Edge enhancement approach for Motif-aware community detection). L’idée principale repose sur les étapes suivantes : tout d’abord, un hypergraphe basé sur des motifs est construit, puis les K plus grandes composantes connexes de cet hypergraphe sont partitionnées en modules. Ensuite, la structure de connectivité à l’intérieur de chaque module est renforcée en construisant un ensemble d’arêtes permettant de former une clique à partir de chaque module. En s’appuyant sur ce nouvel ensemble d’arêtes, la structure de connectivité initiale du réseau d’entrée est améliorée afin de générer un nouveau réseau réarrangé, permettant ainsi d’exploiter efficacement la structure d’ordre supérieur basée sur les motifs tout en résolvant de manière adéquate le problème de fragmentation de l’hypergraphe. Enfin, ce réseau réarrangé est partitionné pour obtenir la structure de communauté d’ordre supérieur.