LI Yifan
Direction de recherche : Cédric DU MOUZA
Co-encadrement : CONSTANTIN Camélia
Partitionnement de grands graphes
Dans cette thèse nous étudions un problème fondamental, le partitionnement de graphe, dans le contexte de la croissance rapide des données, le volume des données continues à augmenter, allant des réseaux sociaux à l'internet des objets. En particulier, afin de vaincre les propriétés intraitables existant dans de nombreuses graphies, par exemple, la distribution des degrés en loi de puissance, nous appliquons un nouveau mode pour coupe de sommet, à la place de la méthode traditionnelle (coupe de bord), ainsi que pour assurer une charge de travail équilibrée et raisonnablement dans le traitement de graphe distribué.
En outre, pour réduire le coût de communication inter-partitions, nous proposons une méthode de partition de bord basée sur les blocs, qui peut explorer efficacement les structures graphiques sous-jacentes au niveau local. , afin d'optimiser l'exécution de l'algorithme de graphe. Par cette méthode, le temps d'exécution et des communications généraux peuvent être considérablement réduits par rapport aux approches existantes.
Les challenges qui se posent dans les grands graphiques comprennent également leur grande variété. Comme nous le savons, la plupart des applications graphiques au monde réel produisent des ensembles de données hétérogènes, dans lesquels les sommets et / ou les arêtes peuvent avoir des différents types ou des différentes étiquettes. De nombreuses algorithmes de fouille de graphes sont également proposés avec beaucoup d'intérêt pour les attributs d'étiquette. Pour cette raison, notre travail est étendu aux graphes de multicouches en prenant en compte la proximité des arêtes et la distribution des étiquettes lors du processus de partitionnement. En fin de cette thèse, Nous démontré à la ses performances exceptionnelles sur les ensembles de données du monde réel.
Soutenance : 15/12/2017
Membres du jury :
Prof. PUCHERAL Philippe, SMIS, UVSQ [Rapporteur]
Prof. VODISLAV Dan, ETIS, Univ. Cergy-Pontoise [Rapporteur]
Prof. AMANN Bernd, Lip6, UPMC
Prof. COHEN Sarah, LRI, Univ. Paris-Sud
Dr. CONSTANTIN Camelia, Lip6, UPMC
Dr. DU MOUZA Cedric, CEDRIC, CNAM
Publications 2015-2019
-
2019
- C. Constantin, C. Du Mouza, Y. Li : “A Label-based Edge Partitioning for Multi-Layer Graphs”, 52nd Hawaii International Conference on System Sciences (HICSS 2019), Maui, Hawaii, United States, pp. 2216-2225, (HICSS) (2019)
-
2017
- Y. Li : “Edge partitioning of large graphs”, thèse, soutenance 15/12/2017, direction de recherche Du mouza, Cédric, co-encadrement : Constantin, Camélia (2017)
- C. Constantin, Y. Li, C. Du Mouza : “Un partitionnement d’arêtes à base de blocs pour les algorithmes de marches aléatoires dans les grands graphes sociaux”, Revue des Sciences et Technologies de l'Information - Série ISI : Ingénierie des Systèmes d'Information, vol. 22 (3), pp. 89-113, (Lavoisier) (2017)
- Y. Li, C. Constantin, C. Du Mouza : “SGVCut: A Vertex-Cut Partitioning Tool for RandomWalks-based Computations over Social Network graphs”, International Conference on Scientific and Statistical Database Management, SSDBM, Chicago, United States, pp. 39:1-39:4 (2017)
-
2016
- Y. Li, C. Constantin, C. Du Mouza : “A Block-Based Edge Partitioning for Random Walks Algorithms over Large Social Graphs”, 32e Conférence sur la Gestion de Données - BDA2016, Poitiers, France (2016)
- Y. Li, C. Constantin, C. Du Mouza : “A Block-Based Edge Partitioning for Random Walks Algorithms over Large Social Graphs”, Web Information Systems Engineering – WISE 2016, Shanghai, China, pp. 275-289 (2016)
-
2015
- Y. Li : “Scalable Approaches for Recommendation in Social Networks”, BDA2015, Toulon, France (2015)