A summary method of complex network diagrams

Abstract

The invention relates to a summary method of a complex network diagram. The complex network diagram is recorded as G=(V, E), V is a set of nodes, E is a set of edges. The method comprises the steps of1, selecting a subgraph H=(V ', E') from the complex network graph, wherein the formula of the sub-graph is shown in the specification, and the formula of the sub-graph is shown in the specification;for the edge formed by any two nodes in the sub-graph, the following conditions are met: sup(e(u, v),H) is greater than or equal to k-2, marking the subgraphs as dense subgraphs; Step 2, compressingall nodes in each dense subgraph into a node, marking the node as a super point, and marking edges associated with all the super points as super edges; and step 3, forming a new node set by all the super points and other nodes except the super points, forming a new edge set by the super edges and other edges except the super edges, and forming a summary graph by the new node set and the new edge set. The data scale can be effectively reduced, the phenomenon of dense nodes and associated edges in the network layout is reduced, and the power and clustering coefficients of the original graph areapproximately kept; and the overall structure of the data can be clearly displayed.

Description

technical field [0001] The invention relates to the field of data processing, in particular to a method for summarizing complex network diagrams. Background technique [0002] There are a large number of complex networks in modern society, such as computer networks, Internet of Things, communication networks, transportation networks, and social relationship networks, etc. Effective analysis of networks has become an important scientific issue. The complex network can be described by a graph in the data structure. The nodes of the graph represent the entities in the network, and the edges represent the connections between entities. As the network scale increases, more storage space is required. The ultra-large-scale complex network brings challenges to algorithm analysis and visualization. The complex network has a large number of nodes and edge associations, and it is difficult to extract and analyze effective information from the original network graph; its complex structu...

AI Technical Summary

Problems solved by technology

[0007] (3) The method based on graph sparseness: introduce the idea of ​​graph sparseness into complex network compression, and realize efficient algorithm analysis on the sparse graph that maintains the original graph properties and a certain accuracy; the graph sparse algorithm is a sampling method that retains nodes for edge sparseness , including generative graph sparseness, edge connected sparseness, clustering graph sparseness, and edge propagation graph sparseness algorithms, but the number of nodes in the network of this method remains unchanged, and the scale of complex networks is reduced by removing some redundant edges. The number of nodes in the middle is expanding, so the method of retaining all nodes is no longer suitable

Images