Similarity Nodes Query Processing Approach In The Evolution Process Of Large Dynamic Graph

With the expansion of application fields, graph as one kind of data structures we commonly used, it is commonly used in the field of actual application, like Web knowledge discovery, community relations network and transportation network at present. When we want to describe some practical applications by using this kind of large graph, the graph will change its topology structure because of the change of its actual application semantics over time; it means the dynamic evolution of the graph. In practice, people often pay attention to the change of contact between the nodes and how to keep contact between the nodes in the process of evolution of the topology structure on the dynamic graph in the time domain. For example, whether the attention node contacts with the current node frequently, and this kind of contact is evenly distributed on the whole time domain at the same time; whether the attention node contacts with the current node frequently in the time domain, and this kind of contact maintain for a long time every time, etc. Because we want to focus on the condition of the node how to maintain contact with the current node in the process of evolution change, so in this paper we called this kind of node with the similarity node of the current node, and measured the level of similarity with the current node by some conditions including:whether it is contacted with the current node frequently; whether it is distributed evenly and whether it is maintained for a long time. The similarity query method main research on graph focuses on the subgraph similarity, and making the subgraph similarity query on the large static graph or the dynamic accumulation change graph often, however, paying little attention to the process of the dynamic evolution on the graph. This paper made the research on this kind of similarity nodes query processing problem in the time of large dynamic graph evolution, and provided a kind of similarity nodes query processing approach on large dynamic graph based on the snapshots. The concrete content includes:(1)The expression of the snapshots of the evolution process on the graph, which we called it evolution dynamic graph; the semantic representation of the nodes ubiquitous similarity and the nodes direct similarity in the dynamic evolution process on the graph and their formal representations, we describe the level of the node similarity in two sides, which including:the frequent degree of contact and uniformity coefficient of distribution, the frequent degree of contact and the time of duration.(2) The representation and the process method of the semantic of the node ubiquitous similarity and the node direct similarity by the matrix. This method analysis the semantics of the node ubiquitous similarity and the node direct similarity, and import the concept of matrix transformation, optimizing similar node of the query processing, and reducing the computational work to reduce the system overhead.(3)Two algorithms which process similarity node query process under these two kinds of semantic. The experimental results on the synthetic datasets and the real datasets show that the proposed algorithm can deal with the node similarity query on the large dynamic graph effectively, and has good performance in the practical application.