Research On Partition Techniques For Large Scale Graph Based On Triangle

Graph is a common data model which is used to describe the relationshipbetween entities.Graph structure is generallyapplicable.In the real world,manysystems can be converted into the corresponding graph model to study.With the Largesocial network,Literature citations network,Biological Information Network and otheremerging large-scalenetworks appearing,the demand of large-scale processing hasbecome increasingly urgent.We usuallyneed to process the large-scale graph inparallel.The connectivity features of graph data lead to strong coupling calculationprocessingwhich restricts the efficiency of parallel processing.Toprocess thelarge-scale graphs efficiently in parallel,we need an effective method of graphpartitioning to reduce the coupling calculation.Many graph partitioning algorithms have some limitations when they are facedwith the large-scale graphs.Some of them havepartition poor results. Some of themhave low operating efficiency which can not be applied to a large-scale graph.In theface of these problems,this paper presents two graph partitioning methods:Triangle-basedEdge Value Estimate Graph Partition Method andTriangle-basedHeuristic DFS Encoding Graph Partition Method.Triangle-basedEdge Value Estimate Partition Method first uses the advancedtriangle to setan initial value to the edges of the graph,and we use the values ofneighbor edgesto estimate the value of the edge accurately by iteration. Afterestimating the value of the edge,we use it as the standard for graphefficientpartitioning.Finally, we adjust the size of the split subgraphs to achieve thebest results.This method uses a limited number of iterationstoreceive the standard forgraph partitioning which is instead of the previous complex computingedgebetweenness.The partition results are satisfactory.When the dense subgraph includes a large number of vertices and the degree ofmost vertices are large, thealgorithm complexity of the iteration processof the abovemethod is not good. We research the iteration process of the above method and propose a new method called Triangle-based Heuristic DFS Encoding Graph PartitionMethod.The new method uses triangulation to define the similarity betweenvertices.Then we use the similarity between vertices to make the heuristic DFSencode process to determinethe value of each edge.After obtainthe value of theedge,we use it as the standard for graph efficientpartitioningthe same as the abovemethod. Triangle-based Heuristic DFS EncodingGraph Partition Method greatlyimproves the efficiency of computing,and the value of edge and partition results aregood.We designed experiments which use virtual network structure to verify the scaleof the sub-graphs and the efficiency of the method.We prove the feasibility of themethodby effective experimental data.