Abstract: “Existing graph partitioning algorithms rarely focus on the choice of the replicas. Most of them make use of random hashing to allocate vertices to partitions due to its convenience and simplicity. However, such random property may result in undesirable partitioning results with huge communication cost if many high degree vertices are being replicated. We address this problem and propose a greedy algorithm to minimize the number of replications of high degree vertices and at the same time minimize the replication factor by sorting the vertices before allocating them to different partitions. We compare our algorithm with one of the well performed existing graph partitioning algorithms, Powers hybrid-cut, and prove that our algorithm gives better results in most practical situations. Experimental results show that our algorithm gives much lower replication factor compared to Powers hybrid-cut algorithm generally in random graphs, power-law graphs and real-life graphs.”

Keywords: graph, partitioning, heuristic, replica, insert