Research On Large Graph Aggregation Algorithm Based On Finite Memory

The graph aggregation(graph summarization)technique abstracts the vertexs and edges in the original graph to a higher level,and obtains a simple hypergraph which can represent the original graph.Compared with the original graph,it can effectively save storage space,solve the privacy protection problem in the social network and achieve fuzzy query issues.The existing graph aggregation algorithms assume that the entire graph information has be loaded into memory at once,so they do not be processed the large-scale graph which can not be fully loaded into memory at once.With physical expansion and the relationship become more complexity of the real world,graph grows rapidly.Such a large-scale complex graph will be more,and brings great challenges for the graph mining work.Similarly,the traditional graph aggregation algorithm does not apply to large-scale graph aggregation.At present,the more convenient solutions be proposed,just like the distributed graph computing system.For example,the large-scale graph computing system GraphX which based on the Spark framework,the Pregel graph computing system based on the BSP framework(Bulk Synchronous Parallel),the overall synchronous parallel model.Specifically used to deal with and optimize all kinds of tasks for complex graph computing.But the cost-effective control,security,algorithm debugging and management issues are more difficult.In view of this problem,the academic community propose graph computing system which based on the single machine,such as GraphChi,TurboGraph and other graph computing system.Compared with the distributed graph computing system,the graph computing system based on the single machine not only achieves reasonable expectation in the computing efficiency of the graph,and its applicability is also stronger.This paper first analyzes the differences and relation between graph aggregation and graph clustering,and helps researchers to understand the concept of graph aggregation.A new graph aggregation algorithm is proposed to deal with too many iterations in the current graph aggregation algorithm.It is proved by experiment that the algorithm can process large graphs based on memory in the effective time.And applied the algorithm on the graphChi graph computing system of the stand-alone graph computing system,to realized the large aggregation based on the limited memory.