Research On Graph Aggregation Algorithm Based On Structural Consistency

In social networks,molecular biology,communication networks,and many other fields,there are often graphs with hundreds of millions of nodes and billions of edges.As graph data grows,mining and visualizing these big graph becomes a challenging task.The runtime of most graph algorithms grows with the size of the input(the number of nodes and/or edges).Executing them on huge graphs may be impractical,especially if the input graph is too large to operate in memory.Graph summary summarizes the nodes and edge sets in the original image to obtain a concise hypergraph while retaining information about most of the structure or properties of the original image.Graph summary speeds up analysis by creating a lossy,compact representation of the graph.Due to the complexity of the structure and the increase of the size of the graphics,how to efficiently summarize the large-map data and find a consistent or interesting structure,the operation of the graph algorithm still needs detailed and systematic research.Firstly,starting from the simple graph,the proposed graph summary algorithm not only considers the structural consistency within a group or between groups,but also considers the probability of existence on the edge of the aggregate graph.The compression ratio to measure the compression degree of the input graph,and using the reconstruction error to quantify the similarity between original graph and the summary.Structural homogeneity based on information entropy,where very dense or very sparse inter-node or intra-node structures are preferred.It is demonstrated that the structural homogeneity of the total minimum information entropy is a non-convex problem and is an NP problem.Therefore,a heuristic method for gradually approximating the objective function by row-column exchange is proposed,and the calculation information gain is proposed to reduce the calculation amount.Based on the study of graph summary,it is further extended to weighted graphs and directed graphs.In the process of studying the weighted graph summary,the structural homogeneity of the weighted graph summary is calculated by counting the probability of occurrence of different weights in the adjacency matrix after random grouping of the statistical weighted graph.In the process of clustering graphs.The structural homogeneity of the directed graph summary is calculated by the probability of the occurrence of the statistical-1,0,1,in the adjacency matrix after random grouping of statistical directed graphs.Experiment with the existing graph summary algorithm on the real data set and analyze the experimental results to demonstrate the effectiveness of the graph summary algorithm and weighted graph summary algorithm proposed in this paper.And demonstrate the validity and efficiency of the graph aggregation algorithm proposed in this paper.