Fouille et Analyse de Grands Graphes Dynamiques : Application dans le clustering de graphes

Recently, graph clustering has become one of the most used techniques to understand structures and inherent knowledge in graph data. This trend progressively attracts the attention of companies and the research community. For example, in the industrial field, it is used for multiple applications like social networks (e.g. Facebook), where communities can be modeled as clusters in a graph. As for collaborative networks (e.g. DBLP), a cluster can represent a team with similar research interests. Several works have been established where their proposed approaches are based on advanced algorithms mainly graph clustering algorithms and modularity based-ones. The former has demonstrated their efficiency notably by providing supplementary information about clusters in a list. Besides, they can identify hub and outlier vertices. Despite their importance, the utility of such algorithms is limited by their high complexity particularly when dealing with Big and dynamic graphs. This limitation motivates us to propose new algorithms with higher performances in our thesis. For more details, our contributions can be summarized in the following points: (1) carrying out of a comparative study between the most popular Big Data platforms (2) proposing a distributed algorithm called DSCAN for large graphs clustering and (3) extending DSCAN to develop an incremental algorithm for dynamic and large graphs. A comparative study between our proposed algorithms and other baselines has shown their effectiveness and their scalability when dealing with large and dynamic graphsRécemment, le clustering de graphes est devenu l’une des techniques les plus utilisées pour comprendre les structures et les connaissances cachées dans les graphes. Le clustering de graphes vise principalement à détecter tous les sous graphes denses dans un graphe donné. Un tel traitement peut toucher de nombreuses applications. Plus précisément, dans les réseaux sociaux (par exemple Facebook), les groupes dans un graphe peuvent être considérés comme étant des communautés. Dans un réseau de collaboration (par exemple DBLP), un cluster peut être un groupe de chercheurs ayant des intérêts de recherche similaires. C’est dans ce contexte que se situe le travail de cette thèse, il consiste à traiter le clustering de grands graphes dynamiques où ce projet de thèse touche plusieurs aspects tels que, le volume massif de données, le traitement des flux des données en plus des mises à jour de graphes en temps réel. De ce fait, dans cette thèse trois contributions sont proposées. La première contribution consiste à effectuer une étude comparative aussi bien théorique que technique entre les plateformes les plus populaires de Big Data notamment : Hadoop, Spark, Samza et Flink. La deuxième contribution consiste à proposer un algorithme distribué pour le clustering de grands graphes. L’algorithme proposé se base sur le clustering structurel. Une étude comparative avec d’autres algorithmes similaires a été effectuée dont l’objectif de montrer l’efficacité de l’algorithme proposé. Les résultats expérimentaux relevés ont affirmé cette efficacité particulièrement dans le passage à l’échelle. La dernière contribution était de proposer un algorithme de clustering de graphes dynamiques. Dans cette contribution, un algorithme incrémental a été proposé pour combattre le problème de temps de calcule de graphes larges et dynamiques, puisque avec les autres algorithmes chaque mis à jour appliquée sur le graphe initial nécessite de refaire le clustering de le début. Une étude comparative entre l’algorithme proposé et d’autres algorithmes a montré l’efficacité de l’algorithme proposé