DHPV: a distributed algorithm for large-scale graph partitioning

Journal of Big Data

Moez Krichen¹  Ismail Assayad²  Wilfried Yves Hamilton Adoni³  Abdeltif El byed³  Tarik Nahhal³ 

[1] Faculty of CSIT, Albaha University, Al Bahah, Saudi Arabia;ReDCAD Laboratory, University of Sfax, Sfax, Tunisia;LIMSAD Laboratory, ENSEM, Hassan II University of Casablanca, Casablanca, Morocco;LIMSAD Laboratory, Faculty of sciences, Hassan II University of Casablanca, Casablanca, Morocco;

关键词: Big graph;    Large-scale networks;    k-Partition;    Graph partitioning algorithms;    Distributed computing;    GraphX;   

DOI  :  10.1186/s40537-020-00357-y

来源: Springer

【 摘 要 】

Big graphs are part of the movement of “Not Only SQL” databases (also called NoSQL) focusing on the relationships between data, rather than the values themselves. The data is stored in vertices while the edges model the interactions or relationships between these data. They offer flexibility in handling data that is strongly connected to each other. The analysis of a big graph generally involves exploring all of its vertices. Thus, this operation is costly in time and resources because big graphs are generally composed of millions of vertices connected through billions of edges. Consequently, the graph algorithms are expansive compared to the size of the big graph, and are therefore ineffective for data exploration. Thus, partitioning the graph stands out as an efficient and less expensive alternative for exploring a big graph. This technique consists in partitioning the graph into a set of k sub-graphs in order to reduce the complexity of the queries. Nevertheless, it presents many challenges because it is an NP-complete problem. In this article, we present DPHV (Distributed Placement of Hub-Vertices) an efficient parallel and distributed heuristic for large-scale graph partitioning. An application on a real-world graphs demonstrates the feasibility and reliability of our method. The experiments carried on a 10-nodes Spark cluster proved that the proposed methodology achieves significant gain in term of time and outperforms JA-BE-JA, Greedy, DFEP.

【 授权许可】

CC BY