Degree feature replacement policy based stream type graph sampling method

Abstract

The invention belongs to the field of stream type graph data sampling and particularly relates to a degree feature replacement policy based sampling method. The method comprises the steps of: S1, when the stream type edge [e=(u,v)] is reached, judging whether point replacement is generated, and if so, performing the step S2, or otherwise, performing the step S7; S2, according to the degree features of points in sampling sub-graphs Gs, determining a point replacement probability function f(di), wherein di is an element of D and D is a degree distribution set of the points in the sub-graphs; according to the probability function, calculating the replacement probability, defined in the description, of a point vi, and obtaining the point replacement probability set, defined in the description, in the sub-graphs; S3, adopting a selection algorithm [select(P)] in a genetic algorithm to select a to-be-replaced point r, wherein P is the point replacement probability set calculated in the step S2; S4, according to a replacement rule, judging whether the point r selected in the step S3 meets the requirements, and if so, going to the step S5, or otherwise, going to the step S3; S5, deleting r from Vs and deleting the r-related edge from Es; S6, deleting an independent point from Vs; and S7, adding new points and edges [e] into the sub-graphs. According to the method, the similarity of the obtained sampling sub-graphs and an original graph is high.

Description

technical field [0001] The invention belongs to the technical field of flow graph data sampling, and more specifically relates to a flow graph sampling method based on a degree feature replacement strategy. Background technique [0002] As a data structure capable of expressing rich data and relationships, graphs are widely used in analysis in various fields. When the scale of graph data reaches a very high order of magnitude, the overhead of performing full graph analysis and operations is very high. Moreover, in actual scenarios, the information of points and edges will change dynamically over time, that is, a dynamic graph. In this case, full graph analysis is difficult to achieve. At this time, it is generally possible to select some points or edges in the graph to obtain a sampled subgraph, and then process it in order to obtain sufficiently accurate results, which will alleviate or eliminate the processing difficulty brought about by the scale of the graph and the dyn...

AI Technical Summary

Problems solved by technology

[0004] The purpose of the present invention is to provide a flow graph sampling algorithm based on partial derivation edge sampling based on the degree feature replacement strategy. Problems such as clustering of points and too dense edges of subgraphs, the obtained subgraphs have a high degree of similarity with the characteristics of the original graphs

Images