Research On Graph Partitioning Method For Social Network

Recently,with the rapid development of the Internet,more and more people use the Internet for social activities,which makes the scale of social networks expand rapidly.By analyzing and calculating social networks,it can not only provide great convenience to the social life of most people,but also provide solutions to various problems in society.Since the scale of social network graph data is very large,its graph computation needs to be performed in a distributed cluster environment.The most important task of graph computing in a distributed environment is to segment the graph,and then use the resource scheduling algorithm to allocate the segmented subgraphs to each computing node in the distributed cluster to perform graph computation.Therefore,the graph segmentation algorithm and resource scheduling algorithm used in graph computation for social network graphs are very important,which can directly affect the speed and quality of graph computation.There are many excellent streaming graph segmentation algorithms and resource scheduling algorithms in the homogeneous cluster environment.However,most of the current clusters are heterogeneous,that is,the computing power and communication cost of each computing node in the cluster are different.Therefore,for the graph segmentation and resource scheduling of social network graphs in a heterogeneous cluster environment,this thesis proposes a heterogeneous-aware high-latitude priority graph segmentation algorithm and a heterogeneous-aware resource dynamic scheduling algorithm.Among them,the heterogeneous-aware high-latitude priority graph segmentation algorithm takes the computing power and communication cost of cluster nodes into account on the basis of considering load balance and minimizing the replication factor;in the heterogeneous-aware resource dynamic scheduling algorithm,Combine the remaining memory and resources of each node in the cluster to allocate the most suitable computing resources for the subgraph.Finally,through a series of experiments,it is demonstrated that using the graph segmentation algorithm proposed in this thesis to perform graph segmentation on the social network graph data set,and then using the resource scheduling algorithm proposed in this paper to perform graph computing can obtain better performance than the experimental control group algorithm.