Research On Graph Partitioning On Distributed System

Graph is a data structure which commonly exists. At the same time, it is used in many fields, no matter in the Bioinformatics and Electricity nor the Social Network,which is booming in the modern society. In all these fields many structure could be abstracted to graphs of Data Structure. As the application of the graph is increasing, the scale of graph is becoming more and more large and amount of large scale graphs emerge at the same time. So how to partition the graph into different subgraph to reduce the information interaction is a work which is very important. How to partition in the distributed system effectively has become a important problem while the the single node algorithm couldn’t satisfy our requirement for the increasing scale of the graph.The existing algorithm almost stay in the basement of single node. Although the partition algorithm has matured, the research in distributed system is still weak. Some one has raise a lightweight streaming graph algorithm. The loader must make a decision about the location of each node as it is loaded. The purpose of this algorithm is to reduce compute time, but the result would be influenced by the heuristic method.In the real world,the graph is changing overtime. When the graph change, we hope that we could partition it effectively based on the result before nor partition the whole graph completely.So this paper presents an algorithm on distributed system. Firstly, we need to process the static graph.We need to choose some nodes as seeds, and then use KL greedy algorithm to partition the seeds. We will decide which partition the node is belong to base on the connection between the node and the partition. Because it is partitioned in distributed system, we need to take the balance into account and decide which partition is belong to. We need to take both the load balance and balance between partition into account for the partition which has many nodes. In this situation the partition which possess less nodes but has less connection with the node would get priority.And the graph is not stable in the real world, so we need to process the partition result as it changes. When the graph is changing dynamically, we will move the nodes base on the change to improve the partition. In this way, the result computed before could be used into the new partitioning. We send the nodes which need to be moved to the master node to decide the allocation strategy by the statistics and then move the nodes.This paper would take both the partition result and the time in simulation and to analysis the result of the experiment to prove the improvement of this algorithm.