Comparative Analysis of Graph Partitioning Strategies for Enhancing Scalability and Performance in Distributed Graph Databases

Graph partitioning is a critical enabler of scalability in distributed graph databases, impacting load balancing, communication overhead, and query performance. This paper presents a comparative analysis of four partitioning strategies—Random Vertex, Metis-based, Random Edge, and HDRF—spanning both edge-cut and vertex-cut paradigms. Each approach is evaluated on synthetic and real-world datasets for metrics such as edge cut, replication factor, load balance, latency, and throughput. Our evaluation framework simulates distributed OLTP/OLAP query workloads on a prototype graph database cluster. Results show that while Metis achieves optimal partition quality for static, balanced graphs, HDRF provides superior performance and scalability for dynamic, power-law networks. The experiments reveal important trade-offs between partitioning complexity and runtime performance across different graph structures. This work contributes a scalable benchmarking environment, a set of representative partitioning algorithms, and statistically grounded insights to guide practitioners in choosing the appropriate strategy for specific workload and graph characteristics.