MDL: Maximum Density Label-Cut Graph Partitioning
Zhanzhe Li, Ningchao Ge, Haiwen Chen, Kaiming Xiao, Peng Peng, Hongbin Huang · 2024
As the scale of graph data increases, the performance bottleneck problem of centralized graph data management is becoming increasingly prominent. Therefore, it is common to divide a massive graph dataset into several data partitions. To achieve distributed workload and improve efficiency through distributed graph management. The typical graph partitioning method is to minimize the cutting of edges and points, or to maximize the tightness of the structure within the partition. However, these methods are difficult to avoid cross partition same label query connections (i.e. inter partition connections) in the context of multi-label graph data queries. Toward this end, we propose a Maximum Density Label Partitioning (MDL) based on labels. Our method allows for independent query evaluation of more identical labels without inter partition connections. A heuristic greedy algorithm is proposed to address the challenge that maximum density label partitioning is an NP-hard problem. A large number of experiments conducted on various synthetic and real graph datasets have shown that the proposed method can significantly avoid inter partition connections and produce good performance.