Nouveaux algorithmes pour la détection de communautés disjointes et chevauchantes basés sur la propagation de labels et adaptés aux grands graphes.

Graphs are mathematical structures amounting to a set of nodes (objects or persons) in which some pairs are in linked with edges. Graphs can be used to model complex systems.One of the main problems in graph theory is the community detection problemwhich aims to find a partition of nodes in the graph to understand its structure.For instance, by representing insurance contracts by nodes and their relationship by edges,detecting groups of nodes highly connected leads to detect similar profiles and to evaluate risk profiles. Several algorithms are used as aresponse to this currently open research field.One of the fastest method is the label propagation.It's a local method, in which each node changes its own label according toits neighbourhood.Unfortunately, this method has two major drawbacks. The first is the instability of the method. Each trialgives rarely the same result.The second is a bad propagation which can lead to huge communities without sense (giant communities problem).The first contribution of the thesis is i) proposing a stabilisation methodfor the label propagation with artificial dams on edges of some networks in order to limit bad label propagations. Complex networks are also characterized by some nodes which may belong to several communities,we call this a cover.For example, in Protein–protein interaction networks, some proteins may have several functions.Detecting these functions according to their communities could help to cure cancers. The second contribution of this thesis deals with the ii)implementation of an algorithmwith functions to detect potential overlapping nodes .The size of the graphs is also to be considered because some networks contain several millions of nodes and edges like the Amazon product co-purchasing network.We propose iii) a parallel and a distributed version of the community detection using core label propagation.A study and a comparative analysis of the proposed algorithms will be done based on the quality of the resulted partitions and covers.Les graphes sont des structures mathématiques capables de modéliser certains systèmes complexes. Une des nombreuses problématiques liées aux graphes concerne la détection de communautés qui vise à trouver une partition en sommet d'un graphe en vue d'en comprendre la structure. A titre d'exemple, en représentant des contrats d'assurances par des noeuds et leurs degrés de similarité par une arête, détecter des groupes de noeuds fortement connectés conduit à détecter des profils similaires, et donc à voir des profils à risques.De nombreux algorithmes ont essayé de répondre à ce problème.Une des méthodes est la propagation de labels qui consiste à ce que chaque noeud puisse recevoir un label par un vote majoritaire de ses voisins. Bien que cette méthode soit simple à mettre en oeuvre, elle présente une grande instabilité due au non déterminisme de l'algorithme et peut dans certains cas ne pas détecter de structures communautaires.La première contribution de cette thèse sera dei) proposer une méthode de stabilisation de la propagation de labels tout en appliquant des barrages artificiels pour limiter les possibles mauvaises propagations. Les réseaux complexes ont également comme caractéristique que certains noeuds puissent appartenir à plusieurs communautés, on parle alors de recouvrements. C'est en ce sens que la seconde contribution de cette thèse portera sur ii) la création d'un algorithme auquel seront adjointes des fonctions d'appartenances pour détecter de possibles recouvrements via des noeuds candidats au chevauchement. La taille des graphes est également une notion à considérer dans la mesure où certains réseaux peuvent contenir plusieurs millions de noeuds et d'arêtes.Nous proposons iii) une version parallèle et distribuée de la détection de communautés en utilisant la propagation de labels par coeur. Une étude comparative sera effectuée pour observer la qualité de partitionnement et de recouvrement des algorithmes proposés