Research On The Parallel Algorithm Of The Minimum Spanning Tree On Large Scale Graphs

As one of the most classic algorithm in graph theory, the Minimum Spanning Tree(MST) has drawn unfailing attention. Due to the properties of MST, it has been widely used in many fields, such as planning, network, medicine and so forth. Meanwhile, some complex graph algorithms based on the MST structure including clustering, classification and shortest path query have improved significantly in terms of efficiency and quality. However, with the rapid development of Internet, the scales of graphs have been becoming bigger and bigger. Large scale graphs which contain millions or even billions of vertices have been more common. Therefore, how to realize query processings and data mining algorithms on large scale graphs has become a problem to be solved urgently. In addition, because of the dynamic properties of large scale graphs, which means sometimes the topologies of graph may change, how to maintain results dynamically has also become one of the most attractive problems.This thesis proposes parallel MST algorithms and a MST dynamic maintenance algorithm to provide a solid foundation for the above problems.Firstly, this thesis puts forward an edge-drive parallel MST algorithm by the design concept of taking edges as center. Besides, there are some optimization techniques to improve the efficiency of the algorithm in this thesis, including distributed index, partition boosting, a sorting algorithm based on histogram and so on. We also implement the algorithm on different communication models and analyze its time complexity. Experiments verify the effectiveness of the algorithm as well as the efficiency of distributed index and the sorting algorithm.Secondly, our thesis proposes a vertex-drive parallel MST algorithm called PB and demonstrates the correctness of PB from the aspect of vertices as center. Moreover, our thesis presents the termination condition and index maitenancce strategy in PB algorithm. Later, we implement the whole process of PB algorithm on MapReduce and BSP framework respectively, including start job and loop job in detail. At the same time, our thesis also analyzes the time conplexity of PB algorithm over above frameworks. And then, our experiments prove the correctness, efficiency and scalability of PB algorithm.Finally, taking the dynamic property of graphs into consideration, this thesis defines five kinds of operations in dynamic graphs and puts forward a distributed dynamic maintenance algorithm of MST, which called MTBM. Meanwhile, our thesis proposes a repartition algorithm and a distributed MST construction algorithm in preprocessing. After preprocessing procedure, for all the opertaions, such as inserting, deteling and changing, we design corresponding and independent strategies in MTBM and analyze the cost model of MTBM algorithm. The experiments show the high reliabilty and efficiency of MTBM algorithm.In conclusion, our thesis lauches a series of studies for MST problem on large scale graphs. We present edge-driven parallel MST algorithm, vertex-driven parallel MST algorithm and a distributed dynamic maintenance algorithm of MST on large scale graphs. Our research work in this thesis, namely the MST structures of large scale graphs, provides an application foundation for other complex query processings and data mining algorithms.