Dans le contexte des réseaux complexes, la structure communautaire du réseau devient un sujet important pour plusieurs domaines de recherche. Les communautés sont en général vues comme des groupes intérieurement denses. La détection de tels groupes offre un éclairage intéressant sur la structure du réseau. Par exemple, une communauté de pages web regroupe des pages traitant du même sujet. La définition de communautés est en général limitée à une partition de l'ensemble des nœds. Cela exclut par définition qu'un nœd puisse appartenir à plusieurs communautés, ce qui pourtant est naturel dans de nombreux (cas des réseaux sociaux par exemple). Une autre question importante et sans réponse est l'étude des réseaux et de leur structure communautaire en tenant compte de leur dynamique. Cette thèse porte sur l'étude de réseaux dynamiques et la détection de communautés recouvrantes. Nous proposons deux méthodes différentes pour la détection de communautés recouvrantes. La première méthode est appelée optimisation de clique. L'optimisation de clique vise à détecter les nœds recouvrants granulaires. La méthode de l'optimisation de clique est une approche à grain fin. La seconde méthode est nommée détection floue (fuzzy detection). Cette méthode est à grain plus grossier et vise à identifier les groupes recouvrants. Nous appliquons ces deux méthodes à des réseaux synthétiques et réels. Les résultats obtenus indiquent que les deux méthodes peuvent être utilisées pour caractériser les nœds recouvrants. Les deux approches apportent des points de vue distincts et complémentaires. Dans le cas des graphes dynamiques, nous donnons une définition sur la relation entre les communautés à deux pas de temps consécutif. Cette technique permet de représenter le changement de la structure en fonction du temps. Pour mettre en évidence cette relation, nous proposons des diagrammes de lignage pour la visualisation de la dynamique des communautés. Ces diagrammes qui connectent des communautés à des pas de temps successifs montrent l'évolution de la structure et l'évolution des groupes recouvrantes., Nous avons également appliquer ces outils à des cas concrets.

Dans le contexte des réseaux complexes, la structure communautaire du réseau devient un sujet important pour plusieurs domaines de recherche. Les communautés sont en général vues comme des groupes intérieurement denses. La détection de tels groupes offre un éclairage intéressant sur la structure du réseau. Par exemple, une communauté de pages web regroupe des pages traitant du même sujet. La définition de communautés est en général limitée à une partition de l’ensemble des nœds. Cela exclut par définition qu’un nœd puisse appartenir à plusieurs communautés, ce qui pourtant est naturel dans de nombreux (cas des réseaux sociaux par exemple). Une autre question importante et sans réponse est l’étude des réseaux et de leur structure communautaire en tenant compte de leur dynamique. Cette thèse porte sur l’étude de réseaux dynamiques et la détection de communautés recouvrantes. Nous proposons deux méthodes différentes pour la détection de communautés recouvrantes. La première méthode est appelée optimisation de clique. L'optimisation de clique vise à détecter les nœds recouvrants granulaires. La méthode de l'optimisation de clique est une approche à grain fin. La seconde méthode est nommée détection floue (fuzzy detection). Cette méthode est à grain plus grossier et vise à identifier les groupes recouvrants. Nous appliquons ces deux méthodes à des réseaux synthétiques et réels. Les résultats obtenus indiquent que les deux méthodes peuvent être utilisées pour caractériser les nœds recouvrants. Les deux approches apportent des points de vue distincts et complémentaires. Dans le cas des graphes dynamiques, nous donnons une définition sur la relation entre les communautés à deux pas de temps consécutif. Cette technique permet de représenter le changement de la structure en fonction du temps. Pour mettre en évidence cette relation, nous proposons des diagrammes de lignage pour la visualisation de la dynamique des communautés. Ces diagrammes qui connectent des communautés à des pas de temps successifs montrent l’évolution de la structure et l'évolution des groupes recouvrantes., Nous avons également appliquer ces outils à des cas concrets. / In complex networks, the notion of community structure refers to the presence of groups of nodes in a network. These groups are more densely connected internally than with the rest of the network. The presence of communities inside a network gives an insight on network structural properties. For example, in social networks, communities are based on common interests, location, hobbies.... Generally, a community structure is described by a partition of the network nodes, where each node belongs to a unique community. A more reasonable description seems to be overlapping community structure, where nodes are allowed to be shared by several communities. Moreover, when considering dynamic networks whose interactions between nodes evolve in time, it appears crucial to consider also the evolution of the intrinsic community structure. This thesis focus on mining dynamic community evolution and overlapping community detection. We have proposed two distinct methods for overlapping community detection. The first one named clique optimization and the second one called fuzzy detection. Our clique optimization aims to identify granular overlaps and it is a fine grain scale approach. Our fuzzy detection is at a coarser grain scale with the strategy of identifying modular overlaps. Their applications in synthetic and real networks indicate that both methods can be used for characterizing overlapping nodes but in distinct and complementary views. We also propose the definition of predecessor and successor in mining community evolution. Such definition describes the relationship between communities at different time steps. We use it to detect community evolution in dynamic networks and show how modular overlaps evolve over time. A visualization tool called lineage diagrams is used to show community evolution by connecting communities in relationship of predecessor and successor. Several cases are studied.

L’analyse des réseaux sociaux a conduit à la découverte d’une propriété très intéressante : ces réseaux se caractérisent par l’existence de zones de forte densité constituées d’éléments fortement connectés entre eux. Ces zones appelées "communautés", évoluent au cours du temps suivant la dynamique des acteurs sociaux et de leurs interactions. L’identification de ces communautés offre un éclairage intéressant sur la structure du réseau et permet de suivre leur évolution au fil du temps. Bien que ce problème ait donné lieu à de très nombreux travaux ces dernières années, la détection des communautés dynamiques reste encore un problème ouvert et aucune solution entièrement satisfaisante n’est encore proposée. Dans ce travail, nous proposons une approche multi-agents pour la détection des communautés dans les réseaux sociaux dynamiques. Les entités de notre approche observent l’évolution du réseau, et en conséquence, elles adaptent en temps réel le graphe représentant le réseau et elles engendrent les modifications adéquates sur les communautés précédemment détectées. Cette approche permet de modéliser le réseau par un graphe dynamique qui s’adapte en fonction l’évolution observée dans le réseau. Pour cette modélisation, plusieurs aspects du réseau sont intégrés : la structure topologique du graphe, la similarité sémantiques des membres sociaux et la communication entre eux. Cette modélisation se base sur le concept d’homophilie et sur une stigmergie à base des phéromones. Afin d’étudier les performances de l’approche proposée, nous l’avons appliquée sur un ensemble très varié de graphes réels et artificiels. Les résultats ont été suffisamment satisfaisants et montrent la bonne performance de notre modèle. / Analysis of social networks has led to the discovery of a very interesting property : these networks are characterized by the existence of areas with high density composed of highly interconnected elements. These areas called "communities", evolve over time according to the dynamic of social members and their interactions. The identification of these communities offers an interesting light on the network structure and it allows to track their progress over time. Although this problem has been the subject of numerous studies in recent years, the detection of dynamic communities remains an open problem and no fully satisfactory solution has yet been proposed. In this work, we propose a multi-agent approach for the detection of communities in dynamic social networks. The entities of our approach observe the evolution of the network and consequently they adapt in real time the graph representing the network and they generate the appropriate changes on previously identified communities. This approach allows to model the network by a graph that dynamically adapts according to the evolution of the network. For this modeling, several network’s aspects are integrated: the topological structure of the graph, the semantic similarity of social members and the communication between them. This modeling is based on the concept of homophily and a pheromone based stigmergy. In order to study the performances of the proposed approach, we applied it to a divers set of real and artificial graphs. The results were satisfactory enough and show the good performance of our model.