Local Graph Partitioning For Large-scale Graph

Graph partitioning is a classical problem of graph data,and is widely used in different fields,such as distributed graph processing,community detection,image segmentation,and road planning.In graph partitioning algorithms,the vertices or edges in a graph are evenly partitioned into several subgraphs while minimizing the number of cut edges or vertices across subgraphs.However,with the increasing scale of real-world graphs,the local graph information and low memory consumption are essential for large-scale graph partitioning.Hence,three local graph partitioning algorithms are proposed for different types of graph data(i.e.,static graph,dynamic graph,and weighted graph).The contributions of this thesis are summarized as follows.(1)Existing static graph partitioning models require global graph information during the their partitioning,which is expensive in terms of time and memory for large-scale graphs.Therefore,a local graph edge partitioning model is defined,which considers only the local information,i.e.,a portion of a graph,instead of the entire graph,during partitioning.Moreover,an adaptive local graph edge partitioning algorithm LocalAGEP that combines two classical graph partitioning strategies by an adaptive method is proposed.A novel graph data storage method is also designed to optimize LocalAGEP memory consumption.Experiments show that LocalAGEP can obtain a higher edge graph edge partitioning quality based on local graph information and a lower memory consumption than the rival algorithms.(2)For a dynamic graph,the local partitioning process of each partition in the LGEP model is divided into Push and Pop stages to adjust the partitioned data according to the graph changes.Based on the improved model,a local dynamic graph edge partitioning algorithm LocalTGEP is proposed.In LocalTGEP,different graph partitioning strategies are adopted in the Push and Pop stages to improve the partitioning quality.Furthermore,a dynamic graph storage framework is designed to ensure that only a portion of graph data is stored in memory.Experiments demonstrate that LocalTGEP outperforms rival algorithms in terms of memory consumption,partitioning quality,and efficiency.(3)For a weighted graph,the local graph vertex partitioning model is firstly defined,and a local weighted graph edge partitioning algorithm,LocalWGVP,is then proposed based on this local model to obtain a weight-balanced partitioning outcome.In LocalWGVP,the vertices are divided into several levels according to the vertex weight,and the vertices in each level are evenly allocated into different partitions based on the local graph information.Experiments show that LocalWGVP can obtain loadbalanced weight graph partitioning results,where the vertex weight distribution of each partition is similar.Meanwhile,the memory consumption of LocalWGVP is lower than that of its baselines,which means LocalWGVP is suitable for large-scale weighted graph partitioning.