Supervision : Cédric DU MOUZA

Co-supervision : CONSTANTIN Camélia

Edge partitioning of large graphs

In this thesis, we focus on the fundamental problem of graph partitioning, in the context of unexpectedly fast growth of data sources, ranging from social networks to internet of things. Based on the topological properties of real large graphs, e.g. power-law degree distribution, and on recent results which prove that vertex-cut partitioning provides better balanced workload and performances when processing algorithms on graphs, we propose a block-based edge partition method which can efficiently explore the locality underlying graphical structures to enhance the execution of graph algorithm and to reduce the inter-partition communication cost.
Another challenge with large graphs is their high-variety. Most real life graph applications produce heterogenous datasets, in which the vertices and/or edges which may present different types or labels. For this reason, our work is extended to multi-layer graphs with taking into account the edges closeness and labels distribution during partitioning process. Our experiments over real-world datasets demonstrate the good behavior of our proposal.

2015-2019 Publications

• 2019
  • C. Constantin, C. Du Mouza, Y. Li : “A Label-based Edge Partitioning for Multi-Layer Graphs”, 52^nd 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”, thesis, defence 12/15/2017, supervision Du mouza, Cédric, co-supervision : 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”, 32^e 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)