Research On Algorithm Of Weighted Graph Aggregation

With the era of big data coming, the research of graph aggregation (graph summarization) has become one of the hottest branches of the graphs. Graph aggregation makes use of the consistency of attribute or structure to aggregate a large graph to a concise graph that can express the main information, be understood and be analyzed. Because of the similarity between graph clustering and graph aggregation, this paper analyzes the relation and differences between them in theory, and proves its correction by using real dataset experiments.As the scale of the social network and information network increased rapidly, Graph aggregation technique is one of the effective ways to mine and analyze huge graphs. However, in reality, these graphs are not only huge but also carry weighted edges. The current algorithms do not or seldom take the weight into consideration, leading to a great difference between the aggregation graph and the original one.In order to solve this problem and improve the quality and efficiency of graph aggregation, The weighted graph aggregation algorithm is studied, the consistency of grouping area values of the adjacent matrix of the aggregation graphs is introduced to measure the consistency of weights of edges, compression ratio is defined to measure the spatial efficiency of the graph aggregation algorithm, and error rate is used to evaluate the difference between the aggregation graph and the original graph. The compression quality is ensured by controlling error rates and a comparison is made between the proposed algorithm and the existing graph aggregation algorithms. The experiment results show the effectiveness of the graph aggregation algorithm.Based on the aggregated weighted graph, this paper studies the query of corresponding aggregation graph:subgraph query and reachable query. In the aggregation graph, subgraph query improves the SMS algorithm that widely used, and it is applied to weighted aggregation graph. In reachable query, user self-defines two vertices, the step of reachable query and the maxim difference of weight w under the situation that when they cannot confirm whether they are reachable, then the result is returned to user.